Linear time 3-approximation for the MAST problem

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(n² + 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: Amihood Amir , Dmitry Keselman, Maximum Agreement Subtree in a Set of Evolutionary Trees: Metrics and Efficient Algorithms, SIAM Journal on Computing, v.26 n.6, p.1656-1669, Dec. 1997 [doi>10.1137/S0097539794269461]
• 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: Vincent Berry , Francois Nicolas, Improved Parameterized Complexity of the Maximum Agreement Subtree and Maximum Compatible Tree Problems, IEEE/ACM Transactions on Computational Biology and Bioinformatics (TCBB), v.3 n.3, p.289-302, July 2006 [doi>10.1109/TCBB.2006.39]
• 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: Richard Cole , Martin Farach-Colton , Ramesh Hariharan , Teresa Przytycka , Mikkel Thorup, An O(nlog n) Algorithm for the Maximum Agreement Subtree Problem for Binary Trees, SIAM Journal on Computing, v.30 n.5, p.1385-1404, 2000 [doi>10.1137/S0097539796313477]
• 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: Martin Farach , Teresa M. Przytycka , Mikkel Thorup, On the agreement of many trees, Information Processing Letters, v.55 n.6, p.297-301, Sept. 29, 1995 [doi>10.1016/0020-0190(95)00110-X]
• 10: Ganeshkumar Ganapathy , Tandy Warnow, Approximating the Complement of the Maximum Compatible Subset of Leaves of k Trees, Proceedings of the 5th International Workshop on Approximation Algorithms for Combinatorial Optimization, p.122-134, September 17-21, 2002
• 11: Ganeshkumar Ganapathysaravanabavan , Tandy Warnow, Finding a Maximum Compatible Tree for a Bounded Number of Trees with Bounded Degree Is Solvable in Polynomial Time, Proceedings of the First International Workshop on Algorithms in Bioinformatics, p.156-163, August 28-31, 2001
• 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: Dov Harel , Robert Endre Tarjan, Fast algorithms for finding nearest common ancestors, SIAM Journal on Computing, v.13 n.2, p.338-355, May 1984 [doi>10.1137/0213024]
• 16: Jotun Hein , Tao Jiang , Lusheng Wang , Kaizhong Zhang, On the complexity of comparing evolutionary trees, Discrete Applied Mathematics, v.71 n.1-3, p.153-169, Dec. 5, 1996 [doi>10.1016/S0166-218X(96)00062-5]
• 17: Ming-Yang Kao , Tak Wah Lam , Wing-Kin Sung , Hing-Fung Ting, A Decomposition Theorem for Maximum Weight Bipartite Matchings with Applications to Evolutionary Trees, Proceedings of the 7th Annual European Symposium on Algorithms, p.438-449, July 16-18, 1999
• 18: Ming-Yang Kao , Tak-Wah Lam , Wing-Kin Sung , Hing-Fung Ting, An even faster and more unifying algorithm for comparing trees via unbalanced bipartite matchings, Journal of Algorithms, v.40 n.2, p.212-233, August 2001 [doi>10.1006/jagm.2001.1163]
• 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: Mike Steel , Tandy Warnow, Kaikoura tree theorems: computing the maximum agreement subtree, Information Processing Letters, v.48 n.2, p.77-82, Nov. 8, 1993 [doi>10.1016/0020-0190(93)90181-8]

INDEX TERMS

Primary Classification:
  G. Mathematics of Computing
  G.1 NUMERICAL ANALYSIS
      G.1.2 Approximation

Additional Classification:
  G. Mathematics of Computing
  G.2 DISCRETE MATHEMATICS
      G.2.1 Combinatorics
          Subjects: Combinatorial algorithms
      G.2.2 Graph Theory
          Subjects: Trees
      G.2.3 Applications

General Terms:
Algorithms

Keywords:
Approximation algorithm, maximum agreement subtree, maximum compatible subtree, phylogenetic tree