## DIMACS TR: 93-46

## Fast Comparison of Evolutionary Trees

### Authors: Martin Farach and Mikkel Thorup

**
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
$T_0$ and $T_1$ leaf-labeled by the elements of $A$, find a maximum
cardinality subset $B$ of $A$ such that the restrictions of $T_0$ and
$T_1$ to $B$ are topologically isomorphic. Our main result is an
$O(n^{2+o(1)})$ time algorithm for the UMAST problem. As a
side-effect we will derive an $O(n^2)$ time algorithm for the RMAST
problem. The previous best algorithm for both these problems has
running time $O(n^{4.5+o(1)})$.

Paper available at:
ftp://dimacs.rutgers.edu/pub/dimacs/TechnicalReports/TechReports/1993/93-46.ps

DIMACS Home Page