Haplotyping Populations: Complexity and Approximations

We study the computational complexity of the following haplotyping problem. Given a set of genotypes G, find a minimum cardinality set of haplotypes which explains G. Here, a genotype g is an n-ary string over the alphabet {A,B,-} and an haplotype h is an n-ary string over the alphabet {A,B}. A set of haplotypes H is said to explain G if for every g in G there are h_1, h_2 in H such that h_1 + h_2 = g. The position-wise sum h_1 + h_2 indicates the genotype which has a '-' in the positions where h_1 and h_2 disagree, and the same value as h_1 and h_2 where they agree. We show the APX-hardness of the problem even in the case the number of '-' symbols is at most 3 for every g in G. We give a $\sqrt{|G|}$-approximation algorithm for the general case, and a $2^{k-1}$-approximation algorithm when the number of '-' symbols is at most k for every g in G.