Fast Compatibility Testing for Rooted Phylogenetic Trees

Abstract

We present a new graph-based approach to the following basic problem in phylogenetic tree construction. Let $\mathcal {P}= \{T_1, \ldots , T_k\}$ be a collection of rooted phylogenetic trees over various subsets of a set of species. The tree compatibility problem asks whether there is a phylogenetic tree T with the following property: for each $i \in \{1, \dots , k\}$, $T_i$ can be obtained from the restriction of T to the species set of $T_i$ by contracting zero or more edges. If such a tree T exists, we say that $\mathcal {P}$ is compatible and that T displays $\mathcal {P}$. Our approach leads to a $O(M_\mathcal {P}\log ^2 M_\mathcal {P})$ algorithm for the tree compatibility problem, where $M_\mathcal {P}$ is the total number of nodes and edges in $\mathcal {P}$. Our algorithm either returns a tree that displays $\mathcal {P}$ or reports that $\mathcal {P}$ is incompatible. Unlike previous algorithms, the running time of our method does not depend on the degrees of the nodes in the input trees. Thus, our algorithm is equally fast on highly resolved and highly unresolved trees.