Haplotype inference with pseudo‐Boolean optimization

Haplotype inference with pseudo‐Boolean optimization

0.00 Avg rating0 Votes
Article ID: iaor20112594
Volume: 184
Issue: 1
Start Page Number: 137
End Page Number: 162
Publication Date: Apr 2011
Journal: Annals of Operations Research
Authors: , , ,
Keywords: boolean programming, genetics, NP-hard, Parsimony haplotyping problem
Abstract:

The fast development of sequencing techniques in the recent past has required an urgent development of efficient and accurate haplotype inference tools. Besides being a crucial issue in genetics, haplotype inference is also a challenging computational problem. Among others, pure parsimony is a viable modeling approach to solve the problem of haplotype inference and also an interesting NP‐hard problem in itself. Recently, the introduction of SAT‐based methods, including pseudo‐Boolean optimization (PBO) methods, has produced very efficient solvers. This paper provides a detailed description of RPoly, a PBO approach for the haplotype inference by pure parsimony (HIPP) problem. Moreover, an extensive evaluation of existent HIPP solvers, on a comprehensive set of instances, confirms that RPoly is currently the most efficient and robust HIPP approach.

Reviews

Required fields are marked *. Your email address will not be published.