  


A Class Representative Model for Pure Parsimony Haplotyping
Daniele Catanzaro (dacatanzulb.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 NPHard. Here we describe a new integer linearprogramming 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 Modify/Update this entry  
Visitors  Authors  More about us  Links  
Subscribe, Unsubscribe Digest Archive Search, Browse the Repository

Submit Update Policies 
Coordinator's Board Classification Scheme Credits Give us feedback 
Optimization Journals, Sites, Societies  