Solving haplotyping inference parsimony problem using a new basic polynomial formulation

Similarity and diversity among individuals of the same species are expressed in small DNA variations called Single Nucleotide Polymorphism. The knowledge of SNP phase gives rise to the haplotyping problem that in the parsimonious version states to infer the minimum number of haplotypes from a given set of genotype data. ILP technique represents a good resolution strategy for this interesting combinatorial problem whose main limit lies in its NP-hardness. In this paper we present a new polynomial model for the haplotyping inference by parsimony problem characterized by the original use of a maximum formulation jointly with a good heuristic solution. This approach showed to be a robust basic model that can be used as starting point for more sophisticated ILP techniques like branch and cut and polyhedral studies. (c) 2007 Elsevier Ltd. All rights reserved.