LePrimAlign: local entropy-based alignment of PPI networks to predict conserved modules

Abstract

Background: Cross-species analysis of protein-protein interaction (PPI) networks provides an effective means of detecting conserved interaction patterns. Identifying such conserved substructures between PPI networks of different species increases our understanding of the principles deriving evolution of cellular organizations and their functions in a system level. In recent years, network alignment techniques have been applied to genome-scale PPI networks to predict evolutionary conserved modules. Although a wide variety of network alignment algorithms have been introduced, developing a scalable local network alignment algorithm with high accuracy is still challenging.

Results: We present a novel pairwise local network alignment algorithm, called LePrimAlign, to predict conserved modules between PPI networks of three different species. The proposed algorithm exploits the results of a pairwise global alignment algorithm with many-to-many node mapping. It also applies the concept of graph entropy to detect initial cluster pairs from two networks. Finally, the initial clusters are expanded to increase the local alignment score that is formulated by a combination of intra-network and inter-network scores. The performance comparison with state-of-the-art approaches demonstrates that the proposed algorithm outperforms in terms of accuracy of identified protein complexes and quality of alignments.

Conclusion: The proposed method produces local network alignment of higher accuracy in predicting conserved modules even with large biological networks at a reduced computational cost.

Keywords: Conserved modules; Local network alignment; Network alignment; PPI networks; Protein complex prediction; Protein-protein interactions.

Fig. 1

The overall flow diagram of LePrimAlign The proposed LePrimAlign algorithm takes two weighted PPI networks and BLAST scores of inter-network protein pairs as input, implements global network alignment PrimAlign as preprocessing, normalizes the PrimAlign scores, and iteratively performs four main steps for local network alignment: (1) seed node selection, (2) initial cluster formation, (3) cluster expansion, and (4) outputting the cluster pair

Fig. 2

A schematic view of (a) a match and (b) a gap between two clusters in different PPI networks In this example, θ denotes the PrimAlign score threshold to select the node pairs as seeds for local network alignment. A match represents an edge in one network directly conserved in the other whereas a gap represents an edge in one network indirectly conserved in the other