The DOI matches its Crossref record; 31 of the 31 references it cites were found in a registry or an index.
BWA-MEME: BWA-MEM emulated with a machine learning approach
Open accessAbstract
Motivation: The growing use of next-generation sequencing and enlarged sequencing throughput require efficient short-read alignment, where seeding is one of the major performance bottlenecks. The key challenge in the seeding phase is searching for exact matches of substrings of short reads in the reference DNA sequence. Existing algorithms, however, present limitations in performance due to their frequent memory accesses. Results: This article presents BWA-MEME, the first full-fledged short read alignment software that leverages learned indices for solving the exact match search problem for efficient seeding. BWA-MEME is a practical and efficient seeding algorithm based on a suffix array search algorithm that solves the challenges in utilizing learned indices for SMEM search which is extensively used in the seeding phase. Our evaluation shows that BWA-MEME achieves up to 3.45× speedup in seeding throughput over BWA-MEM2 by reducing the number of instructions by 4.60×, memory accesses by 8.77× and LLC misses by 2.21×, while ensuring the identical SAM output to BWA-MEM2. Availability and implementation: The source code and test scripts are available for academic use at https://github.com/kaist-ina/BWA-MEME/. Supplementary information: Supplementary data are available at Bioinformatics online.
Overview
The claims and statistics of this paper haven’t been checked yet.
Free: it reads the open-access text and checks the first 5 claims that cite a source we can check. Create a free account to check every claim.
Integrity signals
Registry
Cites
Statistics
Verification
Claims the paper makes
The claims and statistics of this paper haven’t been checked yet.
Free: it reads the open-access text and checks the first 5 claims that cite a source we can check. Create a free account to check every claim.
Self-check
Percentages, sums and reported differences re-computed from the paper’s own numbers.
The self-check needs the paper’s full text.
Citations
Cites
Gapped BLAST and PSI-BLAST: a new generation of protein database search programs
Altschul, S. (1997) · Nucleic Acids Research · doi:10.1093/nar/25.17.3389 · Cited by 73,302
Fast and accurate short read alignment with Burrows-Wheeler transform
Li, H., & Durbin, R. (2009) · Bioinformatics · doi:10.1093/bioinformatics/btp324 · Cited by 58,607
Fast gapped-read alignment with Bowtie 2
Langmead, B., & Salzberg, S. L. (2012) · Nature Methods · doi:10.1038/nmeth.1923 · Cited by 56,400
STAR: ultrafast universal RNA-seq aligner
Dobin, A., Davis, C. A., Schlesinger, F., Drenkow, J., Zaleski, C., Jha, S., Batut, P., Chaisson, M., & Gingeras, T. R. (2013) · Bioinformatics · doi:10.1093/bioinformatics/bts635 · Cited by 51,709
A global reference for human genetic variation
The 1000 Genomes Project Consortium, authors, C., Auton, A., Abecasis, G. R., Steering committee, Altshuler, D. M., Durbin, R. M., Abecasis, G. R., Bentley, D. R., Chakravarti, A., et al. (2015) · Nature · doi:10.1038/nature15393 · Cited by 18,247
Minimap2: Pairwise alignment for nucleotide sequences
Li, H. (2018) · Bioinformatics · doi:10.1093/bioinformatics/bty191 · Cited by 14,807
<tt>BLAT</tt> —The <tt>BLAST</tt> -Like Alignment Tool
Kent, W. J. (2002) · Genome Research · doi:10.1101/gr.229202 · Cited by 8,480
Aligning sequence reads, clone sequences and assembly contigs with BWA-MEM
Li, H. (2013) · DROPS (Schloss Dagstuhl – Leibniz Center for Informatics) · doi:10.48550/arxiv.1303.3997 · Cited by 5,159
Aligning sequence reads, clone sequences and assembly con*gs with BWA-MEM
Li, H. (2014) · arXiv (Cornell University) · doi:10.6084/m9.figshare.963153.v1 · Cited by 4,932
SOAP2: an improved ultrafast tool for short read alignment
Li, R., Yu, C., Li, Y., Lam, T.-W., Yiu, S.-M., Kristiansen, K., & Wang, J. (2009) · Bioinformatics · doi:10.1093/bioinformatics/btp336 · Cited by 3,760
Efficient Architecture-Aware Acceleration of BWA-MEM for Multicore Systems
Vasimuddin, M., Misra, S., Li, H., & Aluru, S. (2019) · 2019 IEEE International Parallel and Distributed Processing Symposium (IPDPS) · doi:10.1109/ipdps.2019.00041 · Cited by 3,000
MUMmer4: A fast and versatile genome alignment system
Marçais, G., Delcher, A. L., Phillippy, A. M., Coston, R., Salzberg, S. L., & Zimin, A. (2018) · PLOS Computational Biology · doi:10.1371/journal.pcbi.1005944 · Cited by 2,484
Strelka2: fast and accurate calling of germline and somatic variants
Kim, S., Scheffler, K., Halpern, A. L., Bekritsky, M. A., Noh, E., Källberg, M., Chen, X., Kim, Y., Beyter, D., Krusche, P., et al. (2018) · Nature Methods · doi:10.1038/s41592-018-0051-x · Cited by 1,632
Chaisson, M. J., & Tesler, G. (2012) · BMC Bioinformatics · doi:10.1186/1471-2105-13-238 · Cited by 1,202
The Case for Learned Index Structures
Kraska, T., Beutel, A., Chi, E. H., Dean, J., & Polyzotis, N. (2018) · Proceedings of the 2018 International Conference on Management of Data · doi:10.1145/3183713.3196909 · Cited by 956
A survey of sequence alignment algorithms for next-generation sequencing
Li, H., & Homer, N. (2010) · Briefings in Bioinformatics · doi:10.1093/bib/bbq015 · Cited by 875
Integrating human sequence data sets provides a resource of benchmark SNP and indel genotype calls
Zook, J. M., Chapman, B., Wang, J., Mittelman, D., Hofmann, O., Hide, W., & Salit, M. (2014) · Nature Biotechnology · doi:10.1038/nbt.2835 · Cited by 814
Exploring single-sample SNP and INDEL calling with whole-genome de novo assembly
Li, H. (2012) · Bioinformatics · doi:10.1093/bioinformatics/bts280 · Cited by 398
Eberle, M. A., Fritzilas, E., Krusche, P., Källberg, M., Moore, B. L., Bekritsky, M. A., Iqbal, Z., Chuang, H.-Y., Humphray, S. J., Halpern, A. L., et al. (2017) · Genome Research · doi:10.1101/gr.210500.116 · Cited by 354
An experimental study of an opportunistic index
Ferragina, P., & Manzini, G. (2001) · doi:10.5555/365411.365458 · Cited by 165
CUSHAW: a CUDA compatible short read aligner to large genomes based on the Burrows–Wheeler transform
Liu, Y., Schmidt, B., & Maskell, D. L. (2012) · Bioinformatics · doi:10.1093/bioinformatics/bts276 · Cited by 160
Hardware acceleration of BWA-MEM genomic short read mapping for longer read lengths
Houtgast, E. J., Sima, V.-M., Bertels, K., & Al-Ars, Z. (2018) · Computational Biology and Chemistry · doi:10.1016/j.compbiolchem.2018.03.024 · Cited by 153
Long read alignment based on maximal exact match seeds
Liu, Y., & Schmidt, B. (2012) · Bioinformatics · doi:10.1093/bioinformatics/bts414 · Cited by 126
deBGA: read alignment with de Bruijn graph-based seed and extension
Liu, B., Guo, H., Brudno, M., & Wang, Y. (2016) · Bioinformatics · doi:10.1093/bioinformatics/btw371 · Cited by 91
A Computational Approach to Packet Classification
Rashelbach, A., Rottenstreich, O., & Silberstein, M. (2020) · ACM SIGCOMM Conference (SIGCOMM) · doi:10.1145/3387514.3405886 · Cited by 76
Prospects and limitations of full-text index structures in genome analysis
Vyverman, M., Bernard De Baets, C., Fack, V., & Dawyndt, P. (2012) · Nucleic Acids Research · doi:10.1093/nar/gks408 · Cited by 34
Accelerated Seeding for Genome Sequence Alignment with Enumerated Radix Trees
Subramaniyan, A. K., Wadden, J., Goliya, K., Ozog, N., Wu, X. L., Narayanasamy, S., Blaauw, D. T., & Das, R. (2021) · Proceedings - International Symposium on Computer Architecture/Proceedings · doi:10.1109/isca52012.2021.00038 · Cited by 31
Sapling: accelerating suffix array queries with learned data models
Kirsche, M., Das, A., & Schatz, M. C. (2020) · Bioinformatics · doi:10.1093/bioinformatics/btaa911 · Cited by 24
Acceleration of short and long DNA read mapping without loss of accuracy using suffix array
Tárraga, J., Arnau, V., Martínez, H., Moreno, R., Cazorla, D., Torres, J. S., Blanquer-Espert, I., Dopazo, J., & Medina, I. (2014) · Bioinformatics · doi:10.1093/bioinformatics/btu553 · Cited by 22
Whisper: read sorting allows robust mapping of DNA sequencing data
Deorowicz, S., Debudaj-Grabysz, A., Gudyś, A., & Grabowski, S. (2018) · Bioinformatics · doi:10.1093/bioinformatics/bty927 · Cited by 7
LISA: A Case For Learned Index based Acceleration of Biological Sequence AnalysisPreprint
Ho, D., Kalikar, S., Misra, S., Ding, J., Md, V., Tatbul, N., Li, H., & Kraska, T. (2020) · bioRxiv (Cold Spring Harbor Laboratory) · doi:10.1101/2020.12.22.423964 · Cited by 6
Metadata
- Authors
- Jung, Y., & Han, D.
- Venue
- Bioinformatics
- Publisher
- Oxford University Press (OUP)
- Published
- 2022-03-07
- Volume
- 38
- Issue
- 9
- Pages
- 2404-2413
- ISSN
- 1367-4803 (ISSN-L)
- 1367-4811
- OpenAlex
- W4214950926
- Cited by
- 331
- References
- 31
- FWCI
- 21.41
- Type
- journal article
- Language
- en
- Open access
- green
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
Data sources
Bibliographic data: Semantic Scholar, OpenAlex, Crossref.
Contains information from the Semantic Scholar Academic Graph Datasets, made available under the ODC Attribution License (ODC-BY 1.0).
Semantic Scholar’s data is described in: Kinney, R., et al. (2023). The Semantic Scholar Open Data Platform. arXiv:2301.10140.