Fast comparison of evolutionary trees

Martin Farach-Colton, Mikkel Thorup

Research output: Chapter in Book/Report/Conference proceedingConference contribution

42 Scopus citations

Abstract

Constructing evolutionary trees for species sets is a fundamental problem in biology. Unfortunately, there is no single agreed upon method for this task, and many methods are in use. Current practice dictates that trees be constructed using different methods and that the resulting trees then be compared for consensus. It has become necessary to automate this process as the number of species under consideration has grown. We study the Unrooted Maximum Agreement Subtree Problem (UMAST) and its rooted variant (RMAST). The UMAST problem is as follows: given a set A and two trees T0 and T1 leaf-labeled by the elements of A, find a maximum cardinality subset B of A such that the restrictions of T0 and T1 to B are topologically isomorphic. Our main result is an O(n2+o(1)) time algorithm for the UMAST problem. As a side-effect we will derive an O(n2) time algorithm for the RMAST problem. The previous best algorithm for both these problems has running time O(n4.5+o(1)).

Original languageEnglish (US)
Title of host publicationProceedings of the Annual ACM SIAM Symposium on Discrete Algorithms
PublisherPubl by ACM
Pages481-488
Number of pages8
ISBN (Print)0898713293
StatePublished - Jan 1 1994
Externally publishedYes
EventProceedings of the Fifth Annual SIAM Symposium on Discrete Algorithms - Arlington, VA, USA
Duration: Jan 23 1994Jan 25 1994

Other

OtherProceedings of the Fifth Annual SIAM Symposium on Discrete Algorithms
CityArlington, VA, USA
Period1/23/941/25/94

All Science Journal Classification (ASJC) codes

  • Software
  • Mathematics(all)

Fingerprint Dive into the research topics of 'Fast comparison of evolutionary trees'. Together they form a unique fingerprint.

  • Cite this

    Farach-Colton, M., & Thorup, M. (1994). Fast comparison of evolutionary trees. In Proceedings of the Annual ACM SIAM Symposium on Discrete Algorithms (pp. 481-488). Publ by ACM.