This Article Full Text (PDF) Alert me when this article is cited Alert me if a correction is posted Services Email this article to a friend Similar articles in this journal Alert me to new issues of the journal Download to citation manager Google Scholar Articles by Catanzaro, D. Articles by Labbé, M.

A Class Representative Model for Pure Parsimony Haplotyping

Graphs and Mathematical Optimization, Computer Science Department, Université Libre de Bruxelles, B-1050 Brussels, Belgium
Istituto di Analisi dei Sistemi ed Informatica, Consiglio Nazionale delle Ricerche, 00185 Roma Italy
Graphs and Mathematical Optimization, Computer Science Department, Université Libre de Bruxelles, B-1050 Brussels, Belgium
dacatanz{at}ulb.ac.be
alessandragodi{at}inwind.it
mlabbe{at}ulb.ac.be

Haplotyping estimation from aligned single nucleotide polymorphism fragments has attracted increasing attention in recent years because of its importance in the analysis of fine-scale genetic data. Its application fields range from mapping of complex disease genes to inferring population histories, passing through designing drugs, functional genomics, and pharmacogenetics. The literature proposes several criteria for haplotyping populations, each of them characterized by biological motivations. One of the most important haplotyping criteria is parsimony, which consists of finding the minimum number of haplotypes necessary to explain a given set of genotypes. Parsimonious haplotype estimation is an -hard problem for which the literature has proposed several integer programming (IP) models. Here, we describe a new polynomial-sized IP model based on the concept of class representatives, already used for the coloring problem. We propose valid inequalities to strengthen our model and show, through computational experiments, that our model outperforms the best IP models currently known in literature.

Key words: haplotype inference; computational biology; integer programming
History: received October 2008; revised March 2009; accepted March 2009.