BURST enables mathematically optimal short-read alignment for big data
Abstract
One of the fundamental tasks in analyzing next-generation sequencing data is genome database search, in which DNA sequences are compared to known reference genomes for identification or annotation. Although algorithms exist for optimal database search with perfect sensitivity and specificity, these have largely been abandoned for next-generation sequencing (NGS) data in favor of faster heuristic algorithms that sacrifice alignment quality. Virtually all DNA alignment tools that are commonly used in genomic and metagenomic database search use approximate methods that sometimes report the wrong match, and sometimes fail to find a valid match when present. Here we introduce BURST, a high-throughput DNA short-read aligner that uses several new synergistic optimizations to enable provably optimal alignment in NGS datasets. BURST finds all equally good matches in the database above a specified identity threshold and can either report all of them, pick the most likely among tied matches, or provide lowest-common-ancestor taxonomic annotation among tied matches. BURST can align, disambiguate, and assign taxonomy at a rate of 1,000,000 query sequences per minute against the RefSeq v82 representative prokaryotic genome database (5,500 microbial genomes, 19GB) at 98% identity on a 32-core computer, representing a speedup of up to 20,000-fold over current optimal gapped alignment techniques. This may have broader implications for clinical applications, strain tracking, and other situations where fast, exact, extremely sensitive alignment is desired.
02 /Specification & Classification
Click any tag to browse matching papers- Citations
- 45
- Organism
- Assay
- Research Focus
- Approach
In-depth summary
Claude Opus 5.5 · xhigh effort · 8 Nov 2026 · from the full text of version 1 (8 Sept 2020) · CC BY 4.0
Exhaustive gapped short-read aligner BURST returns all optimal matches above an identity cutoff, with tie-breaking or LCA taxonomy, at 1,000,000 reads/minute against 5,500 prokaryotic genomes (32 cores).
Most short-read mappers used in genomics and metagenomics are approximate, so they can miss valid matches or report wrong ones, while exact optimal aligners have been set aside as too slow for NGS-scale data. The authors state that no earlier work brought optimal short-read mapping to this scale while listing all tied matches and resolving them deterministically, and they report BURST as up to 20,000 times faster than published optimal gapped aligners.
Key results
SuggestedExhaustive alignment with guaranteed optimality, including tie resolution and taxonomy assignment, runs at metagenome-scale throughput. The authors report up to a 20,000-fold speedup over earlier optimal gapped aligners.
1,000,000 150-base queries per minute were aligned, disambiguated and assigned taxonomy using 32 cores, 98% identity and the RefSeq v82 representative prokaryotic set (5,500 microbial genomes, 19GB). The Table 2 caption says runtime is comparable to heuristic aligners on human gut amplicon data (Greengenes 97% OTU database). The text does not give its values or name the optimal aligners compared. · Abstract; Previous work; Performance and system requirements; Tables
ShownIn best-hit mode, BURST returned an optimal-scoring match for every query. bowtie2 at default settings returned more suboptimal matches as identity to the reference fell.
Based on a gut amplicon dataset aligned against the Greengenes 97% OTU database (Figure 3a). The text describes the comparison qualitatively and gives no counts or rates of suboptimal hits. · Discussion; Figure legends
SuggestedAssigning taxonomy from one best hit overstates specificity. Taking the lowest common ancestor (LCA) across all tied best hits gives more conservative per-read labels, for example reporting a genus instead of an arbitrary species.
Human amplicon dataset with the Greengenes 13_8 reference database: naive best-hit assignment (bowtie2 default) showed strong overconfidence compared with BURST in LCA mode (Figure 3b). The text reports no proportions. · BURST enables arbitrarily confident taxonomy…; Discussion; Figure legends
ShownRelative to the input, the database shrinks as reference redundancy grows. For a large single-species collection it is smaller than a bowtie2 index.
Database plus accelerator is just over 7x the input FASTA for the RefSeq v82 representative genomes (little redundancy) and 2.5x for over 51,000 RefSeq v84 prokaryotic genomes. The BURST database for 7,676 Staphylococcus aureus genomes (RefSeq v99) is under 1.1x the input FASTA, versus 1.9x for bowtie2 on the same genomes. · Performance and system requirements
SuggestedReporting all tied alignments (ALLPATHS mode) of genes against genomes yields a gene-sharing network that reflects relatedness among Enterococcus species and strains.
All genes of 21 strains (10 E. faecalis and 10 E. faecium from RefSeq v86, plus 1 E. aquimarinus) were aligned to those strains' genomes and drawn in Cytoscape. E. faecalis and E. faecium were closer to each other than either was to E. aquimarinus. From the network, the authors infer greater strain-to-strain dissimilarity within E. faecalis than within E. faecium (Figure 4). The result is qualitative only. · Discussion; Figure legends
Methods, data and reproducibility
BURST aligns DNA end to end by dynamic programming, scoring by Levenshtein distance with BLAST-style identity as tie-breaker. It gains speed, without losing optimality, by sorting queries to reuse cached rows for shared prefixes, pruning cells that cannot reach the score threshold, tracking gap counts instead of traceback, two-pass scoring and an optional k-mer accelerator database.
- NCBI RefSeq v82 reference and representative prokaryotic genome collection (throughput benchmark and database size) · prokaryotes (microbial genomes) · n = 5,500 microbial genomes, 19GB
- NCBI RefSeq v84 prokaryotic genomes: complete, chromosome- and scaffold-level, plus representative contig-level (database size) · prokaryotes · n = over 51,000 genomes
- Staphylococcus aureus genomes from RefSeq v99 (database size and creation time) · Staphylococcus aureus · n = 7,676 genomes
- Human gut amplicon dataset aligned against the Greengenes 97% OTU database (runtime and best-hit comparison with bowtie2) · human gut (amplicon data)
- Human amplicon dataset with the Greengenes 13_8 reference database (LCA versus best-hit taxonomy) · human (amplicon data)
- Genes and genomes of Enterococcus strains, E. faecalis and E. faecium drawn at random from RefSeq v86 assemblies (ALLPATHS network) · Enterococcus faecalis, E. faecium, E. aquimarinus · n = 21 strains (10 + 10 + 1)
- Simulated dataset illustrating capitalist (parsimony) disambiguation
- Rep 200: RefSeq v200 assemblies marked representative or reference (database creation time)
- Methods & tools
- BURST, bowtie2, Cytoscape, Greengenes 13_8, Greengenes 97% OTU database, NCBI RefSeq
- Data & accessions
- https://github.com/knights-lab/BURST
- Software & environment
- Precompiled static binaries that need no dependencies or installation step (AGPLv3). No version numbers are stated.
- Assay conditions & compute
- Throughput was measured on a 32-core computer. The database-creation comparison used 28 threads on a dual Xeon Platinum 8180 machine with 1.5TB RAM. Database plus accelerator needs just over 7x the reference FASTA size in RAM and disk when references have little redundancy.
- Reproducibility gaps
- The amplicon and simulated datasets have no accession or link in the text. The BURST version used for the benchmarks is not stated. The S. aureus genome accessions are given only through the GitHub repository.
Limitations (6)
- BURST is not splice-aware and does not output SAM, so it may not suit human genomic workflows that depend on those features. · stated by the authors
- BURST remains 10-to-100 times slower than some heuristic or non-optimal search approaches, k-mer-based search for example. · stated by the authors
- For whole-genome databases, the precalculated accelerator can reach upwards of 7x the input FASTA size, so memory demand is high. Users who value speed and low RAM over optimality may prefer other tools. · stated by the authors
- Only DNA end-to-end alignment is supported, with no protein or local alignment, variable gap penalties or nucleotide-specific scores. The authors argue these matter less for high-identity read mapping and list protein alignment as future work. · stated by the authors
- Accuracy is compared only against bowtie2 at default settings on amplicon data, and the text reports the comparison qualitatively, without counts or rates. · noted in this summary
- The text does not name the optimal aligners behind the 20,000-fold speedup or give the Table 2 and Table 3 values. Capitalist mode is shown only on one simulated example. · noted in this summary
Who should read:Read this if you map short reads or amplicons to large microbial reference databases and need every optimal hit, explicit handling of ties, or conservative per-read taxonomy instead of heuristic best guesses.
Reproducibility ledger
Nobody has reported trying to reproduce this paper yet. Did you replicate an experiment or run the code? Your report saves the next lab a week.
Sign in to file a reproducibility report.
Related papers
- Fast and accurate short read alignment with Burrows–Wheeler transform
Heng Li, Richard Michael Durbin·BioinformaticsPeer-reviewed·May 18, 2009
- Qudaich: A smart sequence aligner
Sajia Akhter, Robert A Edwards·bioRxiv·Jun 24, 2016
- Fast and accurate short read alignment with hybrid hash-tree data structure
Junichiro Makino, Toshikazu Ebisuzaki, … Yoshihide Hayashizaki·Genomics & InformaticsPeer-reviewed·Oct 29, 2024
- benchNGS : An approach to benchmark short reads alignment tools
Farzana Rahman, Mehedi Hassan, … Tatiana Tatarinova·bioRxiv·Apr 18, 2015
- Sequence alignment with k-bounded matching statistics
Tommi Mäklin, Jarno Alanko, … Simon J. Puglisi·bioRxiv·May 19, 2025
- Accuracy, speed and error tolerance of short DNA sequence aligners
Mark Ziemann·bioRxiv·May 16, 2016