IsoRank: We describe an algorithm for global alignment of multiple protein-protein inter- action (PPI) networks. The algorithm aims to maximize the overall match across all input networks. This is, to our knowledge, the first algorithm for this problem. In contrast, much of the previous work in the field has focused on local network alignment. The intuition behind our algorithm is that a protein in one PPI net- work is a good match for a protein in another network if the former’s neighbors are good matches for the latter’s neighbors. We encode this intuition by constructing an eigenvalue problem for every pair of input networks and then using k-partite matching to extract the final global alignment across all the species. Using our algorithm we compute the first known global alignment of PPI networks from five species: yeast, fly, worm, mouse and human. The global alignment immediately suggests functional orthologs across these species; we believe these are the first set of functional orthologs that cover all the five species. We show that these functional orthologs compare favorably with current sequence-only orthology prediction approaches, including better prediction of orthologs for some human disease-related proteins.

References in zbMATH (referenced in 16 articles )

Showing results 1 to 16 of 16.
Sorted by year (citations)

  1. Ganassali, Luca; Lelarge, Marc; Massoulié, Laurent: Spectral alignment of correlated Gaussian matrices (2022)
  2. Liang, Bo; Wang, Lin; Wang, Xiaofan: OLMNE+FT: multiplex network embedding based on overlapping links (2022)
  3. Rácz, Miklós Z.; Sridhar, Anirudh: Correlated randomly growing graphs (2022)
  4. Ding, Jian; Ma, Zongming; Wu, Yihong; Xu, Jiaming: Efficient random graph matching via degree profiles (2021)
  5. Nassar, Huda; Kollias, Georgios; Grama, Ananth; Gleich, David F.: Scalable algorithms for multiple network alignment (2021)
  6. Chen, Shuo; Bowman, F. DuBois; Xing, Yishi: Detecting and testing altered brain connectivity networks with k-partite network topology (2020)
  7. Zhou, Fan; Zhang, Kunpeng; Xie, Shuying; Luo, Xucheng: Learning to correlate accounts across online social networks: an embedding-based approach (2020)
  8. Ge, Li; Liu, Jiaguo; Zhang, Yusen; Dehmer, Matthias: Identifying anticancer peptides by using a generalized chaos game representation (2019)
  9. Malmi, Eric; Chawla, Sanjay; Gionis, Aristides: Lagrangian relaxations for multiple network alignment (2017)
  10. El-Kebir, Mohammed; Heringa, Jaap; Klau, Gunnar W.: Natalie 2.0: sparse global network alignment as a special case of quadratic assignment (2015)
  11. Rossi, Ryan A.; Gleich, David F.; Gebremedhin, Assefaw H.: Parallel maximum clique algorithms with applications to network analysis (2015)
  12. Ibragimov, Rashid; Malek, Maximilian; Guo, Jiong; Baumbach, Jan: GEDEVO: an evolutionary graph edit distance algorithm for biological network alignment (2013)
  13. Fionda, Valeria: Biological network analysis and comparison: mining new biological knowledge (2011) ioport
  14. Fokkens, Like; Botelho, Sandra M. C.; Boekhorst, Jos; Snel, Berend: Enrichment of homologs in insignificant BLAST hits by co-complex network alignment (2010) ioport
  15. Tuller, Tamir; Felder, Yifat; Kupiec, Martin: Discovering local patterns of co - evolution: computational aspects and biological examples (2010) ioport
  16. Klau, Gunnar W.: A new graph-based method for pairwise global network alignment (2009) ioport