## 3 The papers
### Problem area # 4 : haplotyping
The solving algorithm consists in first transforming the problem into a maximum weighted forest on a suitable auxiliary graph, and then solving this graph problem by integer programming. Max parsimony.Since [PERSON]'s algorithm tries to re-use existing haplotypes and to introduce at most one new haplotype at a time, the solution it tends to produce is usually of small size. The objective of minimizing the size of \(\mathcal{H}\) has several biological motivations. For one, the number of distinct haplotypes observed in nature is vastly smaller than the number of possible haplotypes (we all descend from a small number of ancestors, whose haplotypes, modulo some recombination events and mutations, are the same we possess today). Moreover, under a general parsimony principle (also known as _Okkam's razor_), of many possible explanations of an observed phenomenon, one should favor the simplest. The _pure parsimony_ haplotyping problem requires to find a solving set \(\mathcal{H}\) of smallest possible cardinality. This problem has been introduced by [PERSON]  
* [PERSON] (2003) [ILP]  
who adopted an integer programming formulation, with an exponential number of variables and constraints, for its practical solution. The ILP approach is shown to be applicable to instances of about 50 genotypes over 30 SNPs, with relatively few (about 10) ambiguous positions per genotype. An alternative, polynomial-size, integer programming formulation is proposed in
* [PERSON] and [PERSON] (2004) [ILP]  
The polynomial-size ILP can be used for some instances which are too large for the exponential model. However, the LP-relaxation bound is weak and the solving process can be quite long. A similar polynomial-size formulation is present also in
* [PERSON], [PERSON] and [PERSON] (2004) [LP-APPR]  
where [PERSON]'s exponential model is used to derive an LP-based approximation algorithm, yielding \((2^{k-1})\)-approximate solutions for instances in which each genotype has at most \(k\) ambiguous positions. * [PERSON] and [PERSON] (2006) [ILP,OTH]  
prove that the parsimony problem for instances in which each genotype has at most two ambiguous positions is polynomially solvable. The proof consists in showing that, in this special case, the solution of the ILP is naturally integer. The pure parsimony haplotyping problem has also been formulated as a quadratic problem. * [PERSON] and [PERSON] (2005) [QSDP]  
use semidefinite programming for its solution. Similarly to the exponential IP, the formulation has a variable for each possible haplotype and cannot be used to tackle instances for which the set of possible haplotypes is too large. The size of the problems solved is about the same as for the previous methods. Based on a similar formulation, an (exponential-time) approximation algorithm is presented in
* [PERSON], [PERSON] and [PERSON] (2005) [QSDP]Families and disease association.When collecting genotype data for populations, sometimes extra information are gathered as well. For instance, information about which individuals of the population are related (i.e., belong to the same family). Furthermore, some individuals may be affected by a genetic disease, so that the genotypes can be labeled as healthy and diseased. When these extra data are available, new combinatorial models can be defined for several problems. * [72]: [PERSON], [PERSON], [PERSON] and [PERSON] (2005) [ILP]  
In this paper the set of input genotypes is partitioned into family trios, where each trio is composed by a pair of parents and a child. The goal is that of retrieving haplotypes, so that each trio's genotypes are explained by a quartet of parent/offspring haplotypes. The objectives studied are pure parsimony and missing data recovery. For both problems, the authors propose integer linear programming approaches. The approaches are validated by extensive experiments, showing an advantage in the use of the ILP approach over the previously known methods.