×

Geometry of the space of phylogenetic trees. (English) Zbl 0995.92035

Adv. Appl. Math. 27, No. 4, 733-767 (2001); erratum ibid. 29, No. 1, 136 (2002).
Summary: We consider a continuous space which models the set of all phylogenetic trees having a fixed set of leaves. This space has a natural metric of nonpositive curvature, giving a way of measuring distance between phylogenetic trees and providing some procedures for averaging or combining several trees whose leaves are identical. This geometry also shows which trees appear within a fixed distance of a given tree and enables construction of convex hulls of a set of trees.
This geometric model of tree spaces provides a setting in which questions that have been posed by biologists and statisticians over the last decade can be approached in a systematic fashion. For example, it provides a justification for disregarding portions of a collection of trees that agree, thus simplifying the space in which comparisons are to be made.

MSC:

92D15 Problems related to evolution
05C05 Trees
05C90 Applications of graph theory

Software:

PHYLIP
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Aldous, D., Probability distributions on cladograms, (Aldous, D.; Pemantle, R., Random Discrete Structures (1996), Springer-Verlag: Springer-Verlag New York), 1-18 · Zbl 0841.92015
[2] Berry, V.; Gascuel, O., Interpretation of bootstrap trees: Threeshold of clade selection and induced gain, Molecular Biol. Evolution, 13, 999-1011 (1996)
[3] Billera, L.; Chan, C.; Liu, N., Flag complexes, labelled rooted trees, and star shellings, (Chazelle, B.; Goodman, J. E.; Pollack, R., Advances in Discrete and Computational Geometry (1999), Am. Math. Soc: Am. Math. Soc Providence), 91-102 · Zbl 0941.52007
[4] L. Billera, S. Holmes, and, K. Vogtmann, A Geometrical Perspective on the Phylogenetic Tree Problem, Technical report, Statistics, Sequoia Hall, Stanford, CA, 2002.; L. Billera, S. Holmes, and, K. Vogtmann, A Geometrical Perspective on the Phylogenetic Tree Problem, Technical report, Statistics, Sequoia Hall, Stanford, CA, 2002.
[5] Böcker, S.; Dress, A. W.M., Recovering symbolically dated, rooted trees from symbolic ultrametrics, Adv. Math., 138, 105-125 (1998) · Zbl 0912.05031
[6] Bridson, M. R.; Haefliger, A., Metric Spaces of Non-positive Curvature. Metric Spaces of Non-positive Curvature, Grundlehren der math Wiss (1999), Springer-Verlag: Springer-Verlag Berlin/New York · Zbl 0988.53001
[7] Brooks, D. R., Hennig’s parasitological method: A proposed solution, Syst. Zool., 30, 229-249 (1981)
[8] Brown, K. S., Buildings (1989), Springer-Verlag: Springer-Verlag Berlin/New York
[9] Bruhat, F.; Tits, J., Groupes réductifs sur un corps local, Inst. HautesÉtudes Sci., 41, 5-252 (1972) · Zbl 0254.14017
[10] Davis, M.; Januszkiewicz, T.; Scott, R., Nonpositive curvature of blow-ups, Selecta Math., 4, 491-547 (1998) · Zbl 0924.53033
[11] Devadoss, S. L., Tessellations of moduli spaces and the mosaic operad, Homotopy Invariant Algebraic Structures (Baltimore, MD, 1998) (1999), Am. Math. Soc: Am. Math. Soc Providence, p. 91-114 · Zbl 0968.32009
[12] Diaconis, P., Group Representations in Probability and Statistics (1988), Institute of Mathematical Statistics: Institute of Mathematical Statistics Hayward · Zbl 0695.60012
[13] Diaconis, P.; Holmes, S., Matchings and phylogenetic trees, Proc. Nat. Acad. Sci. U.S.A., 95, 14600-14602 (1998) · Zbl 0908.92023
[14] Doyle, J. J., Gene trees and species trees: Molecular systematics as one-character taxonomy, Syst. Bot., 17, 144-163 (1992)
[15] Edelsbrunner, H., Algorithms in Combinatorial Geometry (1987), Springer-Verlag: Springer-Verlag Berlin/New York · Zbl 0634.52001
[16] Efron, B.; Halloran, E.; Holmes, S., Bootstrap confidence levels for phylogenetic trees, Proc. Nat. Acad. Sci. U.S.A., 93, 13429-13434 (1996) · Zbl 0871.62092
[17] Escalante, A.; Ayala, F., Phylogeny of the malarial genus plasmodium derived from rrna gene sequences, Proc. Nat. Acad. Sci., 91, 11371-11377 (1995)
[18] Felsenstein, J., Statistical inference of phylogenies (with discussion), J. Roy. Statist. Soc. Ser. A, 146, 246-272 (1983) · Zbl 0528.62090
[19] J. Felsenstein, http://evolution.genetics.washington.edu/phylip.html; J. Felsenstein, http://evolution.genetics.washington.edu/phylip.html
[20] Foulds, L. R.; Graham, R. L., The Steiner problem in phylogeny is NP-complete, Adv. Appl. Math., 3, 43-49 (1982) · Zbl 0489.92002
[21] Gromov, M., Hyperbolic groups, Essays in Group Theory (1987), Springer-Verlag: Springer-Verlag New York, p. 75-263 · Zbl 0634.20015
[22] Haeckel, E., Generelle Morphologie der Organismen: Allgemeine Grundzuge der organischen Formen-Wissenschaft, mechanisch begrundet durch die von Charles Darwin, reformite Descendenz-Theorie (1866), Georg Riemer: Georg Riemer Berlin
[23] Hayasaka, K.; Gojobori, T.; Horai, S., Molecular phylogeny and evolution of primate mitochondrial DNA, Mol. Biol. Evol., 5/6, 626-644 (1988)
[24] Holmes, S., Phylogenetic trees: An overview, Statistics and Genetics. Statistics and Genetics, IMA, 112 (1999), Springer-Verlag: Springer-Verlag New York, p. 81-118
[25] Jost, J., Nonpositive Curvature: Geometric and Analytic Aspects. Nonpositive Curvature: Geometric and Analytic Aspects, Lectures in Mathematics ETH Zürich (1997), Birkhäuser: Birkhäuser Basel · Zbl 0896.53002
[26] Kapranov, M. M., The permutoassociahedron, Mac Lane’s coherence theorem and asymptotic zones for the KZ equation, J. Pure Appl. Algebra, 85, 119-142 (1993) · Zbl 0812.18003
[27] Krushkal, J.; Li, W. H., Evolution of primate immunodeficiency viruses, (Auger, P.; Jean, R., Advances in Mathematical Population Dynamics—Molecules, Cells and Man (1998), World Scientific: World Scientific Singapore), 5-24 · Zbl 0932.92026
[28] Lee, C. W., The associahedron and triangulations of the \(n\)-gon, European J. Combin., 10, 551-560 (1989) · Zbl 0682.52004
[29] Lin, J.; Gerstein, M., Whole genome trees based on the occurrence of folds and orthologs: Implications for comparing genomes on different levels, Genome Res., 10, 808-818 (2000)
[30] Lovasz, L.; Plummer, M. D., Matching Theory (1985), North-Holland: North-Holland Amsterdam · Zbl 0618.05001
[31] MacFadden, B. J., Patterns of phylogeny and rates of evolution in fossil horses: Hipparions from the Miocene and Pliocene of North America, Paleobiology, 1, 245-257 (1985)
[32] Mallows, C. L., Non-null ranking models. I, Biometrika, 44, 114-130 (1957) · Zbl 0087.34001
[33] Robinson, A.; Whitehouse, S., The tree representation of \(σ_{n+1}\), J. Pure Appl. Algebra, 111, 245-253 (1996) · Zbl 0865.55010
[34] Schröder, E., Vier combinatorische probleme, Z. Math. Phys., 15, 361-376 (1870) · JFM 02.0108.04
[35] Shannon, W.; Banks, D., Combining classification trees using maximum likelihood estimation, Statist. Med., 18, 727-740 (1999)
[36] Sleator, D. D.; Tarjan, R. E.; Thurston, W. P., Rotation distance, triangulations, and hyperbolic geometry, J. Amer. Math. Soc., 1, 647-681 (1988) · Zbl 0653.51017
[37] Sleator, D. D.; Tarjan, R. E.; Thurston, W. P., Short encodings of evolving structures, SIAM J. Discrete Math., 5, 428-450 (1992) · Zbl 0796.68139
[38] Stanley, R., Enumerative Combinatorics (1999), Cambridge Univ. Press: Cambridge Univ. Press Cambridge
[39] Stasheff, J. D., Homotopy associativity of \(h\)-spaces i, Trans. Amer. Math. Soc., 108, 275-292 (1963) · Zbl 0114.39402
[40] K. T. Sturm, Nonlinear Markov Operators, Discrete Heat Flow, and Harmonic Maps between Singular Spaces, Preprint from, http://www-wt.iam.uni-bonn.de/homepages/sturm/sturm.html; K. T. Sturm, Nonlinear Markov Operators, Discrete Heat Flow, and Harmonic Maps between Singular Spaces, Preprint from, http://www-wt.iam.uni-bonn.de/homepages/sturm/sturm.html
[41] K. T. Sturm, Nonlinear Martingale Theory for Processes with Values in Metric Spaces of Nonpositive Curvature, Preprint from, http://www-wt.iam.uni-bonn.de/homepages/sturm/sturm.html; K. T. Sturm, Nonlinear Martingale Theory for Processes with Values in Metric Spaces of Nonpositive Curvature, Preprint from, http://www-wt.iam.uni-bonn.de/homepages/sturm/sturm.html
[42] Tukey, J. W., Mathematics and the picturing of data, Proceedings of the International Congress of Mathematicians (1975), Vancouver, p. 523-531
[43] Vogtmann, K., Local Structure of some out (\(F_n\))-complexes, Proc. Edinburgh Math. Soc., 33, 367-379 (1990) · Zbl 0694.20021
[44] Waterman, M. S.; Smith, T. F., On the similarity of dendrograms, J. Theoret. Biol., 73, 789-800 (1978)
[45] Zharkikh, A.; Li, W. H., Estimation of confidence in phylogeny: The complete and partial bootstrap technique, Mol. Phylogenet. Evol., 4, 44-63 (1995)
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.