GraphAlignment: Bayesian pairwise alignment of biological networks

BMC Systems Biology

Johannes Berg²  Michael Lässig²  Ville Mustonen³  Jörn Meier²  Michal Kolář¹ 

[1] Institute of Molecular Genetics, Academy of Sciences of the Czech Republic, Vídeňská 1083, CZ-14220 Praha, Czech Republic;Institut für Theoretische Physik, Universität zu Köln, Zülpicher Straße 77, D-50937 Köln, Germany;Present address: Wellcome Trust Sanger Institute, Wellcome Trust Genome Campus, Hinxton, CB10 1SA, UK

关键词: Bioconductor;    Parameter estimation;    Biological networks;    Graph alignment;   

Others  :  1143457
DOI  :  10.1186/1752-0509-6-144

 received in 2012-05-10, accepted in 2012-11-07,  发布年份 2012

【 摘 要 】

Background

With increased experimental availability and accuracy of bio-molecular networks, tools for their comparative and evolutionary analysis are needed. A key component for such studies is the alignment of networks.

Results

We introduce the Bioconductor package GraphAlignment for pairwise alignment of bio-molecular networks. The alignment incorporates information both from network vertices and network edges and is based on an explicit evolutionary model, allowing inference of all scoring parameters directly from empirical data. We compare the performance of our algorithm to an alternative algorithm, Græmlin 2.0.

On simulated data, GraphAlignment outperforms Græmlin 2.0 in several benchmarks except for computational complexity. When there is little or no noise in the data, GraphAlignment is slower than Græmlin 2.0. It is faster than Græmlin 2.0 when processing noisy data containing spurious vertex associations. Its typical case complexity grows approximately asView MathML">.

On empirical bacterial protein-protein interaction networks (PIN) and gene co-expression networks, GraphAlignment outperforms Græmlin 2.0 with respect to coverage and specificity, albeit by a small margin. On large eukaryotic PIN, Græmlin 2.0 outperforms GraphAlignment.

Conclusions

The GraphAlignment algorithm is robust to spurious vertex associations, correctly resolves paralogs, and shows very good performance in identification of homologous vertices defined by high vertex and/or interaction similarity. The simplicity and generality of GraphAlignment edge scoring makes the algorithm an appropriate choice for global alignment of networks.

【 授权许可】

   
2012 Kolář et al.; licensee BioMed Central Ltd.

【 图 表 】

Figure 1.

Figure 2.

Figure 3.

Figure 4.

Figure 5.

Figure 6.

Figure 7.

【 参考文献 】

