A Practical Parameterized Algorithm for Weighted Minimum Letter Flips Model of the Individual Haplotyping Problem
Conference Paper
Overview
Research
Identity
Additional Document Info
Other
View All
Overview
abstract
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 , 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. 2008 Springer-Verlag Berlin Heidelberg.
name of conference
Frontiers in Algorithmics, Second Annual International Workshop, FAW 2008, Changsha, China, June 19-21, 2008, Proceeedings