AbstractThis paper presents an O(n1.75 + o(1)) time algorithm for the Unrooted Maximum Agreement Subtree (MAST) problem: Given a set A of n items (e.g. species) and two unrooted trees T and T', each with n leaves uniquely labeled by the items of A, we want to compute the largest subset B of A such that the subtrees of T and T' induced by B are isomorphic.The UMAST problem is closely related to some problems in biology, in particular, the one of finding the consensus between evolutionary trees (or phylogenies) of a set of species.
Categories and Subject Descriptors: E.1 [Data Structures]; F.2.2 [Analysis of Algorithms and Problem Complexity]: Nonnumerical Algorithms and Problems
Additional Key Words and Phrases: comuptational biology, evolutionary tree, unrooted maximum agreement subtree, tree isomorphism
Selected references
- Richa Agarwala and David Fernándex-Baca. A polynomial-time algorithm for the perfect phylogeny problem when the number of character states is fixed. In 34th Annual Symposium on Foundations of Computer Science, pages 140-147, Palo Alto, California, 3-5 November 1993. IEEE.
- Richard Cole and Ramesh Hariharan. An O(n log n) algorithm for the maximum agreement subtree problem for binary trees. In Proceedings of the Seventh Annual ACM-SIAM Symposium on Discrete Algorithms, pages 323-332, Atlanta, Georgia, 28-30 January 1996.
- Martin Farach and Mikkel Thorup. Fast comparison of evolutionary trees. In Proceedings of the Fifth Annual ACM-SIAM Symposium on Discrete Algorithms, pages 481-488, Arlington, Virginia, 23-25 January 1994.
- Martin Farach and Mikkel Thorup. Optimal evolutionary tree comparison by sparse dynamic programming (extended abstract). In 35th Annual Symposium on Foundations of Computer Science, pages 770-779, Santa Fe, New Mexico, 20-22 November 1994. IEEE.
- Harold N. Gabow and Robert E. Tarjan. Faster scaling algorithms for network problems. SIAM Journal on Computing, 18(5):1013-1036, October 1989.
- John Kececioglu and Dan Gusfield. Reconstructing a history of recombinations from a set of sequences. In Proceedings of the Fifth Annual ACM-SIAM Symposium on Discrete Algorithms, pages 471-480, Arlington, Virginia, 23-25 January 1994.
- Dmitry Keselman and Amihood Amir. Maximum agreement subtree in a set of evolutionary trees -- metrics and efficient algorithms. In 35th Annual Symposium on Foundations of Computer Science, pages 758-769, Santa Fe, New Mexico, 20-22 November 1994. IEEE.