A Practical Parameterized Algorithm forWeighted Minimum Letter Flips Model of the Individual Haplotyping Problem

摘要

Given a set of DNA sequence fragments of an individual with each base of every fragment attached a confidence value, the weighted minimum letter flips model (WMLF) of the individual haplotyping problem is to infer a pair of haplotypes by flipping a number of bases such that the sum of the confidence values corresponding to the flipped bases is minimized. WMLF is NP-hard. This paper proposes a parameterized exact algorithm for WMLF of time O(nk_22~(k_2) + mlogm + mk_1), where m is the number of fragments, n is the number of SNP sites, k_1 is the maximum number of SNP sites that a fragment covers, and k_2 is the maximum number of fragments that cover a SNP site. Since in real biological experiments, both k_1 and k_2 are small, the parameterized algorithm is efficient in practical application.