A Practical Exact Algorithm for the Individual Haplotyping Problem MEC/GI Conference Paper uri icon

abstract

  • 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 1kb. 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 + mk), 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. 2008 Springer-Verlag Berlin Heidelberg.

name of conference

  • Computing and Combinatorics, 14th Annual International Conference, COCOON 2008, Dalian, China, June 27-29, 2008, Proceedings

published proceedings

  • Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

author list (cited authors)

  • Xie, M., Wang, J., & Chen, J.

citation count

  • 0

complete list of authors

  • Xie, Minzhu||Wang, Jianxin||Chen, Jianer

publication date

  • August 2008