RPOLY
Haplotype inference with pseudo-Boolean optimization. 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.
(Source: http://plato.asu.edu)
Keywords for this software
References in zbMATH (referenced in 10 articles )
Showing results 1 to 10 of 10.
Sorted by year (- Cai, Shaowei; Luo, Chuan; Lin, Jinkun; Su, Kaile: New local search methods for partial MaxSAT (2016)
- Gebser, Martin; Janhunen, Tomi; Kaminski, Roland; Schaub, Torsten; Tasharrofi, Shahab: Writing declarative specifications for clauses (2016)
- Jäger, Gerold; Climer, Sharlee; Zhang, Weixiong: The complete parsimony haplotype inference problem and algorithms based on integer programming, branch-and-bound and Boolean satisfiability (2016)
- Lancia, Giuseppe: Mathematical models and solutions for the analysis of human genotypes (2014)
- Morgado, Antonio; Heras, Federico; Liffiton, Mark; Planes, Jordi; Marques-Silva, Joao: Iterative and core-guided maxsat solving: a survey and assessment (2013)
- Graça, Ana; Marques-Silva, João; Lynce, Inês; Oliveira, Arlindo L.: Haplotype inference with pseudo-Boolean optimization (2011)
- Wang, I-Lin; Chang, Chia-Yuan: Mathematical properties and bounds on haplotyping populations by pure parsimony (2011)
- Wang, I-Lin; Yang, Hui-E: Haplotyping populations by pure parsimony based on compatible genotypes and greedy heuristics (2011)
- Catanzaro, Daniele; Labbé, Martine: The pure parsimony haplotyping problem: overview and computational advances (2009)
- Graça, Ana; Marques-Silva, João; Lynce, Inês; Oliveira, Arlindo L.: Efficient haplotype inference with pseudo-Boolean optimization (2007)