Abstract
Genome-wide comparison of phylogenetic trees is becoming an increasingly common approach in evolutionary genomics, and a variety of approaches for such comparison have been developed. In this article, we present several methods for comparative analysis of large numbers of phylogenetic trees. To compare phylogenetic trees taking into account the bootstrap support for each internal branch, the Boot-Split Distance (BSD) method is introduced as an extension of the previously developed Split Distance method for tree comparison. The BSD method implements the straightforward idea that comparison of phylogenetic trees can be made more robust by treating tree splits differentially depending on the bootstrap support. Approaches are also introduced for detecting tree-like and net-like evolutionary trends in the phylogenetic Forest of Life (FOL), i.e., the entirety of the phylogenetic trees for conserved genes of prokaryotes. The principal method employed for this purpose includes mapping quartets of species onto trees to calculate the support of each quartet topology and so to quantify the tree and net contributions to the distances between species. We describe the application of these methods to analyze the FOL and the results obtained with these methods. These results support the concept of the Tree of Life (TOL) as a central evolutionary trend in the FOL as opposed to the traditional view of the TOL as a “species tree.”
Key words
This is a preview of subscription content, log in via an institution.
Buying options
Tax calculation will be finalised at checkout
Purchases are for personal use only
Learn about institutional subscriptionsAbbreviations
- CMDS:
-
Classical multidimensional scaling
- COG:
-
Clusters of orthologous genes
- BSD:
-
Boot-split distance
- FOL:
-
Forest of life
- HGT:
-
Horizontal gene transfer
- ND:
-
Nodal distance
- NUTs:
-
Nearly universal trees
- QT:
-
Quartet topology
- TNT:
-
Tree-net trend
- TOL:
-
Tree of life
- SD:
-
Split distance
References
Huerta-Cepas, J., Dopazo, H., Dopazo, J., and Gabaldon, T. (2007) The human phylome. Genome Biol 8, R109.
Huerta-Cepas, J., Bueno, A., Dopazo, J., and Gabaldon, T. (2008) PhylomeDB: a database for genome-wide collections of gene phylogenies. Nucleic Acids Res 36, D491-496.
Frickey, T., and Lupas, A. N. (2004) PhyloGenie: automated phylome generation and analysis. Nucleic Acids Res 32, 5231–5238.
Sicheritz-Ponten, T., and Andersson, S. G. (2001) A phylogenomic approach to microbial evolution. Nucleic Acids Res 29, 545–552.
Puigbo, P., Wolf, Y. I., and Koonin, E. V. (2009) Search for a Tree of Life in the thicket of the phylogenetic forest. J Biol 8, 59.
Felsenstein, J. (2004) Inferring Phylogenies. Sunderland, MA: Sinauer Associates.
Nei, M., and Kumar, S. (2001) Molecular Evolution and Phylogenetics. Oxford: Oxford Univ.
Castresana, J. (2007) Topological variation in single-gene phylogenetic trees. Genome Biol 8, 216.
Soria-Carrasco, V., and Castresana, J. (2008) Estimation of phylogenetic inconsistencies in the three domains of life. Mol Biol Evol 25, 2319–2329.
Marcet-Houben, M., and Gabaldon, T. (2009) The tree versus the forest: the fungal tree of life and the topological diversity within the yeast phylome. PLoS ONE 4, e4357.
Robinson, D. F., and Foulds, L. R. (1981) Comparison of phylogenetic trees. Math Biosci 53, 131–147.
Puigbo, P., Garcia-Vallve, S., and McInerney, J. O. (2007) TOPD/FMTS: a new software to compare phylogenetic trees. Bioinformatics 23, 1556–1558.
Steel, M. A., and Penny, D. (1993) Distribution of tree comparison metrics - some new results. Systematic Biol 42, 126–141.
Bluis, J., and Shin, D.-G. (2003) Nodal distance algorithm: calculating a phylogenetic tree comparison metric. In: Proceedings of the third IEEE symposium on bioInformatics and bioEngineering. IEEE Computer Society, 87–94.
Cardona, G., Llabres, M., Rossello, F., and Valiente, G. (2009) Nodal distances for rooted phylogenetic trees. J Math Biol.
Estabrook, G. F., McMorris, F. R., and Meachan, A. (1985) Comparison of undirected phylogenetic trees based on subtree of four evolutionary units. Syst Zool 34, 193–200.
Allen, L., and Steel, M. (2001) Subtree Transfer Operations and Their Induced Metrics on Evolutionary Trees Annals of Combinatorics 5, 1–15.
Waterman, M. S., and Steel, M. (1978) On the similarity of dendrograms. J Theor Biol 73, 789–800.
Beiko, R. G., and Hamilton, N. (2006) Phylogenetic identification of lateral genetic transfer events. BMC Evol Biol 6, 15.
Hickey, G., Dehne, F., Rau-Chaplin, A., and Blouin, C. (2008) SPR Distance Computation for Unrooted Trees. Evol Bioinform Online 4, 17–27.
Kubicka, E., Kubicki, G., and McMorris, F. R. (1995) An algorithm to find agreement subtrees. J Classification 12, 91–99.
Nye, T. M., Lio, P., and Gilks, W. R. (2006) A novel algorithm and web-based tool for comparing two alternative phylogenetic trees. Bioinformatics 22, 117–119.
de Vienne, D. M., Giraud, T., and Martin, O. C. (2007) A congruence index for testing topological similarity between trees. Bioinformatics 23, 3119–3124.
Cotton, J. A., and Page, R. D. (2002) Going nuclear: gene family evolution and vertebrate phylogeny reconciled. Proc Biol Sci 269, 1555–1561.
Soria-Carrasco, V., Talavera, G., Igea, J., and Castresana, J. (2007) The K tree score: quantification of differences in the relative branch length and topology of phylogenetic trees. Bioinformatics 23, 2954–2956.
Marcet-Houben, M., and Gabaldon, T. (2011) TreeKO: a duplication-aware algorithm for the comparison of phylogenetic trees. Nucleic Acids Res 39, e66.
Koonin, E. V., Wolf, Y. I., and Puigbo, P. (2009) The phylogenetic forest and the quest for the elusive tree of life. Cold Spring Harb Symp Quant Biol 74, 205–213.
Zuckerkandl, E., and Pauling, L. (1962) Molecular evolution. In: Horizons in Biochemistry. Edited by Kasha M, B. P. New York: Academic Press; 189–225.
Woese, C. R. (1987) Bacterial evolution. Microbiol Rev 51, 221–271.
Bapteste, E., O'Malley, M. A., Beiko, R. G., Ereshefsky, M., Gogarten, J. P., Franklin-Hall, L., et al. (2009) Prokaryotic evolution and the tree of life are two different things. Biol Direct 4, 34.
Doolittle, W. F. (2000) Uprooting the tree of life. Sci Am 282, 90–95.
Doolittle, W. F., and Bapteste, E. (2007) Pattern pluralism and the Tree of Life hypothesis. Proc Natl Acad Sci U S A 104, 2043–2049.
Kurland, C. G., Canback, B., and Berg, O. G. (2003) Horizontal gene transfer: A critical view. Proc Natl Acad Sci U S A 100, 9658–9662.
Kurland, C. G. (2005) What tangled web: barriers to rampant horizontal gene transfer. Bioessays 27, 741–747.
Logsdon, J. M., and Faguy, D. M. (1999) Thermotoga heats up lateral gene transfer. Curr Biol 9, R747-751.
Genereux, D. P., and Logsdon, J. M., Jr. (2003) Much ado about bacteria-to-vertebrate lateral gene transfer. Trends Genet 19, 191–195.
Kunin, V., Goldovsky, L., Darzentas, N., and Ouzounis, C. A. (2005) The net of life: reconstructing the microbial phylogenetic network. Genome Res 15, 954–959.
Daubin, V., Moran, N. A., and Ochman, H. (2003) Phylogenetics and the cohesion of bacterial genomes. Science 301, 829–832.
Lerat, E., Daubin, V., and Moran, N. A. (2003) From Gene Trees to Organismal Phylogeny in Prokaryotes:The Case of the gamma-Proteobacteria. PLoS Biol 1, E19.
Woese, C. R., Olsen, G. J., Ibba, M., and Soll, D. (2000) Aminoacyl-tRNA synthetases, the genetic code, and the evolutionary process. Microbiol Mol Biol Rev 64, 202–236.
Fitz-Gibbon, S. T., and House, C. H. (1999) Whole genome-based phylogenetic analysis of free-living microorganisms. Nucleic Acids Res 27, 4218–4222.
Hanage, W. P., Fraser, C., and Spratt, B. G. (2006) Sequences, sequence clusters and bacterial species. Philos Trans R Soc Lond B Biol Sci 361, 1917–1927.
Eisen, J. A., and Fraser, C. M. (2003) Phylogenomics: intersection of evolution and genomics. Science 300, 1706–1707.
Salzberg, S. L., White, O., Peterson, J., and Eisen, J. A. (2001) Microbial genes in the human genome: lateral transfer or gene loss? Science 292, 1903–1906.
Galtier, N. (2007) A model of horizontal gene transfer and the bacterial phylogeny problem. Syst Biol 56, 633–642.
Galtier, N., and Daubin, V. (2008) Dealing with incongruence in phylogenomic analyses. Philos Trans R Soc Lond B Biol Sci 363, 4023–4029.
Ciccarelli, F. D., Doerks, T., von Mering, C., Creevey, C. J., Snel, B., and Bork, P. (2006) Toward automatic reconstruction of a highly resolved tree of life. Science 311, 1283–1287.
Choi, I. G., and Kim, S. H. (2007) Global extent of horizontal gene transfer. Proc Natl Acad Sci U S A 104, 4489–4494.
Koonin, E. V., Wolf, Y. I., and Puigbo, P. (2009) The Phylogenetic Forest and the Quest for the Elusive Tree of Life. Cold Spring Harb Symp Quant Biol.
Dagan, T., and Martin, W. (2009) Getting a better picture of microbial evolution en route to a network of genomes. Philos Trans R Soc Lond B Biol Sci 364, 2187–2196.
Boucher, Y., Douady, C. J., Papke, R. T., Walsh, D. A., Boudreau, M. E., Nesbo, C. L., et al. (2003) Lateral gene transfer and the origins of prokaryotic groups. Annu Rev Genet 37, 283–328.
Bucknam, J., Boucher, Y., and Bapteste, E. (2006) Refuting phylogenetic relationships. Biol Direct 1, 26.
Schliep, K., Lopez, P., Lapointe, F. J., and Bapteste, E. (2011) Harvesting evolutionary signals in a forest of prokaryotic gene trees. Mol Biol Evol 28, 1393–1405.
Beiko, R. G., Doolittle, W. F., and Charlebois, R. L. (2008) The impact of reticulate evolution on genome phylogeny. Syst Biol 57, 844–856.
Doolittle, W. F., and Zhaxybayeva, O. (2009) On the origin of prokaryotic species. Genome Res 19, 744–756.
Gogarten, J. P., and Townsend, J. P. (2005) Horizontal gene transfer, genome innovation and evolution. Nat Rev Microbiol 3, 679–687.
Gogarten, J. P., Doolittle, W. F., and Lawrence, J. G. (2002) Prokaryotic evolution in light of gene transfer. Mol Biol Evol 19, 2226–2238.
Puigbo, P., Wolf, Y. I., and Koonin, E. V. (2010) The tree and net components of prokaryote evolution. Genome Biol Evol 2, 745–756.
Tatusov, R. L., Fedorova, N. D., Jackson, J. D., Jacobs, A. R., Kiryutin, B., Koonin, E. V., et al. (2003) The COG database: an updated version includes eukaryotes. BMC Bioinformatics 4, 41.
Jensen, L. J., Julien, P., Kuhn, M., von Mering, C., Muller, J., Doerks, T., et al. (2008) eggNOG: automated construction and annotation of orthologous groups of genes. Nucleic Acids Res 36, D250-254.
Edgar, R. C. (2004) MUSCLE: multiple sequence alignment with high accuracy and high throughput. Nucleic Acids Res 32, 1792–1797.
Castresana, J. (2000) Selection of conserved blocks from multiple alignments for their use in phylogenetic analysis. Mol Biol Evol 17, 540–552.
Keane, T. M., Naughton, T. J., and McInerney, J. O. (2007) MultiPhyl: a high-throughput phylogenomics webserver using distributed computing. Nucleic Acids Res 35, W33-37.
Creevey, C. J., and McInerney, J. O. (2005) Clann: investigating phylogenetic information through supertree analyses. Bioinformatics 21, 390–392.
Felsenstein, J. (1996) Inferring phylogenies from protein sequences by parsimony, distance, and likelihood methods. Methods Enzymol 266, 418–427.
Torgerson, W. S. (1958) Theory and Methods of Scaling. New York: Wiley.
Gower, J. C. (1966) Some distance properties of latent root and vector methods used in multivariate analysis. Biometrika 53, 325–328.
Tibshirani, R., Walther, G., and Hastie, T. (2001) Estimating the number of clusters in a data set via the gap statistic. Journal of the Royal Statistical Society: Series B (Statistical Methodology) 63, 411–423.
Hillis, D. M., Heath, T. A., and St John, K. (2005) Analysis and visualization of tree space. Syst Biol 54, 471–482.
Pavlidis, P., and Noble, W. S. (2003) Matrix2png: a utility for visualizing matrix data. Bioinformatics 19, 295–296.
Koonin, E. V., and Wolf, Y. I. (2008) Genomics of bacteria and archaea: the emerging dynamic view of the prokaryotic world. Nucleic Acids Res 36, 6688–6719.
Ge, F., Wang, L. S., and Kim, J. (2005) The cobweb of life revealed by genome-scale estimates of horizontal gene transfer. PLoS Biol 3, e316.
Brochier, C., Bapteste, E., Moreira, D., and Philippe, H. (2002) Eubacterial phylogeny based on translational apparatus proteins. Trends Genet 18, 1–5.
Wolf, Y. I., Rogozin, I. B., Grishin, N. V., and Koonin, E. V. (2002) Genome trees and the tree of life. Trends Genet 18, 472–479.
Wolf, Y. I., Rogozin, I. B., Grishin, N. V., Tatusov, R. L., and Koonin, E. V. (2001) Genome trees constructed using five different approaches suggest new major bacterial clades. BMC Evolutionary Biology 1.
Creevey, C. J., Fitzpatrick, D. A., Philip, G. K., Kinsella, R. J., O’Connell, M. J., Pentony, M. M., et al. (2004) Does a tree-like phylogeny only exist at the tips in the prokaryotes? Proc Biol Sci 271, 2551–2558.
Brochier-Armanet, C., Boussau, B., Gribaldo, S., and Forterre, P. (2008) Mesophilic Crenarchaeota: proposal for a third archaeal phylum, the Thaumarchaeota. Nat Rev Microbiol 6, 245–252.
Elkins, J. G., Podar, M., Graham, D. E., Makarova, K. S., Wolf, Y., Randau, L., et al. (2008) A korarchaeal genome reveals new insights into the evolution of the Archaea. Proc Natl Acad Sci USA in press.
Wolf, Y. I., Aravind, L., Grishin, N. V., and Koonin, E. V. (1999) Evolution of aminoacyl-tRNA synthetases--analysis of unique domain architectures and phylogenetic trees reveals a complex history of horizontal gene transfer events. Genome Res 9, 689–710.
Koonin, E. V. (2003) Comparative genomics, minimal gene-sets and the last universal common ancestor. Nature Rev Microbiol 1, 127–136.
Acknowledgments
The authors’ research is supported by the Department of Health and Human Services intramural program (NIH, National Library of Medicine).
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2012 Springer Science+Business Media, LLC
About this protocol
Cite this protocol
Puigbò, P., Wolf, Y.I., Koonin, E.V. (2012). Genome-Wide Comparative Analysis of Phylogenetic Trees: The Prokaryotic Forest of Life. In: Anisimova, M. (eds) Evolutionary Genomics. Methods in Molecular Biology, vol 856. Humana Press. https://doi.org/10.1007/978-1-61779-585-5_3
Download citation
DOI: https://doi.org/10.1007/978-1-61779-585-5_3
Published:
Publisher Name: Humana Press
Print ISBN: 978-1-61779-584-8
Online ISBN: 978-1-61779-585-5
eBook Packages: Springer Protocols