Parsimonious reconstruction of network evolution
- Rob Patro,
- Emre Sefer,
- Justin Malin,
- Guillaume Marçais,
- Saket Navlakha,
- Carl Kingsford
- … show all 6 hide
Abstract
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 at http://cbcb.umd.edu/kingsford-group/parana.
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.
- Pachter L: An introduction to reconstructing ancestral genomes. Proc Symp Appl Mathematics 2007, 64:1–20.
- 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. CrossRef
- Pereira-Leal JB, Levy ED, Kamp C, Teichmann SA: Evolution of protein complexes by duplication of homomeric interactions. Genome Biol 2007,8(4):R51. CrossRef
- 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. CrossRef
- 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. CrossRef
- Dutkowski J, Tiuryn J: Identification of functional modules from conserved ancestral protein–protein interactions. Bioinformatics 2007,23(13):i149-i158. CrossRef
- Erten S, Li X, Bebek G, Li J, Koyuturk M: Phylogenetic analysis of modularity in protein interaction networks. BMC Bioinformatics 2009, 10:333. CrossRef
- 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. CrossRef
- Aldana M, Balleza E, Kauffman S, Resendiz O: Robustness and evolvability in genetic regulatory networks. J Theor Biol 2007,245(3):433–448. CrossRef
- 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. CrossRef
- Raman K, Wagner A: Evolvability and robustness in a complex signalling circuit. Mol Biosyst 2011,7(4):1081–1092. CrossRef
- 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. CrossRef
- Borenstein E, Feldman MW: Topological signatures of species interactions in metabolic networks. J Comput Biol 2009,16(2):191–200. CrossRef
- 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. CrossRef
- Navlakha S, Kingsford C: Network archaeology: uncovering ancient networks from present-day interactions. PLoS Comput Biol 2011,7(4):e1001119. CrossRef
- Gibson TA, Goldberg DS: Reverse engineering the evolution of protein interaction networks. Pac Symp Biocomput 2009, 14:190–202.
- Levy ED, Pereira-Leal JB: Evolution and dynamics of protein interactions and networks. Curr Opin Struct Biol 2008,18(3):349–357. CrossRef
- 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. CrossRef
- 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. CrossRef
- 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.
- Zhang X, Moret B: Refining transcriptional regulatory networks using network evolutionary models and gene histories. Alg Mol Biol 2010, 5:1. CrossRef
- Mithani A, Preston G, Hein J: A stochastic model for the evolution of metabolic networks with neighbor dependence. Bioinformatics 2009,25(12):1528–1535. CrossRef
- Chung F, Lu L, Dewey TG, Galas DJ: Duplication models for biological networks. J Comp Biol 2003,10(5):677–687. CrossRef
- Teichmann SA, Babu MM: Gene regulatory network growth by duplication. Nat Genetics 2004,36(5):492–496. CrossRef
- Pastor-Satorras R, Smith E, Sole R: Evolving protein interaction networks from gene duplication. J Theor Biol 2003, 222:199–210. CrossRef
- Ispolatov I, Krapivsky PL, Yuryev A: Duplication-divergence model of protein interaction network. Phys Rev E 2005,71(6 Pt 1):061911. CrossRef
- 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. CrossRef
- 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. CrossRef
- Durand D, BV Halldórsson, Vernot B: A hybrid micro-macroevolutionary approach to gene tree reconstruction. J Comp Biol 2006,13(2):320–335. CrossRef
- Arvestad L, Berglund AC, Sennblad B: Bayesian gene/species tree reconciliation and orthology analysis using MCMC. Bioinformatics 2003,19(Suppl 1):i7-i15. CrossRef
- 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. CrossRef
- Foster DV, Kauffman SA, Socolar JES: Network growth models and genetic regulatory networks. Phys Rev E 2006,73(3):031912. CrossRef
- Fong JH, Keating AE, Singh M: Predicting specificity in bZIP coiled-coil protein interactions. Genome Biol 2004,5(2):R11. CrossRef
- Title
- Parsimonious reconstruction of network evolution
- Open Access
- Available under Open Access This content is freely available online to anyone, anywhere at any time.
- Journal
-
Algorithms for Molecular Biology
7:25
- Online Date
- September 2012
- DOI
- 10.1186/1748-7188-7-25
- Online ISSN
- 1748-7188
- Publisher
- BioMed Central
- Additional Links
- Topics
- Keywords
-
- Network evolution
- Arsimony
- Ancestral network reconstruction
- Interaction networks
- Regulatory networks
- Authors
-
-
Rob Patro
(1) (2)
-
Emre Sefer
(1) (2)
-
Justin Malin
(1) (3)
-
Guillaume Marçais
(1) (4)
-
Saket Navlakha
(5)
-
Carl Kingsford
(1) (2) (3) (4)
-
Rob Patro
- Author Affiliations
-
- 1. Center for Bioinformatics and Computational Biology, University of Maryland, College Park, MD, 20742, USA
- 2. Department of Computer Science, University of Maryland, College Park, MD, 20742, USA
- 3. Computational Biology, Bioinformatics and Genomics Concentration, Biological Sciences Graduate Program, University of Maryland, College Park, MD, 20742, USA
- 4. Program in Applied Mathematics, Statistics, and Scientific Computation, University of Maryland, College Park, MD, 20742, USA
- 5. School of Computer Science, Carnegie Mellon University, Pittsburgh, PA, 15213, USA