title: A class representative model for Pure Parsimony Haplotyping under uncertain data.
abstract: The Pure Parsimony Haplotyping (PPH) problem is a NP-hard combinatorial optimization problem that consists of finding the minimum number of haplotypes necessary to explain a given set of genotypes. PPH has attracted more and more attention in recent years due to its importance in analysis of many fine-scale genetic data. Its application fields range from mapping complex disease genes to inferring population histories, passing through designing drugs, functional genomics and pharmacogenetics. In this article we investigate, for the first time, a recent version of PPH called the Pure Parsimony Haplotype problem under Uncertain Data (PPH-UD). This version mainly arises when the input genotypes are not accurate, i.e., when some single nucleotide polymorphisms are missing or affected by errors. We propose an exact approach to solution of PPH-UD based on an extended version of Catanzaro et al.[1] class representative model for PPH, currently the state-of-the-art integer programming model for PPH. The model is efficient, accurate, compact, polynomial-sized, easy to implement, solvable with any solver for mixed integer programming, and usable in all those cases for which the parsimony criterion is well suited for haplotype estimation.
authors.affiliation: Graphes et Optimisation Mathématique, Computer Science Department, Université Libre de Bruxelles, CP 210/01 Brussels, Belgium. dacatanz@ulb.ac.be
authors.forename: Daniele
authors.initials: D
authors.lastname: Catanzaro
authors.forename: Martine
authors.initials: M
authors.lastname: Labbé
authors.forename: Luciano
authors.initials: L
authors.lastname: Porretta
mesh_terms: D030541:Databases, Genetic; D006239:Haplotypes / Q000235:genetics*; D006801:Humans; D008957:Models, Genetic; D035501:Uncertainty