Crossref journal-article
Oxford University Press (OUP)
Bioinformatics (286)
Abstract

Abstract Motivation: Next-generation sequencing captures sequence differences in reads relative to a reference genome or transcriptome, including splicing events and complex variants involving multiple mismatches and long indels. We present computational methods for fast detection of complex variants and splicing in short reads, based on a successively constrained search process of merging and filtering position lists from a genomic index. Our methods are implemented in GSNAP (Genomic Short-read Nucleotide Alignment Program), which can align both single- and paired-end reads as short as 14 nt and of arbitrarily long length. It can detect short- and long-distance splicing, including interchromosomal splicing, in individual reads, using probabilistic models or a database of known splice sites. Our program also permits SNP-tolerant alignment to a reference space of all possible combinations of major and minor alleles, and can align reads from bisulfite-treated DNA for the study of methylation state. Results: In comparison testing, GSNAP has speeds comparable to existing programs, especially in reads of ≥70 nt and is fastest in detecting complex variants with four or more mismatches or insertions of 1–9 nt and deletions of 1–30 nt. Although SNP tolerance does not increase alignment yield substantially, it affects alignment results in 7–8% of transcriptional reads, typically by revealing alternate genomic mappings for a read. Simulations of bisulfite-converted DNA show a decrease in identifying genomic positions uniquely in 6% of 36 nt reads and 3% of 70 nt reads. Availability: Source code in C and utility programs in Perl are freely available for download as part of the GMAP package at http://share.gene.com/gmap. Contact:  twu@gene.com

Bibliography

Wu, T. D., & Nacu, S. (2010). Fast and SNP-tolerant detection of complex variants and splicing in short reads. Bioinformatics, 26(7), 873–881.

Authors 2
  1. Thomas D. Wu (first)
  2. Serban Nacu (additional)
