A Mixed Integer Programming Model for the Parsimonious Loss of Heterozygosity Problem

We investigate the Parsimonious Loss of Heterozygosity Problem (PLOHP) , i.e., the problem of partitioning suspected polymorphisms of a set of individuals into the minimum number of deletion areas. We generalize the work of Halldorsson et al. ' by showing how one can incorporate prior knowledge about the location of deletion; we prove the general $\mathcal{NP}$ -hardness of the problem and we provide a state-of-the-art mixed integer programming formulation and a number of possible strengthening valid inequalities able to exactly solve practical instances of the PLHOP containing up to 9.000 individuals and 3000 SNPs within 12 hours compute time.