AbstractThis paper presents an O(n

^{1.75 + o(1)}) time algorithm for the Unrooted Maximum Agreement Subtree (MAST) problem: Given a setAofnitems (e.g. species) and two unrooted treesTandT', each withnleaves uniquely labeled by the items ofA, we want to compute the largest subsetBofAsuch that the subtrees ofTandT'induced byBare 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(nlogn) 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.