A Practical Ezact Algorithm for the Individual Haplotyping Problem MEC/GI
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. For the problem, there has been no practical exact algorithm. In DNA sequencing experiments, due to technical limits, the maximuM length of a fragment sequenced directly is about lkb. In consequence, the maximum number k of SNP sites that a fragment covers is usually small (usually smaller than 10). Based on the observation above, the current paper introduces a new parameterized dynamic programming algorithm of running time O(mk2k + mlogM + ink), where m is the number of fragments. The algorithm solves the MEC/GI problem efficiently even if the number of fragments and SNPs are large, and is practical in real biological applications.
Minzhu Xie Jianxin Wang Jianer Chen
School of Information Science and Engineering, Central South University, Changsha 410083, P.R. China School of Information Science and Engineering, Central South University,Changsha 410083, P.R. China School of Information Science and Engineering, Central South University, Changsha 410083, P.R. China
国际会议
The 4th Annual International Computing and Combinatorics Conference,COCOON 2008(第14届国际计算和组合会议)
大连
英文
342-351
2008-06-01（万方平台首次上网日期，不代表论文的发表时间）