Topological Network Alignment Uncovers Biological Function and Phylogeny

Overview

Journal J R Soc Interface

Specialties Biology
Biomedical Engineering
Biophysics

Date 2010 Mar 19

PMID 20236959

Citations 83

Authors

Oleksii Kuchaiev

Tijana Milenkovic

Vesna Memisevic

Wayne Hayes

Natasa Przulj

Affiliations

Soon will be listed here.

Abstract

Sequence comparison and alignment has had an enormous impact on our understanding of evolution, biology and disease. Comparison and alignment of biological networks will probably have a similar impact. Existing network alignments use information external to the networks, such as sequence, because no good algorithm for purely topological alignment has yet been devised. In this paper, we present a novel algorithm based solely on network topology, that can be used to align any two networks. We apply it to biological networks to produce by far the most complete topological alignments of biological networks to date. We demonstrate that both species phylogeny and detailed biological function of individual proteins can be extracted from our alignments. Topology-based alignments have the potential to provide a completely new, independent source of phylogenetic information. Our alignment of the protein-protein interaction networks of two very different species-yeast and human-indicate that even distant species share a surprising amount of network topology, suggesting broad similarities in internal cellular wiring across all life on Earth.

Citing Articles

Current and future directions in network biology.

Zitnik M, Li M, Wells A, Glass K, Morselli Gysi D, Krishnan A Bioinform Adv. 2024; 4(1):vbae099.

PMID: 39143982 PMC: 11321866. DOI: 10.1093/bioadv/vbae099.

Exact p-values for global network alignments via combinatorial analysis of shared GO terms : REFANGO: Rigorous Evaluation of Functional Alignments of Networks using Gene Ontology.

Hayes W J Math Biol. 2024; 88(5):50.

PMID: 38551701 PMC: 10980677. DOI: 10.1007/s00285-024-02058-z.

Network-Based Structural Alignment of RNA Sequences Using TOPAS.

Chen C, Jeong H, Qian X, Yoon B Methods Mol Biol. 2023; 2586:147-162.

PMID: 36705903 DOI: 10.1007/978-1-0716-2768-6_9.

Challenges and Limitations of Biological Network Analysis.

Milano M, Agapito G, Cannataro M BioTech (Basel). 2022; 11(3).

PMID: 35892929 PMC: 9326688. DOI: 10.3390/biotech11030024.

SANA: cross-species prediction of Gene Ontology GO annotations via topological network alignment.

Wang S, Atkinson G, Hayes W NPJ Syst Biol Appl. 2022; 8(1):25.

PMID: 35859153 PMC: 9300714. DOI: 10.1038/s41540-022-00232-x.

References

Przulj N, Corneil D, Jurisica I . Modeling interactome: scale-free or geometric?. Bioinformatics. 2004; 20(18):3508-15. DOI: 10.1093/bioinformatics/bth436. View

Przulj N, Kuchaiev O, Stevanovic A, Hayes W . Geometric evolutionary dynamics of protein interaction networks. Pac Symp Biocomput. 2009; :178-89. DOI: 10.1142/9789814295291_0020. View

Berg J, Lassig M . Local graph alignment and motif search in biological networks. Proc Natl Acad Sci U S A. 2004; 101(41):14689-94. PMC: 522014. DOI: 10.1073/pnas.0305199101. View

Collins S, Kemmeren P, Zhao X, Greenblatt J, Spencer F, Holstege F . Toward a comprehensive atlas of the physical interactome of Saccharomyces cerevisiae. Mol Cell Proteomics. 2007; 6(3):439-50. DOI: 10.1074/mcp.M600381-MCP200. View

Koyuturk M, Kim Y, Topkara U, Subramaniam S, Szpankowski W, Grama A . Pairwise alignment of protein interaction networks. J Comput Biol. 2006; 13(2):182-99. DOI: 10.1089/cmb.2006.13.182. View

Collins L, Penny D . Complex spliceosomal organization ancestral to extant eukaryotes. Mol Biol Evol. 2005; 22(4):1053-66. DOI: 10.1093/molbev/msi091. View

Liao C, Lu K, Baym M, Singh R, Berger B . IsoRankN: spectral methods for global alignment of multiple protein networks. Bioinformatics. 2009; 25(12):i253-8. PMC: 2687957. DOI: 10.1093/bioinformatics/btp203. View

Suthram S, Sittler T, Ideker T . The Plasmodium protein network diverges from those of other eukaryotes. Nature. 2005; 438(7064):108-12. PMC: 2830740. DOI: 10.1038/nature04135. View

Simonis N, Rual J, Carvunis A, Tasan M, Lemmens I, Hirozane-Kishikawa T . Empirically controlled mapping of the Caenorhabditis elegans protein-protein interactome network. Nat Methods. 2009; 6(1):47-54. PMC: 3057923. DOI: 10.1038/nmeth.1279. View

10.

Ito T, Chiba T, Ozawa R, Yoshida M, Hattori M, Sakaki Y . A comprehensive two-hybrid analysis to explore the yeast protein interactome. Proc Natl Acad Sci U S A. 2001; 98(8):4569-74. PMC: 31875. DOI: 10.1073/pnas.061034498. View

11.

Komili S, Farny N, Roth F, Silver P . Functional specificity among ribosomal proteins regulates gene expression. Cell. 2007; 131(3):557-71. PMC: 2443060. DOI: 10.1016/j.cell.2007.08.037. View

12.

Agrafioti I, Swire J, Abbott J, Huntley D, Butcher S, Stumpf M . Comparative analysis of the Saccharomyces cerevisiae and Caenorhabditis elegans protein interaction networks. BMC Evol Biol. 2005; 5:23. PMC: 1079807. DOI: 10.1186/1471-2148-5-23. View

13.

Xu P, Widmer G, Wang Y, Ozaki L, Alves J, Serrano M . The genome of Cryptosporidium hominis. Nature. 2004; 431(7012):1107-12. DOI: 10.1038/nature02977. View

14.

Kuchaiev O, Przulj N . Learning the structure of protein-protein interaction networks. Pac Symp Biocomput. 2009; :39-50. View

15.

Watts D, Strogatz S . Collective dynamics of 'small-world' networks. Nature. 1998; 393(6684):440-2. DOI: 10.1038/30918. View

16.

Liang Z, Xu M, Teng M, Niu L . NetAlign: a web-based tool for comparison of protein interaction networks. Bioinformatics. 2006; 22(17):2175-7. DOI: 10.1093/bioinformatics/btl287. View

17.

Kelley B, Yuan B, Lewitter F, Sharan R, Stockwell B, Ideker T . PathBLAST: a tool for alignment of protein interaction networks. Nucleic Acids Res. 2004; 32(Web Server issue):W83-8. PMC: 441549. DOI: 10.1093/nar/gkh411. View

18.

Przulj N, Higham D . Modelling protein-protein interaction networks via a stickiness index. J R Soc Interface. 2006; 3(10):711-6. PMC: 1664652. DOI: 10.1098/rsif.2006.0147. View

19.

Pennisi E . Modernizing the tree of life. Science. 2003; 300(5626):1692-7. DOI: 10.1126/science.300.5626.1692. View

20.

Tanriverdi S, Widmer G . Differential evolution of repetitive sequences in Cryptosporidium parvum and Cryptosporidium hominis. Infect Genet Evol. 2006; 6(2):113-22. DOI: 10.1016/j.meegid.2005.02.002. View