zbMATH — the first resource for mathematics

A parsimony-based metric for phylogenetic trees. (English) Zbl 1315.05034
Summary: In evolutionary biology various metrics have been defined and studied for comparing phylogenetic trees. Such metrics are used, for example, to compare competing evolutionary hypotheses or to help organize algorithms that search for optimal trees. Here we introduce a new metric \(d_{P}\) on the collection of binary phylogenetic trees each labeled by the same set of species. The metric is based on the so-called parsimony score, an important concept in phylogenetics that is commonly used to construct phylogenetic trees. Our main results include a characterization of the unit neighborhood of a tree in the \(d_{P}\) metric, and an explicit formula for its diameter, that is, a formula for the maximum possible value of \(d_{P}\) over all possible pairs of trees labeled by the same set of species. We also show that \(d_{P}\) is closely related to the well-known tree bisection and reconnection (tbr) and subtree prune and regraft (spr) distances, a connection which will hopefully provide a useful new approach to understanding properties of these and related metrics.

05C05 Trees
05C12 Distance in graphs
92B10 Taxonomy, cladistics, statistics in mathematical biology
Full Text: DOI
[1] Alberich, R.; Cardona, G.; Rosselló, F.; Valiente, G., An algebraic metric for phylogenetic trees, Appl. Math. Lett., 22, 1320-1324, (2009) · Zbl 1173.05314
[2] Allen, B.; Steel, M., Subtree transfer operations and their induced metrics on evolutionary trees, Ann. Comb., 5, 1-15, (2001) · Zbl 0978.05023
[3] Bogdanowicz, D.; Giaro, K., Matching split distance for unrooted binary phylogenetic trees, IEEE/ACM Trans. Comput. Biol. Bioinform., 9, 150-160, (2012)
[4] Bonet, M.; John, K. St.; Mahindru, R.; Amenta, N., Approximating subtree distances between phylogenies, J. Comput. Biol., 13, 1419-1434, (2006)
[5] Bordewich, M.; Semple, C., On the computational complexity of the rooted subtree prune and regraft distance, Ann. Comb., 8, 409-423, (2004) · Zbl 1059.05035
[6] Bruen, T.; Bryant, D., Parsimony via consensus, Syst. Biol., 57, 251-256, (2008)
[7] Bryant, D., The splits in the neighborhood of a tree, Ann. Comb., 8, 1-11, (2004) · Zbl 1094.68071
[8] Caceres, A.; Daley, S.; DeJesus, J.; Hintze, M.; Moore, D.; John, K. St., Walks in phylogenetic treespace, Inform. Process. Lett., 111, 600-604, (2011) · Zbl 1259.05176
[9] Day, W., Analysis of quartet dissimilarity measures between undirected phylogenetic trees, Syst. Zool., 35, 325-333, (1986)
[10] Ding, Y.; Grünewald, S.; Humphries, P., On agreement forests, J. Combin. Theory Ser. A, 118, 2059-2065, (2011) · Zbl 1231.05072
[11] Erdös, P.; Székely, L., Evolutionary trees: an integer multicommodity MAX-flow-MIN-cut theorem, Adv. in Appl. Math., 13, 375-389, (1992) · Zbl 0773.05047
[12] Hickey, G.; Dehne, F.; Rau-Chaplin, A.; Blouin, C., SPR distance computation for unrooted trees, Evol. Bioinform., 4, 17-27, (2008)
[13] Humphries, P.; Wu, T., On the neighborhood of trees, IEEE/ACM Trans. Comput. Biol. Bioinform., 10, 721-728, (2013)
[14] Kubatko, L., Inference of phylogenetic trees, (Friedman, A., Tutorials in Mathematical Biosciences IV: Evolution and Ecology, (2008), Springer-Verlag Berlin), 1-38 · Zbl 1300.92064
[15] Lin, Y.; Rajan, V.; Moret, B., A metric for phylogenetic trees based on matching, IEEE/ACM Trans. Comput. Biol. Bioinform., 9, 1014-1022, (2012)
[16] Robinson, D.; Foulds, L., Comparison of phylogenetic trees, Math. Biosci., 53, 131-147, (1981) · Zbl 0451.92006
[17] Semple, C.; Steel, M., Phylogenetics, (2003), Oxford University Press Oxford · Zbl 1043.92026
[18] Steel, M.; Penny, D., Distributions of tree comparison metrics - some new results, Syst. Biol., 42, 126-141, (1993)
[19] Waterman, M.; Smith, T., On the similarity of dendrograms, J. Theoret. Biol., 73, 789-800, (1978)
[20] Whelan, S.; Money, D., The prevalence of multifurations in tree-space and their implications for tree-search, Mol. Biol. Evol., 27, 2674-2677, (2010)
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. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.