A Practical Exact Algorithm for the Individual Haplotyping Problem MEC* *This research was supported in part by the National Natural Science Foundation of China under Grant Nos.60433020and 60773111, the Program for New Century Excellent Talents in University No. NCET-050683, the Program for Changjiang Scholars and Innovative Research Team in University No. IRT0661, and the Scientific Research Fund of Hunan Provincial Education Department. Conference Paper uri icon

abstract

  • The individual haplotyping problem MEC is a computational problem that, given a set of DNA sequence fragment data of an individual, induces the corresponding haplotypes by changing the smallest number of SNPs. MEC problem is NP-hard and there has been no practical exact algorithm to solve the problem. 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. Based on the observation above, the current paper introduces a new parameterized algorithm of running time O(mk3k + mlogm + mk), where m is the number of fragments. The algorithm solves the MEC problem efficiently even if the number of fragments and SNPs are large, and is practical in real biological applications. 2008 IEEE.

name of conference

  • 2008 International Conference on BioMedical Engineering and Informatics

published proceedings

  • 2008 International Conference on BioMedical Engineering and Informatics

author list (cited authors)

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

citation count

  • 2

complete list of authors

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

publication date

  • May 2008