Optimal evolutionary tree comparison by sparse dynamic programming

Martin Farach, Mikkel Thorup

    Research output: Contribution to journalConference articlepeer-review


    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
    StatePublished - 1994
    EventProceedings of the 35th IEEE Annual Symposium on Foundations of Computer Science - Santa Fe, NM, USA
    Duration: Nov 20 1994Nov 22 1994

    ASJC Scopus subject areas

    • General Computer Science


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

    Cite this