zbMATH — the first resource for mathematics

Approximating geodesic tree distance. (English) Zbl 1184.68658
Summary: Billera, Holmes, and Vogtmann introduced an intriguing new phylogenetic tree metric for weighted trees with useful properties related to statistical analysis. However, the best known algorithm for calculating this distance is exponential in the number of leaves of the trees compared. We point out that lower and upper bounds for this distance, which can be calculated in linear time, can differ by at most a multiplicative factor of \(\sqrt 2\).

68W40 Analysis of algorithms
PAUP*; MrBayes
Full Text: DOI
[1] Allen, B.L.; Steel, M., Subtree transfer operations and their induced metrics on evolutionary trees, Ann. of combin., 5, 1, 1-15, (2001) · Zbl 0978.05023
[2] Amenta, N.; Clarke, F.; St. John, K., A linear-time majority tree, (), 216-227
[3] N. Amenta, J. Klingner, Case study: Visualizing sets of evolutionary trees, in: 8th IEEE Symposium on Information Visualization (InfoVis 2002), 2002, pp. 71-74. Software available at comet.lehman.cuny.edu/treeviz
[4] Billera, L.J.; Holmes, S.P.; Vogtmann, K., Geometry of the space of phylogenetic trees, Adv. appl. math., 27, 733-767, (2001) · Zbl 0995.92035
[5] Bordewich, M.; Semple, C., On the computational complexity of the rooted subtree prune and regraft distance, Ann. of combin., 8, 409-423, (2005) · Zbl 1059.05035
[6] D. Bryant, Hunting for trees, building trees and comparing trees: theory and method in phylogenetic analysis, PhD thesis, Dept. of Mathematics, University of Canterbury, 1997
[7] DasGupta, B.; He, X.; Jiang, T.; Li, M.; Tromp, J.; Zhang, L., On computing the nearest neighbor interchange distance, (), 125-143 · Zbl 1133.92347
[8] Day, W.H.E., Optimal algorithms for comparing trees with labeled leaves, J. classification, 2, 1, 7-28, (1985) · Zbl 0589.62044
[9] Hillis, D.M.; Mable, B.K.; Moritz, C., Molecular systematics, (1996), Sinauer Assoc. Sunderland, MA
[10] J.P. Huelsenbeck, F. Ronquist, MrBayes: Bayesian inference of phylogeny, 2001
[11] Nixon, K.C., The parsimony ratchet, a new method for rapid parsimony analysis, Cladistics, 15, 407, (1999)
[12] C. Stockham, L.-S. Wang, T. Warnow, Statistically based postprocessing of phylogenetic analysis by clustering, in: Proceedings of 10th Internat. Conf. on Intelligent Systems for Molecular Biology (ISMB’02), Edmonton, Canada, 2002, pp. 285-293
[13] Swofford, D.L., PAUP*. phylogenetic analysis using parsimony (*and other methods). version 4, (2002), Sinauer Associates Sunderland, MA
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.