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 \(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.
This research was supported in part by the National Natural Science Foundation of China under Grant Nos. 60433020 and 60773111, the National Basic Research 973 Program of China No.2008CB317107, the Program for New Century Excellent Talents in University No. NCET-05-0683, the Program for Changjiang Scholars and Innovative Research Team in University No. IRT0661, and the Scientific Research Fund of Hunan Provincial Education Department under Grant No.06C526.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
Venter, J.C., Adams, M.D., Myers, E.W., et al.: The sequence of the human genome. Science 291(5507), 1304–1351 (2001)
The International HapMap Consortium: A haplotype map of the human genome. Nature 437(7063), 1299–1320 (2005)
Gabriel, S.B., Schaffner, S.F., Nguyen, H., et al.: The structure of haplotype blocks in the human genome. Science 296(5576), 2225–2229 (2002)
Stephens, J.C., Schneider, J.A., Tanguay, D.A., et al.: Haplotype variation and linkage disequilibrium in 313 human genes. Science 293(5529), 489–493 (2001)
Horikawa, Y., Oda, N., Cox, N.J., et al.: Genetic variation in the gene encoding calpain-10 is associated with type 2 diabetes mellitus. Nature Genetics 26(2), 163–175 (2000)
Zhang, X.S., Wang, R.S., Wu, L.Y., Chen, L.: Models and algorithms for haplotyping problem. Current Bioinformatics 1(1), 105–114 (2006)
Zhao, Y.Y., Wu, L.Y., Zhang, J.H., Wang, R.S., Zhang, X.S.: Haplotype assembly from aligned weighted snp fragments. Computational Biology and Chemistry 29(4), 281–287 (2005)
Lancia, G., Bafna, V., Istrail, S., Lippert, R., Schwartz, R.: SNPs Problems, Complexity, and Algorithms. In: Meyer auf der Heide, F. (ed.) ESA 2001. LNCS, vol. 2161, pp. 182–193. Springer, Berlin (2001)
Lippert, R., Schwartz, R., Lancia, G., Istrail, S.: Algorithmic strategies for the single nucleotide polymorphism haplotype assembly problem. Brief. Bioinform 3(1), 1–9 (2002)
Greenberg, H.J., Hart, W.E., Lancia, G.: Opportunities for combinatorial optimization in computational biology. INFORMS J. Comput. 16(3), 211–231 (2004)
Hinds, D.A., Stuve, L.L., Nilsen, G.B., Halperin, E., Eskin, E., Ballinger, D.B., Frazer, K.A., Cox, D.R.: Whole-genome patterns of common dna variation in three human populations. Science 307(5712), 1072–1079 (2005)
International Human Genome Sequencing Consortium: Initial sequencing and analysis of the human genome. Nature 409(6822), 860–921 (2001)
Huson, D.H., Halpern, A.L., Lai, Z., Myers, E.W., Reinert, K., Sutton, G.G.: Comparing Assemblies Using Fragments and Mate-Pairs. In: Gascuel, O., Moret, B.M.E. (eds.) WABI 2001. LNCS, vol. 2149, pp. 294–306. Springer, Berlin (2001)
Wang, R.S., Wu, L.Y., Li, Z.P., Zhang, X.S.: Haplotype reconstruction from snp fragments by minimum error correction. Bioinformatics 21(10), 2456–2462 (2005)
Panconesi, A., Sozio, M.: Fast Hare: A Fast Heuristic for Single Individual SNP Haplotype Reconstruction. In: Jonassen, I., Kim, J. (eds.) WABI 2004. LNCS (LNBI), vol. 3240, pp. 266–277. Springer, Heidelberg (2004)
Myers, G.: A dataset generator for whole genome shotgun sequencing. In: Lengauer, T., Schneider, R., Bork, P., Brutlag, D.L., Glasgow, J.I., Mewes, H.W., Zimmer, R. (eds.) Proc. ISMB, pp. 202–210. AAAI Press, California (1999)
Author information
Authors and Affiliations
Editor information
Rights and permissions
Copyright information
© 2008 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Xie, M., Wang, J., Zhou, W., Chen, J. (2008). A Practical Parameterized Algorithm for Weighted Minimum Letter Flips Model of the Individual Haplotyping Problem . In: Preparata, F.P., Wu, X., Yin, J. (eds) Frontiers in Algorithmics. FAW 2008. Lecture Notes in Computer Science, vol 5059. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-540-69311-6_5
Download citation
DOI: https://doi.org/10.1007/978-3-540-69311-6_5
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-69310-9
Online ISBN: 978-3-540-69311-6
eBook Packages: Computer ScienceComputer Science (R0)