Optimal evolutionary tree comparison by sparse dynamic programming

Martin Farach, Mikkel Thorup

Research output: Contribution to journalConference articlepeer-review

31 Scopus citations

Abstract

In computational biology one is often interested in finding the concensus between different evolutionary trees for the same set of species. A popular formalizations is the Maximum Agreement Subtree Problem (MAST) defined as follows: given a set A and two rooted trees T0 and T1 leaf-labeled by the elements of A, find a maximum cardinality subset B ofA such that the restrictions of T0 and T1 to B are topologically isomorphic. Polynomial time solutions exist, but they rely on a dynamic program with Θ(n2) nodes-and Θ(n2) running time. We sparsify this dynamic program and show that MAST is equivalent to Unary Weighted Bipartite Matching (UWBM) modulo an O(nc logn) additive overhead. Applying the best bound for UWBM, we get an O(n1. 5logn) algorithm for MAST. From our sparsification follows an O(nc logn) time algorithm for the special case of bounded degrees. Also here the best previous bound was Θ(n2).

Original languageEnglish (US)
Pages (from-to)770-779
Number of pages10
JournalProceedings - Annual IEEE Symposium on Foundations of Computer Science, FOCS
DOIs
StatePublished - 1994
Externally publishedYes
EventProceedings of the 35th IEEE Annual Symposium on Foundations of Computer Science - Santa Fe, NM, USA
Duration: Nov 20 1994Nov 22 1994

All Science Journal Classification (ASJC) codes

  • Computer Science(all)

Fingerprint

Dive into the research topics of 'Optimal evolutionary tree comparison by sparse dynamic programming'. Together they form a unique fingerprint.

Cite this