Abstract (Teresa M. Przytycka)
The Maximum Agreement Subtree arises in biology as a measure of consistency
between two evolutionary trees. An evolutionary tree for a species set A is a
rooted tree in which the leaves are uniquely labeled by the species in A, and
the internal nodes represent ancestors. There are many methods for computing
evolutionary tree. Not surprisingly, these various methods do not always give
the same answer on the same inputs. Given that there is no "gold standard"
for constructing evolutionary trees, current practice dictates that several
different methods be applied to the data. The resulting trees are then
compared in order to arrive at some consensus. One technique for obtaining
such a consensus is to compute the so-called Maximum Agreement Subtree (MAST).
It is known that the MAST problem for two trees of unbounded degree is
computationally equivalent to unary weighted bipartite matching and for 3 or
more unbounded degree trees is NP-complete. We show that in the case of two
binary trees the MAST problem can be solved in O(n log^3(n)) time (O(n sqrt(d)
log^3(n)) if the degree bound is d) and for k trees of degree bounded by d in
O(k n^3+n^d) time.
Joint work with: Martin Farach, Rutgers University and Mikkel Thorup,
Copenhagen University.
Last modified: March 8, 1995.
Kim Skak Larsen
(kslarsen@imada.sdu.dk)