TREE COMPATIBILITY AND INFERRING EVOLUTIONARY HISTORY

The tree compatibility problem is a problem concerned with evolutionar y history construction. For a species set S, an S-labelled tree is a t ree T along with a labelling L: S --> V(T). The tree compatibility pro blem asks whether a set T of S-labelled trees, each of which describes the evolution of S, is compatible in the sense that there is a single tree T from which each tree T is-an-element-of T can be derived by a sequence of edge contractions. Polynomial time algorithms for the tre e compatibility problem have been known to exist for a long time, with the best being the recent O(n2k) algorithm by Gusfield to determine c ompatibility of k trees on n species. Recently Gusfield found an O(nk) algorithm for a restricted case of the tree compatibility problem. In this paper, we will present an O(nk) algorithm for the tree compatibi lity problem, thus achieving linear time. The perfect phylogeny proble m is another problem in evolutionary history construction, which has b een recently shown to be in P for special cases but NP-complete for th e general case. We will show that we can characterize each instance to the perfect phylogeny problem as an instance to the tree compatibilit y problem, and thus derive an algorithm for the perfect phylogeny prob lem. Our algorithm is superior to the other algorithms for perfect phy logeny problem for many realistic cases, such as when the species are defined by molecular data such as amino-acid sequences. (C) 1994 Acade mic Press, Inc.