• [1]Ogata H, Goto S, Sato K, Fujibuchi W, Bono H, Kanehisa M: KEGG: Kyoto Encyclopedia of Genes and Genomes. Nucleic Acids Res 1999, 27:29-34. http://nar.oxfordjournals.org/content/27/1/29.abstract webcite
• [2]Stuart JM, Segal E, Koller D, Kim SK: A gene-coexpression network for global discovery of conserved genetic modules. Science 2003, 302(5643):249-255. [http://www.sciencemag.org/cgi/content/abstract/302/5643/249 webcite]
• [3]Phillips DC: The development of crystallographic enzymology. In British Biochemistry, Past and Present. Edited by Goodwin TW. (Academic Press, London,; 1970):pp. 11-28.
• [4]Amitai G, Shemesh A, Sitbon E, Shklar M, Netanely D, Venger I, Pietrokovski S: Network Analysis of Protein Structures Identifies Functional Residues. J Mol Biol 2004, 344(4):1135-1146. [http://www.sciencedirect.com/science/article/pii/S0022283604013592 webcite]
• [5]Uetz P, Dong YA, Zeretzke C, Atzler C, Baiker A, Berger B, Rajagopala S, Roupelieva M, Rose D, Fossum E, Haas J: Herpesviral protein networks and their interaction with the human proteome. Science 2006, 311:239-242.
• [6]Képès F: Biological networks. (World Scientific, Singapore; 2007).
• [7]Pevsner J: Bioinformatics and Functional Genomics. (John Wiley & Sons, New Jersey; 2009).
• [8]Wagner A: How the global structure of protein interaction networks evolves. Proc R Soc London. Series B: Biol Sci 2003, 270(1514):457-466. http://rspb.royalsocietypublishing.org/content/270/1514/457.abstract webcite
• [9]Wuchty S, Oltvai ZN, Barabási AL: Evolutionary conservation of motif constituents in the yeast protein interaction network. Nat Genet 2003, 35:176-179.
• [10]Kelley B, Sharan R, Karp R, Sittler T, Root D, Stockwell B, Ideker T: Conserved pathways within Bacteria and Yeast as revealed by global protein network alignment. Proc Natl Acad Sci USA 2003, 100(20):11394-11399.
• [11]Pinter R, Rokhlenko O, Yeger-Lotem E, Ziv-Ukelson M: Alignment of metabolic pathways. Bioinformatics 2005, 21:3401-3408.
• [12]Sharan R, Suthram S, Kelley R, Kuhn T, McCuine S, Uetz P, Sittler T, Karp R, Ideker T: Conserved patterns of protein interaction in multiple species. Proc Natl Acad Sci USA 2005, 102(6):1974-1979.
• [13]Bandyopadhyay S, Sharan R, Ideker T: Systematic identification of functional orthologs based on protein network comparison. Genome Res 2006, 16:428-435.
• [14]Pinney JW, Amoutzias GD, Rattray M, Robertson DL: Reconstruction of ancestral protein interaction networks for the bZIP transcription factors. Proc Nat Acad Sci 2007, 104(51):20449-20453. [http://www.pnas.org/content/104/51/20449.abstract webcite]
• [15]Beltrao P, Serrano L: Specificity and evolvability in eukaryotic protein interaction networks. PLoS Comput Biol 2007, 3(2):e25.
• [16]Cootes A, Muggleton S, Sternberg M: The identification of similarities between biological networks: application to the metabolome and interactome. J Mol Biol 2007, 369(4):1126-1139.
• [17]Papadimitriou CH, Steiglitz K: Combinatorial optimization: algorithms and complexity. (Dover Publications, Mineola, USA; 1998).
• [18]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-1354. [http://rsif.royalsocietypublishing.org/content/7/50/1341.abstract webcite]
• [19]Trusina A, Sneppen K, Dodd I, Shearwin K, Egan J: Functional alignment of regulatory networks: a study of temperate phages. PLoS Comput Biol 2005, 1(7):e74.
• [20]Kuchaiev O, Pržulj N: Integrative network alignment reveals large regions of global network similarity in yeast and human. Bioinformatics 2011, 27:1390-1396.
• [21]Bradde S, Braunstein A, Mahmoudi H, Tria F, Weigt M, Zecchina R: Aligning graphs and finding substructures by a cavity approach. EPL (Europhys Lett) 2010, 89(3):37009. [http://stacks.iop.org/0295-5075/89/i=3/a=37009 webcite]
• [22]Flannick J, Novak A, Do CB, Srinivasan BS, Batzoglou S: Automatic Parameter Learning for Multiple Local Network Alignment. J Comput Biol 2009, 16(8):1001-1022. http://www.liebertonline.com/doi/abs/10.1089/cmb.2009.0099 [PMID: 19645599] webcite
• [23]Kalaev M, Bafna V, Sharan R: Fast and Accurate Alignment of Multiple Protein Networks. J Comput Biol 2009, 16(8):989-999. http://www.liebertonline.com/doi/abs/10.1089/cmb.2009.0136. webcite [PMID: 19624266]
• [24]Klau G: A new graph-based method for pairwise global network alignment. BMC Bioinf 2009, 10(Suppl 1):S59. [http://www.biomedcentral.com/1471-2105/10/S1/S59 webcite] BioMed Central Full Text
• [25]Li Z, Zhang S, Wang Y, Zhang XS, Chen L: Alignment of molecular networks by integer quadratic programming. Bioinformatics 2007, 23:1631-1639.
• [26]Liao CS, Lu K, Baym M, Singh R, Berger B: IsoRankN: spectral methods for global alignment of multiple protein networks. Bioinformatics 2009, 25(12):i253—i258. [http://bioinformatics.oxfordjournals.org/content/25/12/i253.abstract webcite]
• [27]Zaslavskiy M, Bach F, Vert JP: Global alignment of protein–protein interaction networks by graph matching methods. Bioinformatics 2009, 25(12):i259—1267. [http://bioinformatics.oxfordjournals.org/content/25/12/i259.abstract webcite]
• [28]Berg J, Lässig M: Cross-species analysis of biological networks by Bayesian alignment. Proc Natl Acad Sci USA 2006, 103(29):10967-10972.
• [29]Henikoff S, Henikoff JG: Amino acid substitution matrices from protein blocks. Proc Natl Acad Sci USA 1992, 89:10915-10919.
• [30]Yu YK, Hwa T: Statistical significance of probabilistic sequence alignment and related local Hidden Markov Models. J Comput Biol 2001, 8:249-282.
• [31]Kolář M, Berg J, Lässig M: From protein interactions to functional annotation: Graph alignment in Herpes. BMC Syst Biol 2008, 2:90. [http://www.biomedcentral.com/1752-0509/2/90 webcite] BioMed Central Full Text
• [32]Phan HTT, Sternberg MJE: PINALOG: a novel approach to align protein interaction networks—implications for complex detection and function prediction. Bioinformatics 2012, 28:1239-1245.
• [33]Guo X, Hartemink AJ: Domain-oriented edge-based alignment of protein interaction networks. Bioinformatics 2009, 25(12):i240—1246. [http://bioinformatics.oxfordjournals.org/content/25/12/i240.abstract webcite]
• [34]Singh R, Xu J, Berger B: Pairwise global alignment of protein interaction networks by matching neighborhood topology. Proc the 11th Annu Int Conference Res Comput Mol Biol (2007): Lecture Notes Comput Sci 2007, 4453:16-31.
• [35]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:W83-W88.
• [36]Shlomi T, Segal D, Ruppin E, Sharan R: QPath: a method for querying pathways in a protein-protein interaction network. BMC Bioinf 2006, 7:199. BioMed Central Full Text
• [37]Pache RA, Céol A, Aloy P: NetAligner—a network alignment server to compare complexes, pathways and whole interactomes. Nucleic Acids Res 2012, 40:W157—W161.
• [38]Fionda V, Palopoli L: Biological Network Querying Techniques: Analysis and Comparison. J comput biol 2011, 18:595-625.
• [39]Berg J, Lässig M: Bayesian analysis of biological networks: Clusters, motifs, cross-species correlations. In Statistical and evolutionary analysis of biological networks. Edited by Stumpf MPH, Wiuf C. (Imperial College Press, London; 2009):pp. 65-84.
• [40]Kirkpatrick S, Gelatt CJ, Vecchi M: Optimization by Simulated Annealing. Science 1983, 220:671-680.
• [41]Jonker R, Volgenant A: A shortest augmenting path algorithm for dense and sparse linear assignment problems. Computing 1987, 38:325-340.
• [42]Powell S, Szklarczyk D, Trachana K, Roth A, Kuhn M, Muller J, Arnold R, Rattei T, Letunic I, Doerks T, Jensen LJ, von Mering C, Bork P: eggNOG v3.0: orthologous groups covering 1133 organisms at 41 different taxonomic ranges. Nucleic Acids Res 2012, 40:D284—9.
• [43]Szklarczyk D, Franceschini A, Kuhn M, Simonovic M, Roth A, Minguez P, Doerks T, Stark M, Muller J, Bork P, Jensen LJ, von Mering C: The STRING database in 2011: functional interaction networks of proteins, globally integrated and scored. Nucleic Acids Res 2011, 39(Database issue):D561—8.
• [44]Kerrien S, Aranda B, Breuza L, Bridge A, Broackes-Carter F, Chen C, Duesbury M, Dumousseau M, Feuermann M, Hinz U, Jandrasits C, Jimenez RC, Khadake J, Mahadevan U, Masson P, Pedruzzi I, Pfeiffenberger E, Porras P, Raghunath A, Roechert B, Orchard S, Hermjakob H: The IntAct molecular interaction database in 2012. Nucleic Acids Res 2012, 40(D1):D841—D846. [http://nar.oxfordjournals.org/content/40/D1/D841.abstract webcite]
• [45]Radivojac P, Peng K, Clark WT, Peters BJ, Mohan A, Boyle SM, Mooney SD: An integrated approach to inferring gene–disease associations in humans. Proteins: Struct, Funct, and Bioinf 2008, 72:1030-1037.
• [46]Collins SR, Kemmeren P, Zhao XC, Greenblatt JF, Spencer F, Holstege FCP, Weissman JS, Krogana NJ: Toward a Comprehensive Atlas of the Physical Interactome of Saccharomyces cerevisiae. Mol and Cell Proteomics 2007, 6:439-450.
• [47]Cherry JM, Hong EL, Amundsen C, Balakrishnan R, Binkley G, Chan ET, Christie KR, Costanzo MC, Dwight SS, Engel SR, Fisk DG, Hirschman JE, Hitz BC, Karra K, Krieger CJ, Miyasato SR, Nash RS, Park J, Skrzypek MS, Simison M, Weng S, Wong ED: Saccharomyces Genome Database: the genomics resource of budding yeast. Nucleic Acids Res 2012, 40:D700—5.
• [48]Engelen K, Fu Q, Meysman P, Sanchez-Rodriguez A, De Smet R, Lemmens K, Fierro A, Marchal K: COLOMBOS: access port for cross-platform bacterial expression compendia. PLoS ONE 2011, 6:e20938.
• [49]Faith JJ, Driscoll ME, Fusaro VA, Cosgrove EJ, Hayete B, Juhn FS, Schneider SJ, Gardner TS: Many Microbe Microarrays Database: uniformly normalized Affymetrix compendia with structured experimental metadata. Nucleic Acids Res 2008, 36(suppl 1):D866—D870. [http://nar.oxfordjournals.org/content/36/suppl_1/D866.abstract webcite]
• [50]Altschul SF, Gish W, Miller W, Myers EW, Lipman DJ: Basic local alignment search tool. J Mol Biol 1990, 215(3):403-410. [http://www.sciencedirect.com/science/article/pii/S0022283605803602 webcite]
• [51]Lewis ACF, Jones NS, Porter MA, Deane CM: What Evidence Is There for the Homology of Protein-Protein Interactions? PLoS Comput Biol 2012, 8(9):e1002645.