References 33 Referenced 1,715
  1. 10.1093/hmg/ddi006 / Hum. Mol. Genet. / Comprehensive identification and characterization of diallelic insertion-deletion polymorphisms in 330 human candidate genes by Bhangale (2005)
  2. 10.1093/bioinformatics/btn300 / Bioinformatics / Optimal spliced alignments of short sequence reads by Bona (2008)
  3. {'key': '2023012508033121200_B3', 'article-title': 'A block-sorting lossless data compression algorithm', 'volume-title': 'Technical Report 124.', 'author': 'Burrows', 'year': '1994'} / Technical Report 124. / A block-sorting lossless data compression algorithm by Burrows (1994)
  4. 10.1038/nbt1236 / Nat. Biotechnol. / Evaluation of DNA microarray results with quantitative gene expression platforms by Canales (2006)
  5. 10.1073/pnas.162371599 / Proc. Natl Acad. Sci. / Locus-specific control of asymmetric and CpNpG methylation by the DRM and CMT3 methyltransferase genes by Cao (2002)
  6. 10.1038/nbt.1530 / Nat. Biotechnol. / Targeted bisulfite sequencing reveals changes in DNA methylation associated with nuclear reprogramming by Deng (2009)
  7. 10.1016/j.modgep.2003.08.006 / Gene Expression Patterns / A conserved non-homeodomain Hoxa9 isoform interacting with CBP is co-expressed with the ‘typical’ Hoxa9 protein during embryogenesis by Dintilhac (2004)
  8. 10.1146/annurev.biochem.74.010904.153721 / Annu. Rev. Biochem. / Eukaryotic cytosine methyltransferases by Goll (2005)
  9. 10.1101/gr.080259.108 / Genome Res. / A sequence-level map of chromosomal breakpoints in the MCF-7 breast cancer cell line yields insights into the evolution of a cancer genome by Hampton (2009)
  10. 10.1137/0201004 / SIAM J. Comput. / A simple algorithm for merging two disjoint linearly ordered sets by Hwang (1980)
  11. 10.1093/bioinformatics/btn429 / Bioinformatics / SeqMap: mapping massive amount of oligonucleotides to the genome by Jiang (2008)
  12. {'key': '2023012508033121200_B12', 'first-page': '656', 'article-title': 'BLAT—the BLAST-like alignment tool', 'volume': '12', 'author': 'Kent', 'year': '2002', 'journal-title': 'Genome Research'} / Genome Research / BLAT—the BLAST-like alignment tool by Kent (2002)
  13. {'key': '2023012508033121200_B13', 'volume-title': 'The Art of Computer Programming: Sorting and Searching', 'author': 'Knuth', 'year': '1973'} / The Art of Computer Programming: Sorting and Searching by Knuth (1973)
  14. 10.1186/gb-2009-10-3-r25 / Genome Biology / Ultrafast and memory-efficient alignment of short dna sequences to the human genome by Langmead (2009)
  15. 10.1093/bioinformatics/btp324 / Bioinformatics / Fast and accurate short read alignment with Burrows-Wheeler Transform by Li (2009)
  16. 10.1101/gr.078212.108 / Genome Res. / Mapping short DNA sequencing reads and calling variants using mapping quality scores by Li (2008)
  17. 10.1093/bioinformatics/btn025 / Bioinformatics / SOAP: short oligonucleotide alignment program by Li (2008)
  18. 10.1093/bioinformatics/btp336 / Bioinformatics / SOAP2: an improved ultrafast tool for short read alignment by Li (2009)
  19. 10.1101/gr.083451.108 / Genome Research / Finding the fifth base: Genome-wide sequencing of cytosine methylation by Lister (2009)
  20. 10.1137/0222058 / SIAM J. Comput. / Suffix arrays: a new method for on-line string searches by Manber (1993)
  21. 10.1093/bioinformatics/btp403 / Bioinformatics / SNP-o-matic by Manske (2009)
  22. 10.1145/1250734.1250746 / Proceedings of the 2007 ACM SIGPLAN Conference on Programming Language Design and Implementation / Valgrind: a framework for heavyweight dynamic binary instrumentation by Nethercote (2007)
  23. 10.1101/gr.194201 / Genome Res. / SSAHA: a fast search method for large DNA databases by Ning (2001)
  24. 10.1089/cmb.2006.13.296 / J. Comput. Biol. / Efficient q-gram filters for finding all ε-matches over a given length by Rasmussen (2006)
  25. 10.1371/journal.pcbi.1000386 / PLoS Comput. Biol. / SHRiMP: accurate mapping of color-space reads by Rumble (2009)
  26. 10.1093/nar/29.1.308 / Nucleic Acids Res. / dbSNP: the NCBI database of genetic variation by Sherry (2001)
  27. 10.1186/1471-2105-9-128 / BMC Bioinformatics / Using quality scores and longer reads improves accuracy of Solexa read mapping by Smith (2008)
  28. 10.1093/bioinformatics/btp120 / Bioinformatics / TopHat: discovering splice junctions with RNA-Seq by Trapnell (2009)
  29. 10.1038/nature07509 / Nature / Alternative isoform regulation in human tissue transcriptomes by Wang (2008)
  30. 10.1086/342727 / Am. J. Hum. Genet. / Human diallelic insertion/deletion polymorphisms by Weber (2002)
  31. 10.1101/gr.088823.108 / Genome Res. / RazerS—fast read mapping with sensitivity control by Weese (2009)
  32. 10.1093/bioinformatics/bti310 / Bioinformatics / GMAP: a genomic mapping and alignment program for mRNA and EST sequences by Wu (2005)
  33. 10.1089/1066527041410418 / J. Comput. Biol. / Maximum entropy modeling of short sequence motifs with applications to RNA splicing signals by Yeo (2004)
Dates
Type When
Created 15 years, 6 months ago (Feb. 10, 2010, 10:43 p.m.)
Deposited 2 years, 7 months ago (Jan. 25, 2023, 3:06 a.m.)
Indexed 29 minutes ago (Sept. 3, 2025, 5:34 a.m.)
Issued 15 years, 6 months ago (Feb. 10, 2010)
Published 15 years, 6 months ago (Feb. 10, 2010)
Published Online 15 years, 6 months ago (Feb. 10, 2010)
Published Print 15 years, 5 months ago (April 1, 2010)
Funders 0

None

@article{Wu_2010, title={Fast and SNP-tolerant detection of complex variants and splicing in short reads}, volume={26}, ISSN={1367-4803}, url={http://dx.doi.org/10.1093/bioinformatics/btq057}, DOI={10.1093/bioinformatics/btq057}, number={7}, journal={Bioinformatics}, publisher={Oxford University Press (OUP)}, author={Wu, Thomas D. and Nacu, Serban}, year={2010}, month=feb, pages={873–881} }