skip to main content
research-article

Linear time 3-approximation for the MAST problem

Published: 23 March 2009 Publication History

Abstract

Given a set of leaf-labeled trees with identical leaf sets, the well-known Maximum Agreement SubTree (MAST) problem consists in finding a subtree homeomorphically included in all input trees and with the largest number of leaves. MAST and its variant called Maximum Compatible Tree (MCT) are of particular interest in computational biology. This article presents a linear-time approximation algorithm to solve the complement version of MAST, namely identifying the smallest set of leaves to remove from input trees to obtain isomorphic trees. We also present an O(n2 + kn) algorithm to solve the complement version of MCT. For both problems, we thus achieve significantly lower running times than previously known algorithms. Fast running times are especially important in phylogenetics where large collections of trees are routinely produced by resampling procedures, such as the nonparametric bootstrap or Bayesian MCMC methods.

References

[1]
Amir, A., and Keselman, D. 1997. Maximum agreement subtree in a set of evolutionary trees: Metrics and efficient algorithm. SIAM J. Comput. 26, 6, 1656--1669.
[2]
Berger-Wolf, T. 2004. Consensus and agreement of phylogenetic trees. In Proceedings of the 4th Workshop on Algorithms in Bioinformatics (WABI). Lecture Notes in Computer Science. Springer, 350--361.
[3]
Berry, V., and Nicolas, F. 2004. Maximum agreement and compatible supertrees. In Proceedings of the 15th Annual Symposium on Combinatorial Pattern Matching (CPM'04), S. C. Sahinalp et al., Eds. Lecture Notes in Computer Science, vol. 3109. Springer, 205--219.
[4]
Berry, V., and Nicolas, F. to appear. Improved parametrized complexity and approximation of the maximum agreement subtree and maximum compatible tree problems. IEEE/ACM Trans. Comput. Biol. Bioinf.
[5]
Bryant, D. 1997. Building trees, hunting for trees and comparing trees: Theory and method in phylogenetic analysis. Ph.D. thesis, University of Canterbury, Department of Mathemathics.
[6]
Bryant, D., Steel, M., and MacKenzie, A. 1983. The size of a maximum agreement subtree for random binary trees. In BioConsensus, M. Janowitz et al., Eds. DIMACS AMS, 55--66.
[7]
Cole, R., Farach-Colton, M., Hariharan, R., Przytycka, T. M., and Thorup, M. 2001. An O(n log n) algorithm for the maximum agreement subtree problem for binary trees. SIAM J. Comput. 30, 5, 1385--1404.
[8]
Downey, R. G., Fellows, M. R., and Stege, U. 1999. Computational tractability: The view from Mars. Bull. Eur. Assoc. Theor. Comput. Sci. 69, 73--97.
[9]
Farach, M., Przytycka, T. M., and Thorup, M. 1995. On the agreement of many trees. Inf. Process. Lett. 55, 6, 297--301.
[10]
Ganapathy, G., and Warnow, T. J. 2002. Approximating the complement of the maximum compatible subset of leaves of k trees. In Proceedings of the 5th International Workshop on Approximation Algorithms for Combinatorial Optimization (APPROX'02). Lecture Notes in Computer Science, vol. 2462. Springer, 122--134.
[11]
Ganapathysaravanabavan, G., and Warnow, T. J. 2001. Finding a maximum compatible tree for a bounded number of trees with bounded degree is solvable in polynomial time. In Proceedings of the 1st International Workshop on Algorithms in Bioinformatics (WABI'01), O. Gascuel and B. M. E. Moret, Eds. Lecture Notes in Computer Science, vol. 2149. Springer, 156--163.
[12]
Guindon, S., and Gascuel, O. 2003. A simple, fast and accurate method to estimate large phylogenies by maximum-likelihood. Syst. Biol. 52, 5, 696--704.
[13]
Gupta, A., and Nishimura, N. 1998. Finding largest subtrees and smallest supertrees. Algorithmica 21, 2, 183--210.
[14]
Hamel, A. M., and Steel, M. A. 1996. Finding a maximum compatible tree is NP-hard for sequences and trees. Appl. Math. Lett. 9, 2, 55--59.
[15]
Harel, D., and Tarjan, R. E. 1984. Fast algorithms for finding nearest common ancestor. SIAM J. Comput. 13, 2, 338--355.
[16]
Hein, J., Jiang, T., Wang, L., and Zhang, K. 1996. On the complexity of comparing evolutionary trees. Discrete Appl. Math. 71, 1--3, 153--169.
[17]
Kao, M.-Y., Lam, T. W., Sung, W.-K., and Ting, H.-F. 1999. A decomposition theorem for maximum weight bipartite matchings with applications to evolutionary trees. In Proceedings of the 7th Annual European Symposium on Algorithms (ESA'99). Lecture Notes in Computer Science, vol. 1643. Springer, 438--449.
[18]
Kao, M.-Y., Lam, T. W., Sung, W.-K., and Ting, H.-F. 2001. An even faster and more unifying algorithm for comparing trees via unbalanced bipartite matchings. J. Algor. 40, 2, 212--233.
[19]
McMorris, F., Meronik, D., and Neumann, D. 1983. A view of some consensus methods for trees. In Numerical Taxonomy, J. Felsenstein, Ed. Springer, 122--125.
[20]
Nishimura, N., Ragde, P., and Thilikos, D. 2004. Smaller kernels for hitting set problems of constant arity. In International Workshop on Parameterized and Exact Computation (IWPEC). Lecture Notes in Computer Science, vol. 3162. 121--126.
[21]
Semple, C., and Steel, M. 2003. Phylogenetics. Oxford Lecture Series in Mathematics and its Applications, vol. 24. Oxford University Press.
[22]
Steel, M. A., and Warnow, T. J. 1993. Kaikoura tree theorems: Computing the maximum agreement subtree. Inf. Process. Lett. 48, 2, 77--82.

Cited By

View all

Recommendations

Comments

Information & Contributors

Information

Published In

cover image ACM Transactions on Algorithms
ACM Transactions on Algorithms  Volume 5, Issue 2
March 2009
235 pages
ISSN:1549-6325
EISSN:1549-6333
DOI:10.1145/1497290
Issue’s Table of Contents
Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 23 March 2009
Accepted: 01 October 2008
Revised: 01 October 2008
Received: 01 April 2006
Published in TALG Volume 5, Issue 2

Permissions

Request permissions for this article.

Check for updates

Author Tags

  1. Approximation algorithm
  2. maximum agreement subtree
  3. maximum compatible subtree
  4. phylogenetic tree

Qualifiers

  • Research-article
  • Research
  • Refereed

Contributors

Other Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

  • Downloads (Last 12 months)2
  • Downloads (Last 6 weeks)0
Reflects downloads up to 15 Feb 2025

Other Metrics

Citations

Cited By

View all

View Options

Login options

Full Access

View options

PDF

View or Download as a PDF file.

PDF

eReader

View online with eReader.

eReader

Figures

Tables

Media

Share

Share

Share this Publication link

Share on social media