Generalizing the Splits Equivalence Theorem and Four Gamete Condition: Perfect Phylogeny on Three-State Characters

Abstract

We study the three-state perfect phylogeny problem and show that there is a three-state perfect phylogeny for a set of input sequences if and only if there is a perfect phylogeny for every subset of three characters. In establishing these results, we prove fundamental structural features of the perfect phylogeny problem on three-state characters and completely characterize the minimal obstruction sets that must occur in input sequences that do not have a perfect phylogeny. We also give a proof for a stated lower bound involved in the conjectured generalization of our main result to any number of states.