Abstract
An edge-weighted tree is called ultrametric if the distances from the root to all the leaves in the tree are equal. For an n by n distance matrix M, the minimum ultrametric tree for M is an ultrametric tree T = (V, E, w) with leaf set {1,..., n} such that dT(i, j) ≥ M[i, j] for all i, j and \(\sum {_{e \in E} w(e)}\) is minimum, where dT(i, j) is the distance between i and j on T. Constructing minimum ultrametric trees from distance matrices is an important problem in computational biology. In this paper, we examine its computational complexity and approximability. When the distances satisfy the triangle inequality, we show that the minimum ultrametric tree problem can be approximated in polynomial time with error ratio 1.5(1 + ⌈log n⌉), where n is the number of species. We also develop an efficient branch-and-bound algorithm for constructing the minimum ultrametric tree for both metric and non-metric inputs. The experimental results show that it can find an optimal solution for 25 species within reasonable time, while, to the best of our knowledge, there is no report of algorithms solving the problem even for 12 species.
This is a preview of subscription content, log in via an institution to check access.
Similar content being viewed by others
References
H.J. Bandelt, “Recognition of tree metrics,” SIAM Journal on Discrete Mathematics, vol. 3, no. 1, pp. 1-6, 1990.
N. Christofides, “Worst-case analysis of a new heuristic for the travelling salesman problem,” Technique Report, Graduate School of Industrial Administration, Carnegie-Mellon University, Pittsburgh, PA, 1976.
E. Dahlhaus, “Fast parallel recognition of ultrametrics and tree metrics,” SIAM Journal on Discrete Mathematics, vol. 6, no. 4, pp. 523-532, 1993.
W.H.E. Day, “Computationally difficult parsimony problems in phylogenetic systematics,” Journal of Theoretic Biology, vol. 103, pp. 429-438, 1983.
W.H.E. Day, “Computational complexity of inferring phylogenies from dissimilarity matrices,” Bulletin of Mathematical Biology, vol. 49, no. 4, pp. 461-467, 1987.
W.H.E. Day, D.S. Johnson, and D. Sankoff, “The computational complexity of inferring rooted phylogenies by parsimony,” Mathematical Biosciences, vol. 81, pp. 33-42, 1986.
M. Farach, S. Kannan, and T. Warnow, “A robust model for finding optimal evolutionary trees,” Algorithmica, vol. 13, pp. 155-179, 1995.
W.M. Fitch, “Anon-sequential method for constructing trees and hierarchical classifications,” Journal of Molecular Evolution, vol. 18, pp. 30-37, 1981.
L.R. Foulds, “Maximum savings in the Steiner problem in phylogeny,” Journal of Theoretic Biology, vol. 107, pp. 471-474, 1984.
L.R. Foulds and R.L. Graham, “The Steiner problem in phylogeny is NP-complete,” Advances in Applied Mathematics, vol. 3, pp. 43-49, 1982.
M.R. Garey and D.S. Johnson, Computers and Intractability: AGuide to the Theory of NP-Completeness, Freeman: San Fransisco, 1979.
D. Gusfield, Algorithms on Strings, Trees, and Sequences, Computer Science and Computational Biology, Cambridge University Press, 1997.
M.D. Hendy and D. Penny, “Branch and bound algorithms to determine minimal evolutionary trees,” Mathematical Biosciences, vol. 59, pp. 277-290, 1982.
R.M. Karp, “Reducibility among combinatorial problems,” in Complexity of Computer Computations, R.E. Miller and J.W. Thatcher (Eds.), Plenum Press: New York, 1972, pp. 85-103.
M. Krivanek, “The complexity of ultrametric partitions on graphs,” Information Processing Letter, vol. 27, no. 5, pp. 265-270, 1988.
W.H. Li and D. Graur, Fundamentals of Molecular Evolution, Sinauer Associates, 1991.
C.L. Liu, Introduction to Combinatorial Mathematics, McGraw-Hill: New York, 1968.
Author information
Authors and Affiliations
Rights and permissions
About this article
Cite this article
Wu, B.Y., Chao, KM. & Tang, C.Y. Approximation and Exact Algorithms for Constructing Minimum Ultrametric Trees from Distance Matrices. Journal of Combinatorial Optimization 3, 199–211 (1999). https://doi.org/10.1023/A:1009885610075
Issue Date:
DOI: https://doi.org/10.1023/A:1009885610075