SpeedHap: An Accurate Heuristic for the Single Individual SNP Haplotyping Problem with Many Gaps, High Reading Error Rate and Low Coverage

ABSTRACT

Single nucleotide polymorphism (SNP) is the most frequent form of DNA variation. The set of SNP's present in a chromosome (called the em haplotype) is of interest in a wide area of applications in molecular biology and biomedicine, including diagnostic and medical therapy. In this paper we propose a new heuristic method for the problem of haplotype reconstruction for (portions of) a pair of homologous human chromosomes from a single individual (SIH). The problem is well known in literature and exact algorithms have been proposed for the case when no (or few) gaps are allowed in the input fragments. These algorithms, though exact and of polynomial complexity, are slow in practice. When gaps are considered no exact method of polynomial complexity is known. The problem is also hard to approximate with guarantees. Therefore fast heuristics have been proposed. In this paper we describe SpeedHap, a new heuristic method that is able to tackle the case of many gapped fragments and retains its effectiveness even when the input fragments have high rate of reading errors (up to 20%) and low coverage (as low as 3). We test SpeedHap on real data from the HapMap Project.

REFERENCES

• 1: Vineet Bafna , Bjarni V. Halldorsson , Russell Schwartz , Andrew G. Clark , Sorin Istrail, Haplotypes and informative SNP selection algorithms: don't block out information, Proceedings of the seventh annual international conference on Research in computational molecular biology, p.19-27, April 10-14, 2003, Berlin, Germany [doi>10.1145/640075.640078]
• 2: Vineet Bafna , Sorin Istrail , Giuseppe Lancia , Romeo Rizzi, Polynomial and APX-hard cases of the individual haplotyping problem, Theoretical Computer Science, v.335 n.1, p.109-125, 20 May 2005 [doi>10.1016/j.tcs.2004.12.017]
• 3: Paola Bonizzoni , Gianluca Della Vedova , Riccardo Dondi , Jing Li, The Haplotyping problem: an overview of computational models and solutions, Journal of Computer Science and Technology, v.18 n.6, p.675-688, November 2003 [doi>10.1007/BF02945456]
• 4: R. Cilibrasi, L. van Iersel, S. Kelk, and J. Tromp, "On the Complexity of Several Haplotyping Problems," Proc. Fifth Int'l Workshop Algorithms in Bioinformatics (WABI '05), pp. 128-139, 2005.
• 5: Rudi Cilibrasi , Leo van Iersel , Steven Kelk , John Tromp, The Complexity of the Single Individual SNP Haplotyping Problem, Algorithmica, v.49 n.1, p.13-36, September 2007 [doi>10.1007/s00453-007-0029-z]
• 6: The Int'l HapMap Consortium, "A Haplotype Map of the Human Genome" Nature, vol. 437, pp. 1299-1320, 2005.
• 7: M.J. Daly, J.D. Rioux, S.F. Schaffner, T.J. Hudson, and E.S. Lander, "High-Resolution Haplotype Structure in the Human Genome," Nature Genetics, vol. 29, pp. 229-232, 2001.
• 8: Roberto Grossi , Ankur Gupta , Jeffrey Scott Vitter, High-order entropy-compressed text indexes, Proceedings of the fourteenth annual ACM-SIAM symposium on Discrete algorithms, January 12-14, 2003, Baltimore, Maryland
• 9: Y. Guo and D.C. Jamison, "The Distribution of SNPS in Human Gene Regulatory Regions," BMC Genomics, vol. 6, no. 140, 2005.
• 10: D. Gusfield and S.H. Orzack, "Haplotype Inference," CRC Handbook on Bioinformatics, chapter 1, pp. 1-25, CRC Press, 2005.
• 11: C.-G. Hur, S. Kim, C.H. Kim, S.H. Yoon, Y.-H. In, C. Kim, and H.G. Cho, "Fasim: Fragments Assembly Simulation Using Biased-Sampling Model and Assembly Simulation for Microbial Genome Shotgun Sequencing," J. Microbiology and Biotechnology, vol. 16, no. 5, 2006.
• 12: X. Ke, S. Hunt, W. Tapper, R. Lawrence, G. Stavrides, J. Ghori, P. Whittaker, A. Collins, A.P. Morris, D. Bentley, L.R. Cardon, and P. Deloukas, "The Impact of SNP Density on Fine-Scale Patterns of Linkage Disequilibrium," Human Molecular Genetics, vol. 13, no. 6, pp. 577-588, 2004.
• 13: Giuseppe Lancia , Vineet Bafna , Sorin Istrail , Ross Lippert , Russell Schwartz, SNPs Problems, Complexity, and Algorithms, Proceedings of the 9th Annual European Symposium on Algorithms, p.182-193, August 28-31, 2001
• 14: E.S. Lander and M.S. Waterman, "Genomic Mapping by Fingerprinting Random Clones: A Mathematical Analysis," Genomics, vol. 2, pp. 231-239, 1988.
• 15: Lei Li , Jong Hyun Kim , Michael S. Waterman, Haplotype reconstruction from SNP alignment, Proceedings of the seventh annual international conference on Research in computational molecular biology, p.207-216, April 10-14, 2003, Berlin, Germany [doi>10.1145/640075.640102]
• 16: L.K. Matukumalli, J.J. Grefenstette, D.L. Hyten, I.-Y. Choi, P.B. Cregan, and C.P. Van Tassell, "Application of Machine Learning in SNP Discovery," BMC Bioinformatics, vol. 7, no. 4, 2006.
• 17: Eugene W. Myers, The fragment assembly string graph, Bioinformatics, v.21 n.2, p.79-85, January 2005 [doi>10.1093/bioinformatics/bti1114]
• 18: Gene Myers, A Dataset Generator for Whole Genome Shotgun Sequencing, Proceedings of the Seventh International Conference on Intelligent Systems for Molecular Biology, p.202-210, August 06-10, 1999
• 19: Gonzalo Navarro , Veli Mäkinen, Compressed full-text indexes, ACM Computing Surveys (CSUR), v.39 n.1, p.2-es, 2007 [doi>10.1145/1216370.1216372]
• 20: A. Panconesi and M. Sozio, "Fast Hare: A Fast Heuristic for Single Individual SNP Haplotype Reconstruction," Proc. Fourth Int'l Workshop Algorithms in Bioinformatics (WABI '04), pp. 266-277, 2004.
• 21: J.K. Pritchard and M. Przeworski, "Linkage Disequilibrium in Humans: Models and Data," Am. J. Human Genetics, vol. 69, pp. 1-14, 2001.
• 22: R. Sachidanandam et al., "A Map of Human Genome Sequence Variation Containing 1.42 Million Single Nucleotide Polymorphisms," Nature, vol. 409, pp. 928-933, Feb. 2001.
• 23: K.A. Frazer et al., "A Second Generation Human Haplotype Map of over 3.1 Million SNPs," Nature, vol. 449, pp. 851-861, Oct. 2007.
• 24: Romeo Rizzi , Vineet Bafna , Sorin Istrail , Giuseppe Lancia, Practical Algorithms and Fixed-Parameter Tractability for the Single Individual SNP Haplotyping Problem, Proceedings of the Second International Workshop on Algorithms in Bioinformatics, p.29-43, September 17-21, 2002
• 25: J.C. Roach, C. Boysen, K. Wang, and L. Hood, "Pairwise End Sequencing: A Unified Approach to Genomic Mapping and Sequencing," Genomics, vol. 26, no. 2, pp. 345-353, 1995.
• 26: L.-Y. Wu, R.-S. Wang, X.-S. Zhang, and L. Chen, "A Markov Chain Model for Haplotype Assembly from SNP Fragments," Genome Informatics, vol. 17, no. 2, pp. 162-171, 2006.
• 27: Rui-Sheng Wang , Ling-Yun Wu , Zhen-Ping Li , Xiang-Sun Zhang, Haplotype reconstruction from SNP fragments by minimum error correction, Bioinformatics, v.21 n.10, p.2456-2462, May 2005 [doi>10.1093/bioinformatics/bti352]
• 28: Ying Wang , Enmin Feng , Ruisheng Wang, Technical comment: A clustering algorithm based on two distance functions for MEC model, Computational Biology and Chemistry, v.31 n.2, p.148-150, April, 2007 [doi>10.1016/j.compbiolchem.2007.02.001]
• 29: M.P. Weiner and T.J. Hudson, "Introduction to SNPs: Discovery of Markers for Disease," Biotechniques, suppl., 2002.
• 30: Y.-Y. Zhao, L.-Y. Wu, J.-H. Zhang, R.-S. Wang, and X.-S. Zhang, "Haplotype Assembly from Aligned Weighted SNP Fragments," Computational Biology and Chemistry, vol. 29, no. 4, pp. 281-287, 2005.

INDEX TERMS

Primary Classification:
  I. Computing Methodologies
  I.2 ARTIFICIAL INTELLIGENCE
      I.2.8 Problem Solving, Control Methods, and Search
          Subjects: Heuristic methods

Additional Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.2 Nonnumerical Algorithms and Problems

  I. Computing Methodologies
  I.5 PATTERN RECOGNITION
      I.5.1 Models
  I.6 SIMULATION AND MODELING
      I.6.4 Model Validation and Analysis
      I.6.5 Model Development
          Subjects: Modeling methodologies

  J. Computer Applications
  J.3 LIFE AND MEDICAL SCIENCES
      Subjects: Biology and genetics

General Terms:
Algorithms, Design, Performance, Theory

Keywords:
Algorithms, Biology and genetics