A Practical Exact Algorithm for the Individual Haplotyping Problem MEC/GI
A Practical Exact Algorithm for the Individual Haplotyping Problem MEC/GI
复制标题
DOI：
10.1007/s00453-009-9288-1
复制
发表时间：
2008-05
期刊：
影响因子：
1.1
通讯作者：
Jian-xin Wang;Minzhu Xie;Jianer Chen
中科院分区：
文献类型：
--
作者：
Jian-xin Wang;Minzhu Xie;Jianer Chen
单倍型在复杂疾病的遗传关联研究中起着重要作用。最近，计算机技术帮助确定人类单倍型进行了广泛的研究。给定个体的基因型和比对的单核苷酸多态性（SNP）片段，利用基因型信息的最小误差校正（MEC/GI）是通过校正给定SNP片段中的最小数目的SNP来推断与基因型相容的单倍型对的重要计算模型。MEC/GI问题已被证明是NP难的，没有实际的精确算法。尽管分子生物学技术发展迅速，但现代高通量测序仪不能直接测序含有超过1200个核苷酸碱基的DNA片段。在低SNP密度的情况下，现有的数据显示，一个DNA片段覆盖的SNP位点的数量通常小于10。在此基础上，我们提出了一个新的动态规划算法，其运行时间为O（mk ~ 2k +mlogm+ n），其中n为分段数。由于该算法在真实的生物学应用中规模较小，因此具有实用性和高效性.
Haplotypes play an important role in genetic association studies of complex diseases. Recently, computational techniques helping to determine human haplotypes were studied extensively. Given the genotype and the aligned single nucleotide polymorphism (SNP) fragments of an individual,Minimum Error Correction with Genotype Information(MEC/GI) is an important computational model to infer a pair of haplotypes compatible with the genotype by correcting minimum number of SNPs in the given SNP fragments. The MEC/GI problem has been proven NP-hard, for which there is no practical exact algorithm. Despite the rapid advances in molecular biological techniques, modern high-throughput sequencers cannot sequence directly a DNA fragment that contains more than 1200 nucleotide bases. With low SNP density, current available data reveal that the numberkof SNP sites that a DNA fragment covers is usually smaller than 10. Based on the above fact, we develop a new dynamic programming algorithm with running timeO(mk2k+mlogm+mk), wheremis the number of fragments. Sincekis small in real biological applications, the algorithm is practical and efficient.