Sawal Maskey
  Department of Computer Science
  Baylor University

  Young-Rae Cho
  Department of Computer Science
  Baylor University
 

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 systematic level. In recent years, network alignment techniques have been applied to 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. We present a novel pairwise local network alignment algorithm, called LePrimAlign, to predict conserved modules between PPI networks of two different species. The proposed algorithm exploits the results of a pairwise global alignment algorithm with many-to-many node mappings. 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 predicted protein complexes and quality of alignments. The proposed method produces local network alignments of higher accuracy in predicting conserved modules even with large biological networks at a reduced computational cost.
 

  Source Code: Download LePrimAlign (zip file)

  Input Data: Download Data (zip file)