The undirected incomplete perfect phylogeny problem

The incomplete perfect phylogeny (IPP) problem and the incomplete perfect phylogenyhaplotyping (IPPH) problemdeal with constructing a phylogeny for a given set of haplotypes or genotypes with missing entries. The earlier approaches for both these problems dealt with restricted versions of the problem, where the root is either available or can be trivially re-constructed from the data, or certain assumptions were made about the data. In this paper, we deal with the unrestricted ver-sion of the problem, where the root of the phylogeny is neither available nor trivially recoverable from the data. The conditions underwhich a set of incomplete haplotypesadmit a unique per-fect phylogeny has remained an open problem. We solve this open problem and state a set of necessary and sufficient con-ditions for a given set of incomplete haplotypes or genotypes to admit a perfect phylogeny. Both IPP and IPPH problems have previously been proven to be NP-complete. Here, we present efficient algorithms that can handle practical instances of the problem. Empirical analysis on simulated data shows that the algorithms take less than a second on data involving as many as hundred SNP loci. An implementation of our method will be made available online shortly. Contact