Haplotype Inference by Pure Parsimony: A Survey
Haplotype Inference by Pure Parsimony: A Survey
复制标题
纯粹简约的单倍型推断：一项调查
DOI：
10.1089/cmb.2009.0101
复制
发表时间：
2010
期刊：
影响因子：
--
通讯作者：
Arlindo L. Oliveira
中科院分区：
文献类型：
--
作者：
Ana Graça;I. Lynce;Joao Marques;Arlindo L. Oliveira
给定一个群体的一组基因型，恢复解释基因型的单倍型的过程称为单倍型推断。纯简约性假设下的单倍型推断问题在于找到解释给定基因型集合的最小单倍型数目。这个问题是NP难的。纯简约单倍型推断（HIPP）问题的原始解决方案是基于整数线性规划和分枝定界技术。最近，基于布尔可满足性，伪布尔优化和答案集编程的解决方案已经被证明是非常有效的。HIPP是一种可行的单倍型推断方法，可以与其他方法相竞争。本文概述了解决HIPP问题的方法，包括预处理、边界技术和启发式方法。本文还提出了一个实证评估的准确HIPP解决方案的综合和真实的问题的例子。此外，边界技术的确切问题进行评估。最后一节比较和讨论了HIPP方法与一个成熟的统计方法，代表了这个问题的参考算法。
Given a set of genotypes from a population, the process of recovering the haplotypes that explain the genotypes is called haplotype inference. The haplotype inference problem under the assumption of pure parsimony consists in finding the smallest number of haplotypes that explain a given set of genotypes. This problem is NP-hard. The original formulations for solving the Haplotype Inference by Pure Parsimony (HIPP) problem were based on integer linear programming and branch-and-bound techniques. More recently, solutions based on Boolean satisfiability, pseudo-Boolean optimization, and answer set programming have been shown to be remarkably more efficient. HIPP can now be regarded as a feasible approach for haplotype inference, which can be competitive with other different approaches. This article provides an overview of the methods for solving the HIPP problem, including preprocessing, bounding techniques, and heuristic approaches. The article also presents an empirical evaluation of exact HIPP solvers on a comprehensive set of synthetic and real problem instances. Moreover, the bounding techniques to the exact problem are evaluated. The final section compares and discusses the HIPP approach with a well-established statistical method that represents the reference algorithm for this problem.
登录
查看更多内容
影响因子：
10.7
作者：
A. Clark
通讯作者：
A. Clark
DOI：
10.1097/00008571-200308000-00006
发表时间：
2003-08-01
期刊：
PHARMACOGENETICS
影响因子：
--
作者：
Kroetz, DL;Pauli-Magnus, C;Clark, AG
通讯作者：
Clark, AG
影响因子：
56.9
作者：
KEREM, BS;ROMMENS, JM;TSUI, LC
通讯作者：
TSUI, LC
影响因子：
9.8
作者：
Marchini, J;Cutler, D;Donnelly, P
通讯作者：
Donnelly, P
DOI：
10.1073/pnas.97.19.10483
发表时间：
2000-09-12
影响因子：
11.1
作者：
Drysdale, CM;McGraw, DW;Liggett, SB
通讯作者：
Liggett, SB