Parsimonious haplotype estimation from aligned Single Nucleotide Polymorphism (SNP) fragments consists of finding the minimum number of haplotypes necessary to explain a given set of genotypes. This problem is known to be NP-Hard. Here we describe a new integer linear-programming model to tackle this problem based on the concept of class representatives, already used for the coloring problem. The model is characterized by a polynomial number of variables and constraints. We also provide valid inequalities to strengthen our model. Computational experiments show that such model is robust and outperforms the relative ILP models known in literature.
Citation
Technical Reports of the ULB Computer Science Department, Number 580, Brussels, Belgium, August 2007.