WHAM: a high-throughput sequence alignment method
Abstract
Over the last decade the cost of producing genomic sequences has dropped dramatically due to the current so called "next-gen" sequencing methods. However, these next-gen sequencing methods are critically dependent on fast and sophisticated data processing methods for aligning a set of query sequences to a reference genome using rich string matching models. The focus of this work is on the design, development and evaluation of a data processing system for this crucial "short read alignment" problem. Our system, called WHAM, employs novel hash-based indexing methods and bitwise operations for sequence alignments. It allows richer match models than existing methods and it is significantly faster than the existing state-of-the-art method. In addition, its relative speedup over the existing method is poised to increase in the future in which read sequence lengths will increase. The WHAM code is available at http://www.cs.wisc.edu/wham/.
Integrity signals
Registry
Cites
Statistics
Claims the paper makes
Claims other papers make about this one
Each is checked against this paper’s own text: does it say what the citing paper says it does?
High inter-site false positive DEG rates were observed across multiple analysis pipelines (WHAM, Mapsplice, Novoalign, Cufflinks, HTSeq), independent of pipeline or alignment method.
“When we examined the inter-site DEG false positive rates for several other analysis pipelines (WHAM34, Mapsplice35, Novoalign36, Cufflinks23, 37, 38 and HTSeq39) we found similarly high false positive rates, regardless of the analysis pipeline or read alignment methods used (Supplementary Fig. 1).”
From Detecting and correcting systematic variation in large-scale RNA sequencing data (2014) · cites this paper as [34]
Cites
Basic local alignment search tool
Altschul, S. F., Gish, W., Miller, W., Myers, E. W., & Lipman, D. J. (1990) · Journal of Molecular Biology · doi:10.1006/jmbi.1990.9999 · Cited by 98,669 · see citing works
Ultrafast and memory-efficient alignment of short DNA sequences to the human genome.
Langmead, B., Trapnell, C., Pop, M., & Salzberg, S. L. (2009) · Genome Biology · doi:10.1186/gb-2009-10-3-r25 · Cited by 21,849 · see citing works
The Art of Computer Programming
Knuth, D. E. (1968) · Cited by 16,097 · see citing works
The sequence of the human genome
Venter, J. C., Adams, M. D., Myers, E. W., Li, P. W., Mural, R. J., Sutton, G. G., Smith, H. O., Yandell, M., Evans, C. A., Holt, R. A., et al. (2001) · Science · doi:10.1126/science.1058040 · Cited by 13,909 · see citing works
Needleman, S. B., & Wunsch, C. D. (1970) · Journal of Molecular Biology · doi:10.1016/0022-2836(70)90057-4 · Cited by 11,288 · see citing works
Identification of common molecular subsequences
Smith, T. F., & Waterman, M. S. (1981) · Journal of Molecular Biology · doi:10.1016/0022-2836(81)90087-5 · Cited by 9,962 · see citing works
SOAP: Short oligonucleotide alignment program
Li, R., Li, Y., Kristiansen, K., & Wang, J. (2008) · Bioinformatics · doi:10.1093/bioinformatics/btn025 · Cited by 3,597 · see citing works
Self-citationMapping short DNA sequencing reads and calling variants using mapping quality scores
Li, H., Ruan, J., & Durbin, R. (2008) · Genome Research · doi:10.1101/gr.078212.108 · Cited by 2,638 · see citing works
A Block-sorting Lossless Data Compression Algorithm
Burrows, M. T., & Wheeler, D. J. (1994) · Cited by 2,333 · see citing works
Wu, S., & Manber, U. (1992) · Communications of the ACM · doi:10.1145/135239.135244 · Cited by 732 · see citing works
A new approach to text searching
Baeza-Yates, R. A., & Gonnet, G. H. (1992) · Communications of the ACM · doi:10.1145/135239.135243 · Cited by 607 · see citing works
Efficient exact set-similarity joins
Arasu, A., Ganti, V., & Kaushik, R. (2006) · doi:10.5555/1182635.1164206 · Cited by 406 · see citing works
Cache Conscious Indexing for Decision-Support in Main Memory
Rao, J., & Ross, K. A. (1998) · doi:10.7916/d8t441zb · Cited by 249 · see citing works
Partial-Match Retrieval Algorithms
Rivest, R. L. (1976) · SIAM Journal on Computing · doi:10.1137/0205003 · Cited by 244 · see citing works
Li, C., Wang, B., & Yang, X. (2007) · Cited by 187 · see citing works
McPherson, J. D. (2009) · Nature Methods · doi:10.1038/nmeth.f.268 · Cited by 130 · see citing works
Yang, X., Wang, B., & Li, C. (2008) · Proceedings - ACM-SIGMOD International Conference on Management of Data · doi:10.1145/1376616.1376655 · Cited by 92 · see citing works
n-Gram/2L: A Space and Time Efficient Two-Level n-Gram Inverted Index Structure
Kim, M., Whang, K.-Y., Lee, J.-G., et al. (2005) · Cited by 76 · see citing works
Efficient Subsequence Matching Using the Longest Common Subsequence with a Dual Match Index
Han, T. S., Ko, S.-K., & Kang, J. (2007) · Lecture notes in computer science · doi:10.1007/978-3-540-73499-4_44 · Cited by 23 · see citing works
Reference-based alignment in large sequence databases
Papapetrou, P., Athitsos, V., Kollios, G., et al. (2009) · Proceedings of the VLDB Endowment · doi:10.14778/1687627.1687651 · Cited by 18 · see citing works
Fast nGram-based string search over data encoded using algebraic signatures
Litwin, W., Mokadem, R., Rigaux, P., et al. (2007) · Cited by 16 · see citing works
Novel Approaches to Biomolecular Sequence Indexing.
Karakoç, E., Ozsoyoglu, Z. M., Şahinalp, S. C., et al. (2004) · IEEE Data(base) Engineering Bulletin · Cited by 8 · see citing works
Flagged first, then by citations
Cited by
Sorted by citations
Detecting and correcting systematic variation in large-scale RNA sequencing data
Li, S., Łabaj, P. P., Zumbo, P., Sykacek, P., Shi, W., Shi, L., Phan, J., Wu, P.-Y., Wang, M., Wang, C., et al. (2014) · Nature Biotechnology · doi:10.1038/nbt.3000 · Cited by 175 · see citing works
- Authors
- Li, Y., Terrell, A., & Patel, J. M.
- Affiliations
- University of Wisconsin–Madison (US)
- ORCID
- Patel, Jignesh M.
- Venue
- Proceedings of the 2011 ACM SIGMOD International Conference on Management of data
- Publisher
- ACM
- Published
- 2011-06-12
- Pages
- 445-456
- ISSN
- 0730-8078 (ISSN-L)
- OpenAlex
- W2112099725
- Cited by
- 36
- References
- 22
- Citations by year
- 2021: 4 · 2019: 1 · 2017: 3 · 2016: 1 · 2015: 4 · 2014: 4 · 2013: 7 · 2012: 11
- FWCI
- 5.76
- Type
- conference paper
- Language
- en
- Open access
- closed
- Locations
- ACM SIGMOD International Conference on Management of Data (SIGMOD) (publishedVersion)
- Topics
- Physical Sciences › Computer Science › Artificial Intelligence › Algorithms and Data Compression
- Life Sciences › Biochemistry, Genetics and Molecular Biology › Molecular Biology › Genomics and Phylogenetic Studies
- Life Sciences › Biochemistry, Genetics and Molecular Biology › Molecular Biology › Fractal and DNA sequence analysis
- Keywords
- short-read alignment, next-generation sequencing, hash-based indexing, bitwise operations, sequence alignment, string matching, reference genome, WHAM
About these checks
Registry, retraction, Cites and statistics results are computed, not judged, with one exception: a printed reference that no index lists is read once by a model before it counts as a citation error. Claims are extracted by a model and kept only when their quote appears verbatim in the text; each cited source is then checked, with a model’s help, for whether it says what the claim relies on. Those verdicts can be wrong — read the claim’s quote and the cited source before relying on one.
Statistics and arithmetic are recomputed, not judged.
Confidence bands are shown only for fields calibrated on our annotated test set. None is calibrated yet, so no band is shown.
What counts as a claim ›How we measure confidence ›How we check this ›
Are you an author, or do you see a problem with this page? Request a review
