Sparse dynamic programming for evolutionary-tree comparison

Martin Farach, Mikkel Thorup

    Research output: Contribution to journalReview articlepeer-review


    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 should be compared for consensus. It has become necessary to automate this process as the number of species under consideration has grown. We study one formalisation of the problem: the maximum agreement-subtree (MAST) problem. The MAST problem is 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 of A such that the topological restrictions of T0 and T1 to B are isomorphic. In this paper, we will show that this problem reduces to unary weighted bipartite matching (UWBM) with an O(n1+o(1)) additive overhead. We also show that UWBM reduces linearly to MAST. Thus our algorithm is optimal unless UWBM can be solved in near linear time. The overall running time of our algorithm is O(n1.5 log n), improving on the previous best algorithm, which runs in O(n2). We also derive an O(nc√log n)-time algorithm for the case of bounded degrees, whereas the previously best algorithm runs in O(n2), as in the unbounded case.

    Original languageEnglish (US)
    Pages (from-to)210-230
    Number of pages21
    JournalSIAM Journal on Computing
    Issue number1
    StatePublished - Feb 1997


    • Computational biology
    • Evolutionary trees
    • Sparse dynamic programming

    ASJC Scopus subject areas

    • General Computer Science
    • General Mathematics


    Dive into the research topics of 'Sparse dynamic programming for evolutionary-tree comparison'. Together they form a unique fingerprint.

    Cite this