Ancestral genome reconstruction can be understood as a phylogenetic study with more details than a traditional phylogenetic tree reconstruction. We present a new computational system called REGEN for ancestral bacterial genome reconstruction at both the gene and replicon levels. REGEN reconstructs gene content, contiguous gene runs, and replicon structure for each ancestral genome. Along each branch of the phylogenetic tree, REGEN infers evolutionary events, including gene creation and deletion and replicon fission and fusion. The reconstruction can be performed by either a maximum parsimony or a maximum likelihood method. Gene content reconstruction is based on the concept of neighboring gene pairs. REGEN was designed to be used with any set of genomes that are sufficiently related, which will usually be the case for bacteria within the same taxonomic order. We evaluated REGEN using simulated genomes and genomes in the Rhizobiales order.
References
[1]
Boussau, B.; Karlberg, E.O.; Frank, A.C.; Legault, B.A.; Andersson, S.G. Computational inference of scenarios for alpha-proteobacterial genome evolution. Proc. Natl. Acad. Sci. USA 2004, 101, 9722–9727, doi:10.1073/pnas.0400975101. 15210995
[2]
Slater, S.C.; Goldman, B.S.; Goodner, B.; Setubal, J.C.; Farrand, S.K.; Nester, E.W.; Burr, T.J.; Banta, L.; Dickerman, A.W.; Paulsen, I.; et al. Genome sequences of three agrobacterium biovars help elucidate the evolution of multi-chromosome genomes in Bacteria. J. Bacteriol. 2009, 191, 2501–2511, doi:10.1128/JB.01779-08.
[3]
Sankoff, D.; Rousseau, P. Locating the vertices of a Steiner tree in an arbitrary metric space. Math. Progr. 1975, 9, 240–246, doi:10.1007/BF01681346.
[4]
Fitch, W.M. Toward defining the course of evolution : Minimum change for a specific tree topology. Syst. Zool. 1971, 20, 406–416, doi:10.2307/2412116.
[5]
Bhutkar, A.; Gelbart, W.M.; Smith, T.F. Inferring genome-scale rearrangement phylogeny and ancestral gene order: A Drosophila case study. Genome Biol. 2007, 8, doi:10.1186/gb-2007-8-11-r236.
[6]
Pe’er, I.; Shamir, R. The median problems for breakpoints are NP-complete. Electron. Colloq. Comput. Complex. 1998, 71, TR98-07.
[7]
Moret, B.M.E.; Tang, J.; Wang, L.S.; Warnow, T. Steps toward accurate reconstructions of phylogenies from gene-order data. J. Comput. Syst. Sci. 2002, 65, 508–525, doi:10.1016/S0022-0000(02)00007-7.
[8]
Caprara, A. Formulations and Hardness of Multiple Sorting by Reversals. In Proceedings of the 3rd International Conference of Computational Molecular Biology, Lyon, France, 11–14 April 1999; Istrail, S., Pevzner, P., Waterman, M., Eds.; ACM Press: New York, USA, 1999; pp. 84–93.
[9]
Moret, B.M.E.; Tang, J.; Warnow, T.; Gascuel, O. Reconstructing phylogenies from gene-content and gene-order data. In Mathematics of Evolution and Phylogeny; Oxford University Press: Oxford, UK, 2005; Volume Chapter 12, pp. 321–352.
[10]
Bourque, G.; Tesler, G.; Pevzner, P.A. The convergence of cytogenetics and rearrangement-based models for ancestral genome reconstruction. Genome Res. 2006, 16, 311–313, doi:10.1101/gr.4631806.
[11]
Eriksen, N. Reversal and transposition medians. Theor. Comput. Sci. 2007, 374, 111–126, doi:10.1016/j.tcs.2006.12.006.
[12]
Yang, K.; Setubal, J.C. Homology Prediction Refinement and Reconstruction of Gene Content and Order of Ancestral Bacterial Genomes. In Proceedings of the First ACM International Conference on Bioinformatics and Computational Biology, Niagara Falls, NY, USA, 2–4 August 2010; Zhang, A., Borodovsky, M., Eds.; ACM: New York, NY, USA; pp. 230–236. Available online: http://dl.acm.org (accessed on 10 July 2012).
[13]
Yang, K.; Setubal, J.C. A Whole Genome Simulator of Prokaryote Genome Evolution. In Proceedings of the Second ACM Conference on Bioinformatics, Computational Biology and Biomedicine, Chicago, IL, USA, 31 July–3 August 2011; Grossman, R., Rzhetsky, A., Eds.; ACM: New York, NY, USA; pp. 508–510. Available online: http://dl.acm.org (accessed on 10 July 2012).
[14]
The Setubal Research Group. Available online: http://staff.vbi.vt.edu/jcslab/tools.html (accessed on 1 July 2012).
[15]
Price, M.N.; Huang, K.H.; Alm, E.J.; Arkin, A.P. A novel method for accurate operon predictions in all sequenced prokaryotes. Nucl. Acids Res. 2005, 33, 880–892, doi:10.1093/nar/gki232. 15701760
[16]
Stamatakis, A. RAxML-VI-HPC: Maximum likelihood-based phylogenetic analyses with thousands of taxa and mixed models. Bioinformatics 2006, 22, 2688–2690, doi:10.1093/bioinformatics/btl446.
[17]
Li, L.; Stoeckert, C.J., Jr; Roos, D.S. OrthoMCL: Identification of ortholog groups for eukaryotic genomes. Genome Res. 2003, 13, 2178–2189, doi:10.1101/gr.1224503.
[18]
Buschbom, J.; Barker, D. Evolutionary history of vegetative reproduction in porpidia s.l. (lichen-forming ascomycota). Syst. Biol. 2006, 55, 471–484, doi:10.1080/10635150600697465.
[19]
Kanehisa, M.; Goto, S. KEGG: Kyoto encyclopedia of genes and genomes. Nucl. Acids Res. 2000, 28, 27–30, doi:10.1093/nar/28.1.27.
[20]
De Queiroz, A.; Gatesy, J. The supermatrix approach to systematics. Trends Ecol. Evol. 2007, 22, 34–41, doi:10.1016/j.tree.2006.10.002.
[21]
Altschul, S.F.; Madden, T.L.; Schffer, A.A.; Zhang, J.; Zhang, Z.; Miller, W.; Lipman, D.J. Gapped BLAST and PSI-BLAST: A new generation of protein database search programs. Nucl. Acids Res. 1997, 25, 3389–3402, doi:10.1093/nar/25.17.3389.
[22]
Edgar, R.C. MUSCLE: Multiple sequence alignment with high accuracy and high throughput. Nucl. Acids Res. 2004, 32, 1792–1797, doi:10.1093/nar/gkh340.
[23]
Castresana, J. Selection of conserved blocks from multiple alignments for their use in phylogenetic analysis. Mol. Biol. Evol. 2000, 17, 540–552, doi:10.1093/oxfordjournals.molbev.a026334.
[24]
Alexeyenko, A.; Tamas, I.; Liu, G.; Sonnhammer, E.L. Automatic clustering of orthologs and inparalogs shared by multiple proteomes. Bioinformatics 2006, 22, e9–e15, doi:10.1093/bioinformatics/btl213.
[25]
Kruskal, J. On the shortest spanning subtree of a graph and the traveling salesman problem. Proc. Am. Math. Soc. 1956, 7, 48–50, doi:10.1090/S0002-9939-1956-0078686-7.
[26]
Cormen, T.; Leiserson, C.; Rivest, R.; Stein, C. Introduction to Algorithms; McGraw-Hill: New York, NY, USA, 2003.
[27]
Harrison, P.W.; Lower, R.P.J.; Kim, N.K.D.; Young, J.P.W. Introducing the bacterial ’chromid’: Not a chromosome, not a plasmid. Trends Microbiol. 2010, 18, 141–148, doi:10.1016/j.tim.2009.12.010.
[28]
Wu, D.; Hugenholtz, P.; Mavromatis, K.; Pukall, R.; Dalin, E.; Ivanova, N.N.; Kunin, V.; Goodwin, L.; Wu, M.; Tindall, B.J.; et al. A phylogeny-driven genomic encyclopaedia of Bacteria and Archaea. Nature 2009, 462, 1056–1060, doi:10.1038/nature08656. 20033048
