Parsimonious reconstruction of network evolution

Algorithms for Molecular Biology

Rob Patro²  Emre Sefer²  Justin Malin⁴  Guillaume Marçais³  Saket Navlakha¹  Carl Kingsford³ 

[1] School of Computer Science, Carnegie Mellon University, Pittsburgh, PA 15213, USA

[2] Department of Computer Science, University of Maryland, College Park, MD 20742, USA

[3] Program in Applied Mathematics, Statistics, and Scientific Computation, University of Maryland, College Park, MD 20742, USA

[4] Computational Biology, Bioinformatics and Genomics Concentration, Biological Sciences Graduate Program, University of Maryland, College Park, MD 20742, USA

关键词: Regulatory networks;    Interaction networks;    Ancestral network reconstruction;    Arsimony;    Network evolution;   

Others  :  794923
DOI  :  10.1186/1748-7188-7-25

 received in 2011-12-28, accepted in 2012-05-14,  发布年份 2012

【 摘 要 】

Background

Understanding the evolution of biological networks can provide insight into how their modular structure arises and how they are affected by environmental changes. One approach to studying the evolution of these networks is to reconstruct plausible common ancestors of present-day networks, allowing us to analyze how the topological properties change over time and to posit mechanisms that drive the networks’ evolution. Further, putative ancestral networks can be used to help solve other difficult problems in computational biology, such as network alignment.

Results

We introduce a combinatorial framework for encoding network histories, and we give a fast procedure that, given a set of gene duplication histories, in practice finds network histories with close to the minimum number of interaction gain or loss events to explain the observed present-day networks. In contrast to previous studies, our method does not require knowing the relative ordering of unrelated duplication events. Results on simulated histories and real biological networks both suggest that common ancestral networks can be accurately reconstructed using this parsimony approach. A software package implementing our method is available under the Apache 2.0 license athttp://cbcb.umd.edu/kingsford-group/parana webcite.

Conclusions

Our parsimony-based approach to ancestral network reconstruction is both efficient and accurate. We show that considering a larger set of potential ancestral interactions by not assuming a relative ordering of unrelated duplication events can lead to improved ancestral network inference.

【 授权许可】

   
2012 Patro et al.; licensee BioMed Central Ltd.

【 图 表 】

Figure 1.

Figure 2.

Figure 3.

Figure 4.

【 参考文献 】

