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 runningtime O(m k 3^{k}+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.
Index Terms:
SNP (single-nucleotide polymorphism), haplotype, MEC (Minimum Error Correction), NP-hardness
Citation:
Minzhu Xie, Jianxin Wang, Jianer Chen, "A Practical Exact Algorithm for the Individual Haplotyping Problem MEC," bmei, vol. 1, pp.72-76, 2008 International Conference on BioMedical Engineering and Informatics, 2008