A Practical Exact Algorithm for the Individual Haplotyping Problem MEC

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 1 kb. 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(mk3^k + mlogm + ink), 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.