A Practical Parameterized Algorithm for Weighted Minimum Letter Flips Model of the Individual Haplotyping Problem Conference Paper uri icon

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

published proceedings

  • Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

author list (cited authors)

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

citation count

  • 1

complete list of authors

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

publication date

  • July 2008