The haplotype inference (HI) problem is the problem of inferring 2n haplotype pairs from n observed genotype vectors. This is a key problem that arises in studying genetic variation in populations, for example in
the ongoing HapMap project [5]. In order to have a hope of finding the haplotypes that actually generated the observed genotypes,
we must use some (implicit or explicit) genetic model of the evolution of the underlying haplotypes. The Perfect Phylogeny
Haplotyping (PPH) model was introduced in 2002 [9] to reflect the “neutral coalescent” or “perfect phylogeny” model of haplotype
evolution. The PPH problem (which can be solved in polynomial time) is to determine whether there is an HI solution where
the inferred haplotypes can be derived on a perfect phylogeny (tree).
Since the introduction of the PPH model, several extensions and modifications of the PPH model have been examined. The most
important modification, to model biological reality better, is to allow a limited number of biological events that violate the perfect phylogeny model. This was accomplished implicitly in [7,12] with the
inclusion of several heuristics into an algorithm for the PPH problem [8]. Those heuristics are invoked when the genotype
data cannot be explained with haplotypes that fit the perfect phylogeny model. In this paper, we address the issue explicitly, by allowing one recombination or homoplasy event in the model of haplotype evolution. We formalize the problems and provide
a polynomial time solution for one problem, using an additional, empirically-supported assumption. We present a related framework
for the second problem which gives a practical algorithm. We believe the second problem can be solved in polynomial time.
Research partially supported by grant EIA-0220154 from the National Science Foundation.