A Class Representative Model for Pure Parsimony Haplotyping

Daniele Catanzaro (dacatanzulb.ac.be)
Alessandra Godi (godiapollo.iasi.rm.cnr.it)
Martine Labbé (mlabbeulb.ac.be)

Abstract: 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.

Keywords: haplotyping under parsimony, polynomial models, integer linear programming.

Category 1: Integer Programming ((Mixed) Integer Linear Programming )

Category 2: Applications -- Science and Engineering (Basic Sciences Applications )

Citation: Technical Reports of the ULB Computer Science Department, Number 580, Brussels, Belgium, August 2007.

Download: [PDF]

Entry Submitted: 01/10/2008
Entry Accepted: 01/10/2008
Entry Last Modified: 06/05/2008

Modify/Update this entry