SAT in Bioinformatics: Making the Case with Haplotype Inference
SAT in Bioinformatics: Making the Case with Haplotype Inference
复制标题
生物信息学 SAT：利用单倍型推断进行论证
DOI：
--
复制
发表时间：
2006
期刊：
影响因子：
--
通讯作者：
Joao Marques
中科院分区：
文献类型：
--
作者：
I. Lynce;Joao Marques
DNA突变是人类差异的主要原因，而单核苷酸多态性（SNP）是最常见的突变。因此，一项基本任务是完成人群中的单倍型图谱（识别 SNP）。与这项工作相关的一个关键计算问题是从基因型数据推断单倍型数据，因为在实践中通常获得的是基因型数据而不是单倍型数据。最近的工作表明，基于 SAT 的方法是迄今为止解决纯简约单倍型推断 (HIPP) 问题最有效的解决方案，比现有的整数线性规划和分支定界解决方案快几个数量级。本文对原有的基于 SAT 的模型提出了一些关键的优化。新版本的模型比原来基于 SAT 的 HIPP 模型快几个数量级，特别是在生物测试数据上。
Mutation in DNA is the principal cause for differences among human beings, and Single Nucleotide Polymorphisms (SNPs) are the most common mutations. Hence, a fundamental task is to complete a map of haplotypes (which identify SNPs) in the human population. Associated with this effort, a key computational problem is the inference of haplotype data from genotype data, since in practice genotype data rather than haplotype data is usually obtained. Recent work has shown that a SAT-based approach is by far the most efficient solution to the problem of haplotype inference by pure parsimony (HIPP), being several orders of magnitude faster than existing integer linear programming and branch and bound solutions. This paper proposes a number of key optimizations to the the original SAT-based model. The new version of the model can be orders of magnitude faster than the original SAT-based HIPP model, particularly on biological test data.