Abstract
The Lp-min increment fit and Lp-min increment ultrametric fit problems are two popular optimization problems arising from distance methods for reconstructing phylogenetic trees. This paper proves
1. An O(n2) algorithm for approximating L ∞-min increment fit within ratio 3.
2. A ratio-O n 1/p polynomial time approximation to Lp-min increment ultrametric fit.
3. The neighbor-joining algorithm can correctly reconstruct a phylogenetic tree T when increment errors are small enough under L ∞-norm.
This is a preview of subscription content, log in via an institution to check access.
Similar content being viewed by others
References
R. Agarwala, V. Bafna, M. Farach, B. Narayanan, M. Paterson, and M. Thorup, “On the approximability of numerical taxonomy,” in Proceedings of the Seventh Annual ACM-SIAM Symposium on Discrete Algorithms, 1996, pp. 365-372.
K. Atteson, “The performance of neighbor-joining algorithms of phylogeny reconstruction,” in Proc. of The 3rd International Conference on Computing and Combinatorics, Shanghai, 1997, Lecture Notes in Computer Sciences, vol. 1276, pp. 101-110.
H.J. Bandelt and A. Dress, “Reconstructing the shape of a tree from observed dissimilarity data,” Advances in Applied Mathematics, vol. 7, pp. 309-343, 1986.
W.H.E. Day, “Computational complexity of inferring phylogenies from dissimilarity matrices,” Bulletin of Mathematical Biology, vol. 49, no. 4, pp. 461-467, 1987.
M. Farach, S. Kannan, and T. Warnow, “A robust model for finding optimal evolutionary trees,” Algorithmica, vol. 13, pp. 155-179, 1995.
J.S. Farris, “Estimating phylogenetic trees from distance matrices,” Am. Nat., vol. 106, pp. 645-668, 1972.
J. Felsenstein, “Numerical methods for inferring evolutionary trees,” Quart. Rev. Bio., vol. 57, pp. 379-404, 1982.
M. Křivánek, “The complexity of ultrametric partitions on graphs,” Infor. Proc. Letters, vol. 27, pp. 265-270, 1988.
C.H. Papadimitriou and K. Steiglitz, Combinatorial Optimization: Algorithms and Complexity, Prentice-Hall: Englewood Cliffs, NJ, 1982.
N. Saitou and M. Nei, “The neighbor-joining method: A new method for reconstructing phylogenetic trees,” Mol. Biol. Evol., vol. 4, pp. 406-425, 1987.
D. Swofford, G.J. Olsen, P.J. Waddell, and D.M. Hillis, “Phylogenetic inference,” in Molecular Systematics, 2nd edition, D.M. Hillis, C. Moritz, and B.K. Mable (Eds.), Sinauer Associates: Massachusetts, 1996.
M.S. Waterman, T.F. Smith, M. Singh, and W.A. Beyer, “Additive evolutionary trees,” J. Theoret. Biol., vol. 64, pp. 199-213, 1977.
B.Y. Wu, K.M. Chao, and C.Y. Tang, “Approximation and exact algorithms for constructing minimum ultrametric trees from distance matrices,” in Proc. of the 4th Annual International Conference on Computing and Combinatorics, Taiwan, 1998, pp. 299-308.
Author information
Authors and Affiliations
Rights and permissions
About this article
Cite this article
Ma, B., Wang, L. & Zhang, L. Fitting Distances by Tree Metrics with Increment Error. Journal of Combinatorial Optimization 3, 213–225 (1999). https://doi.org/10.1023/A:1009837726913
Issue Date:
DOI: https://doi.org/10.1023/A:1009837726913