## 3 The papers
### Problem area # 4 : haplotyping  
Notation.Given a set of \(n\) SNPs, fix a binary encoding of the two alleles for each SNP (e.g., call \"0\" the least frequent allele and \"1\" the most frequent allele). With this encoding, each haplotype corresponds to binary vector of length \(n\). Given two haplotypes \(h^{\prime}\) and \(h^{\prime\prime}\), define their sum as a vector \(g:=h^{\prime}\oplus h^{\prime\prime}\), of length \(n\), and with components in \(\{0,1,2\}\). The vector \(g\) is called a genotype, and its components are defined as follows:  
\[g[i]:= \begin{cases}0&\text{if }h^{\prime}[i]=h^{\prime\prime}[i]=0\\ 1&\text{if }h^{\prime}[i]=h^{\prime\prime}[i]=1\\ 2&\text{if }h^{\prime}[i]\
eq h^{\prime\prime}[i].\end{cases} \]  
Each position \(i\) such that \(g[i]=2\) is called an _ambiguous position_. Genotype entries of value 0 or 1 correspond to homozygous SNP sites, while entries of value 2 correspond to heterozygous sites. In Fig. 6 we illustrate a case of three individuals, showing their haplotypes and genotypes. A _resolution_ of a genotype \(g\) is a pair of haplotypes \(h^{\prime}\) and \(h^{\prime\prime}\) such that \(g=h^{\prime}\oplus h^{\prime\prime}\). The haplotypes \(h^{\prime}\) and \(h^{\prime\prime}\) are said to resolve \(g\). A genotype is _ambiguous_ if it has more than one possible resolution, i.e., if it has at least two ambiguous positions. A haplotype \(h\) is said to be _compatible_ with a genotype \(g\) if \(h\) can be used in a resolution of \(g\). Two genotypes \(g\) and \(g^{\prime}\) are compatible if there exists at least one haplotype compatible with both of them, otherwise, they are _incompatible_. For the haplotyping problems described in this section, the input data consist in a set \(\mathcal{G}\) of \(m\) genotypes \(g_{1},\ldots,g_{m}\), corresponding to \(m\) individuals in a population. The output is set \(\mathcal{H}\) of haplotypes such that, for each \(g\in\mathcal{G}\), there is at least one pair of haplotypes \(h^{\prime},h^{\prime\prime}\in\mathcal{H}\) with \(g=h^{\prime}\oplus h^{\prime\prime}\). The set \(\mathcal{H}\) of is said to explain \(\mathcal{G}\). [PERSON]'s rule.The first haplotyping problem studied was related to the optimization of _[PERSON]'s inference rule_ (IR). The rule, proposed by the geneticist [PERSON] [64], can be used to resolve a genotype \(g\) whenever a haplotype \(h\) compatible with \(g\) is known. The rule derives new haplotypes by inference from known ones as follows:  
* Given a genotype \(g\) and a compatible haplotype \(h\), obtain a new haplotype \(q\) by setting \(q[j]:=1-h[j]\) at each ambiguous position \(j\) and \(q[j]:=h[j]\) at the remaining positions. Then \(h\) and \(q\) resolve \(g\). In order to resolve all genotypes, [PERSON] suggested the use of successive applications of the inference rule, starting from a \"bootstrap\" set of known available haplotypes. In essence, [PERSON] proposed the following algorithm: (i) take an unsolved genotype \(g\) and an available compatible haplotype \(h\); (ii) derive \(q\) by inference, and solve \(g\) as \(h\oplus q\); (iii) declare \(g\) solved and \(q\) available. If there are still unsolved genotypes go to (i). If at the end all genotypes have been solved, the algorithm _succeeds_, otherwise, it _fails_ (this happens if in step (i) there are no compatible available haplotypes for an unsolved genotype). Notice that the procedure, as outlined, is nondeterministic since it does not specify how to choose the pair \((g,h)\) whenever there are more candidates to the application of the rule. It can be shown that, because of this vagueness, there may be two runs of the algorithm on the same data such as one run succeeds while the other fails. Figure 6: Haplotypes and corresponding genotypes. * [65] [PERSON] (2001) [RED,ILP]  
studies the problem of finding an optimal order of application of [PERSON]'s rule. The objective is that of leaving the fewest number of unsolved genotypes in the end. The problem is proved to be APX-hard.