  In this paper we present a collection of results pertaining to haplotyping.
The first set of results concerns the combinatorial problem of reconstructing
haplotypes from incomplete and/or imperfectly sequenced haplotype data. More
specifically, we show that an interesting, restricted case of Minimum Error
Correction (MEC) is NP-hard, point out problems in earlier claims about a
related problem, and present a polynomial-time algorithm for the ungapped case
of Longest Haplotype Reconstruction (LHR). Secondly, we present a polynomial
time algorithm for the problem of resolving genotype data using as few
haplotypes as possible (the Pure Parsimony Haplotyping Problem, PPH) where each
genotype has at most two ambiguous positions, thus solving an open problem
posed by Lancia et al in "Haplotyping Populations by Pure Parsimony: Complexity
of Exact and Approximation Algorithms."
