Brief Survey of Biological Network Alignment and a Variant with Incorporation of Functional Annotations

Author(s): Fang Jing, Shao-Wu Zhang*, Shihua Zhang*.

Journal Name: Current Bioinformatics

Volume 14 , Issue 1 , 2019

Become EABM
Become Reviewer

Graphical Abstract:


Background: Biological network alignment has been widely studied in the context of protein-protein interaction (PPI) networks, metabolic networks and others in bioinformatics. The topological structure of networks and genomic sequence are generally used by existing methods for achieving this task.

Objective and Method: Here we briefly survey the methods generally used for this task and introduce a variant with incorporation of functional annotations based on similarity in Gene Ontology (GO). Making full use of GO information is beneficial to provide insights into precise biological network alignment.

Results and Conclusion: We analyze the effect of incorporation of GO information to network alignment. Finally, we make a brief summary and discuss future directions about this topic.

Keywords: Biological network, network alignment, gene ontology, alignment graph, optimization.

Zhang S, Jin G, Zhang XS, Chen L. Discovering functions and revealing mechanisms at molecular level from biological networks. Proteomics 2007; 7(16): 2856-69.
Zhang S, Tian D, Tran NH, Choi KP, Zhang L. Profiling the transcription factor regulatory networks of human cell types. Nucleic Acids Res 2014; 42(20): 12380-7.
Sharan R, Ideker T. Modeling cellular machinery through biological network comparison. Nat Biotechnol 2006; 24(4): 427-33.
Faisal FE, Meng L, Crawford J, Milenković T. The post-genomic era of biological network alignment. EURASIP J Bioinform Syst Biol 2015; 2015(1): 3.
Li Z, Zhang S, Wang Y, Zhang XS, Chen L. Alignment of molecular networks by integer quadratic programming. Bioinformatics 2007; 23(13): 1631-9.
Zhang S, Zhang XS, Chen L. Biomolecular network querying: a promising approach in systems biology. BMC Syst Biol 2008; 2(1): 5.
Pujol A, Mosca R, Farrés J, Aloy P. Unveiling the role of network and systems biology in drug discovery. Trends Pharmacol Sci 2010; 31(3): 115-23.
Faisal FE, Milenković T. Dynamic networks reveal key players in aging. Bioinformatics 2014; 30(12): 1721-9.
Faisal FE, Zhao H, Milenković T. Global network alignment in the context of agingIEEE/ACM Trans Comput Biol Bioinform 2015. 12(1): 40-52.
Sharan R, Suthram S, Kelley RM, et al. Conserved patterns of protein interaction in multiple species. Proc Natl Acad Sci USA 2005; 102(6): 275-86.
Flannick J, Novak A, Srinivasan BS, Mcadams HH, Batzoglou S. Graemlin: general and robust alignment of multiple large interaction networks. Genome Res 2006; 16(9): 1169-81.
Koyutürk M, Kim Y, Topkara U, Subramaniam S, Szpankowski W, Grama A. Pairwise alignment of protein interaction networks. J Bioinform Comput Biol 2006; 13(2): 182-99.
Berg J, Lässig M. Local graph alignment and motif search in biological networks. Proc Natl Acad Sci USA 2004; 101(41): 14689-94.
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.
Berg J, Lässig M. Cross-species analysis of biological networks by Bayesian alignment. Proc Natl Acad Sci USA 2006; 103(29): 10967-72.
Ciriello G, Mina M, Guzzi PH, Cannataro M, Guerra C. AlignNemo: a local network alignment method to integrate homology and topology. PLoS One 2012; 7(6): e38107.
Pache RA, Aloy P. A novel framework for the comparative analysis of biological networks. PLoS One 2012; 7(2): e31220.
Kelley BP, Yuan B, Lewitter F, Sharan R, Stockwell BR, Ideker T. PathBLAST: a tool for alignment of protein interaction networks. Nucleic Acids Res 2004; 32(Suppl. 2): W83-.
Clark C, Kalita J. A comparison of algorithms for the pairwise alignment of biological networks. Bioinformatics 2014; 30(16): 2351-9.
Liao CS, Lu K, Baym M, Singh R, Berger B. IsoRankN: spectral methods for global alignment of multiple protein networks. Bioinformatics 2009; 25(12): 253-8.
Kuchaiev O, Przulj N. Integrative network alignment reveals large regions of global network similarity in yeast and human. Bioinformatics 2011; 27(10): 1390-6.
Zaslavskiy M, Bach F, Vert JP. Global alignment of protein-protein interaction networks by graph matching methods. Bioinformatics 2009; 25(12): i259-67.
Phan HT, Sternberg MJ. PINALOG: a novel approach to align protein interaction networks--implications for complex detection and function prediction. Bioinformatics 2012; 28(9): 1239-45.
Neyshabur B, Khadem A, Hashemifar S, Arab SS. NETAL: a new graph-based method for global alignment of protein-protein interaction networks. Bioinformatics 2013; 29(13): 1654-62.
Saraph V, Milenković T. MAGNA: maximizing accuracy in global network alignment. Bioinformatics 2014; 30(20): 2931-40.
Sun Y, Crawford J, Tang J, Milenković T. Simultaneous Optimization of both Node and Edge Conservation in Network Alignment via Wave. Quant Biol 2015; 76(4): 439-56.
Sahraeian SM, Yoon BJ. SMETANA: accurate and scalable algorithm for probabilistic alignment of large-scale biological networks. PLoS One 2013; 8(7): e67995.
Hu J, Kehr B, Reinert K. NetCoffee: A fast and accurate global alignment approach to identify functionally conserved proteins in multiple networks. Bioinformatics 2014; 30(4): 540-8.
Ali W, Rito T, Reinert G, Sun F, Deane CM. Alignment-free protein interaction network comparison. Bioinformatics 2014; 30(17): 430-7.
Vijayan V, Saraph V, Milenkovi T. MAGNA++: Maximizing Accuracy in Global Network Alignment via both node and edge conservation. Bioinformatics 2015; 31(14): 2409-11.
Hashemifar S, Ma J, Naveed H, Canzar S, Xu J. ModuleAlign: module-based global alignment of protein–protein interaction networks. Bioinformatics 2016; 32(17): i658-64.
Chindelevitch L, Ma CY, Liao CS, Berger B. Optimizing a global alignment of protein interaction networks. Bioinformatics 2013; 29(21): 2765-73.
Aladağ AE, Erten C. SPINAL: scalable protein interaction network alignment. Bioinformatics 2013; 29(7): 917-24.
Singh R, Xu J, Berger B. Global alignment of multiple protein interaction networks with application to functional orthology detection. Proc Natl Acad Sci USA 2008; 105(35): 12763-8.
Kuchaiev O, Milenković T, Memišević V, Hayes W, Pržulj N. Topological network alignment uncovers biological function and phylogeny. J R Soc Interface 2010; 7(50): 1341-54.
Przulj N. Biological network comparison using graphlet degree distribution. Bioinformatics 2007; 23(2): e177-83.
Patro R, Kingsford C. Global network alignment using multiscale spectral signatures. Bioinformatics 2012; 28(23): 3105-14.
Milenković T, Ng WL, Hayes W, Pržulj N. Optimal Network Alignment with Graphlet Degree Vectors. Cancer Inform 2010; 9(9): 121-37.
Collins SR, Kemmeren P, Zhao XC, et al. Toward a comprehensive atlas of the physical interactome of Saccharomyces cerevisiae. Mol Cell Proteomics 2007; 6(3): 439-50.
Radivojac P, Peng K, Clark WT, et al. An integrated approach to inferring gene-disease associations in humans. Proteins 2008; 72(3): 1030-7.
Park D, Singh R, Baym M, Liao CS, Berger B. IsoBase: a database of functionally related proteins across PPI networks. Nucleic Acids Res 2011; 39(Suppl. 1): D295-300.
Altschul SF, Gish W, Miller W, Myers EW, Lipman DJ. Basic local alignment search tool. J Mol Biol 1990; 215(3): 403-10.

Rights & PermissionsPrintExport Cite as

Article Details

Year: 2019
Page: [4 - 10]
Pages: 7
DOI: 10.2174/1574893612666171020103747
Price: $58

Article Metrics

PDF: 44