A practical parameterized algorithm for the individual haplotyping problem MLF Conference Paper

abstract

• The individual haplotyping problem Minimum Letter Flip (MLF) is a computational problem that, given a set of aligned DNA sequence fragment data of an individual, induces the corresponding haplotypes by flipping minimum SNPs. 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, with a genome-average SNP density of 1.84 SNPs per 1 kb of DNA sequence, the maximum number k 1 of SNP sites that a fragment covers is usually small. Moreover, in order to save time and money, the maximum number k 2 of fragments that cover a SNP site is usually no more than 19. Based on the properties of fragment data, the current paper introduces a new parameterized algorithm of running time , where m is the number of fragments, n is the number of SNP sites. The algorithm solves the MLF problem efficiently even if m and n are large, and is more practical in real biological applications. 2008 Springer-Verlag Berlin Heidelberg.

name of conference

• Theory and Applications of Models of Computation, 5th International Conference, TAMC 2008, Xi'an, China, April 25-29, 2008. Proceedings

authors

• Chen, Jianer

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., & Chen, J.

complete list of authors

• Xie, M||Wang, J||Chen, J

publication date

• December 2008

published in

• Lecture Notes in Artificial Intelligence  Journal

Digital Object Identifier (DOI)

• 10.1007/978-3-540-79228-4-38

International Standard Book Number (ISBN) 10

• 3540792279

International Standard Book Number (ISBN) 13

• 9783540792277

start page

• 433

end page

• 444

volume

• 4978 LNCS