• [1]Pachter L: An introduction to reconstructing ancestral genomes. Proc Symp Appl Mathematics 2007, 64:1-20.
• [2]Kreimer A, Borenstein E, Gophna U, Ruppin E: The evolution of modularity in bacterial metabolic networks. Proc Natl Acad Sci USA 2008, 105(19):6976-6981.
• [3]Pereira-Leal JB, Levy ED, Kamp C, Teichmann SA: Evolution of protein complexes by duplication of homomeric interactions. Genome Biol 2007, 8(4):R51. BioMed Central Full Text
• [4]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-1181.
• [5]Singh R, Xu J, Berger B: Pairwise global alignment of protein interaction networks by matching neighborhood topology. Proc. Intl. Conf. on Research in Computational Molecular Biology (RECOMB) 2007, 16-31.
• [6]Dutkowski J, Tiuryn J: Identification of functional modules from conserved ancestral protein–protein interactions. Bioinformatics 2007, 23(13):i149-i158.
• [7]Erten S, Li X, Bebek G, Li J, Koyuturk M: Phylogenetic analysis of modularity in protein interaction networks. BMC Bioinformatics 2009, 10:333. BioMed Central Full Text
• [8]Kuchaiev O, Milenkovic T, Memisevic V, Hayes W, Przulj N: Topological network alignment uncovers biological function and phylogeny. J R Soc Interface 2010, 7(50):1341-1354.
• [9]Aldana M, Balleza E, Kauffman S, Resendiz O: Robustness and evolvability in genetic regulatory networks. J Theor Biol 2007, 245(3):433-448.
• [10]Espinosa-Soto C, Martin OC, Wagner A: Phenotypic robustness can increase phenotypic variability after nongenetic perturbations in gene regulatory circuits. J Evol Biol 2011, 24(6):1284-1297.
• [11]Raman K, Wagner A: Evolvability and robustness in a complex signalling circuit. Mol Biosyst 2011, 7(4):1081-1092.
• [12]Borenstein E, Kupiec M, Feldman MW, Ruppin E: Large-scale reconstruction and phylogenetic analysis of metabolic environments. Proc Natl Acad Sci USA 2008, 105(38):14482-14487.
• [13]Borenstein E, Feldman MW: Topological signatures of species interactions in metabolic networks. J Comput Biol 2009, 16(2):191-200.
• [14]Middendorf M, Ziv E, Wiggins CH: Inferring network mechanisms: the Drosophila melanogaster protein interaction network. Proc Natl Acad Sci USA 2005, 102(9):3192-3197.
• [15]Navlakha S, Kingsford C: Network archaeology: uncovering ancient networks from present-day interactions. PLoS Comput Biol 2011, 7(4):e1001119.
• [16]Gibson TA, Goldberg DS: Reverse engineering the evolution of protein interaction networks. Pac Symp Biocomput 2009, 14:190-202.
• [17]Levy ED, Pereira-Leal JB: Evolution and dynamics of protein interactions and networks. Curr Opin Struct Biol 2008, 18(3):349-357.
• [18]Pinney JW, Amoutzias GD, Rattray M, Robertson DL: Reconstruction of ancestral protein interaction networks for the bZIP transcription factors. Proc Natl Acad Sci USA 2007, 104(51):20449-20453.
• [19]Mirkin BG, Fenner TI, Galperin MY, Koonin EV: Algorithms for computing parsimonious evolutionary scenarios for genome evolution, the last universal common ancestor and dominance of horizontal gene transfer in the evolution of prokaryotes. BMC Evol Biol 2003, 3:2. BioMed Central Full Text
• [20]Zhang X, Moret BM: Boosting the performance of inference algorithms for transcriptional regulatory networks using a phylogenetic approach. Proc. Intl. Workshop on Algorithms in Bioinformatics (WABI) 2008, 245-258.
• [21]Zhang X, Moret B: Refining transcriptional regulatory networks using network evolutionary models and gene histories. Alg Mol Biol 2010, 5:1. BioMed Central Full Text
• [22]Mithani A, Preston G, Hein J: A stochastic model for the evolution of metabolic networks with neighbor dependence. Bioinformatics 2009, 25(12):1528-1535.
• [23]Chung F, Lu L, Dewey TG, Galas DJ: Duplication models for biological networks. J Comp Biol 2003, 10(5):677-687.
• [24]Teichmann SA, Babu MM: Gene regulatory network growth by duplication. Nat Genetics 2004, 36(5):492-496.
• [25]Pastor-Satorras R, Smith E, Sole R: Evolving protein interaction networks from gene duplication. J Theor Biol 2003, 222:199-210.
• [26]Ispolatov I, Krapivsky PL, Yuryev A: Duplication-divergence model of protein interaction network. Phys Rev E 2005, 71(6 Pt 1):061911.
• [27]Toll-Riera M, Bosch N, Bellora N, Castelo R, Armengol L, Estivill X, Mar Alba M: Origin of primate orphan genes: a comparative genomics approach. Mol Biol Evol 2009, 26(3):603-612.
• [28]Chen K, Durand D, Farach-Colton M: NOTUNG: a program for dating gene duplications and optimizing gene family trees. J Comput Biol 2000, 7(3-4):429-447.
• [29]Durand D, BV Halldórsson, Vernot B: A hybrid micro-macroevolutionary approach to gene tree reconstruction. J Comp Biol 2006, 13(2):320-335.
• [30]Arvestad L, Berglund AC, Sennblad B: Bayesian gene/species tree reconciliation and orthology analysis using MCMC. Bioinformatics 2003, 19(Suppl 1):i7-i15.
• [31]Stewart AJ, Seymour RM, Pomiankowski A: Degree dependence in rates of transcription factor evolution explains the unusual structure of transcription networks. Proc Biol Sci 2009, 276(1666):2493-2501.
• [32]Foster DV, Kauffman SA, Socolar JES: Network growth models and genetic regulatory networks. Phys Rev E 2006, 73(3):031912.
• [33]Fong JH, Keating AE, Singh M: Predicting specificity in bZIP coiled-coil protein interactions. Genome Biol 2004, 5(2):R11. BioMed Central Full Text