A FAST ALGORITHM FOR THE COMPUTATION AND ENUMERATION OF PERFECT PHYLOGENIES

The perfect phylogeny problem is a classical problem in computational evolutionary biology, in which a set of species/taxa is described by a set of qualitative characters. In recent years, the problem has been shown to be NP-complete in general, while the different fixed paramete r versions can each be solved in polynomial time. In particular, Agarw ala and Fernandez-Baca have developed an O(2(3r)(nk(3) + k(4))) algori thm for the perfect phylogeny problem for n species defined by k r-sta te characters [SIAM J. Comput., 23 (1994), pp. 1216-1224]. Since, comm only, the character data are drawn from alignments of molecular sequen ces, k is the length of the sequences and can thus be very large (in t he hundreds or thousands). Thus, it is imperative to develop algorithm s which run efficiently for large values of k. In this paper we make a dditional observations about the structure of the problem and produce an algorithm for the problem that runs in time O(2(2r)k(2)n). We also show how it is possible to efficiently build a structure that implicit ly represents the set of all perfect phylogenies and to randomly sampl e from that set.