**Compatibility Testing for Rooted Phylogenetic Trees**

The tree compatibility problem is a basic special case of the supertree problem. A supertree method is a way to synthesize a collection of phylogenetic trees with partially overlapping taxon sets into a single supertree that represents the information in the input trees. The supertree approach has been used successfully to build large-scale phylogenies.

We present a new graph-based approach to the following basic problem in phylogenetic tree construction. Let P = {T1 , . . . , Tk } 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 ∈ {1, . . . , k}, Ti can be obtained from the restriction of T to the species set of Ti by contracting zero or more edges. If such a tree T exists, we say that P is compatible and that T displays P. Our approach leads to a O(MP log2 MP ) algorithm for the tree compatibility problem, where MP is the total number of nodes and edges in P. Our algorithm either returns a tree that displays P or reports that P is incompatible.

A more general version of the problem is called ancestral compatibility problem with semi-labeled trees. Semi-labeled trees are phylogenies whose internal nodes may be labeled by higher-order taxa. Suppose we are given collection P of semi- labeled trees over various subsets of a set of taxa. The ancestral compatibility problem asks whether there is a semi-labeled tree T that respects the clustering and the ancestor/descendant relationships implied by the trees in P. We give a same running time algorithm for the ancestral compatibility problem. Unlike the best previous algorithm, 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.

**Committee: **David Fernandez-Baca (major professor), Oliver Eulenstein, Xiaoqiu Huang, Ryan Martin, Wensheng Zhang