CoChat
Sign Up
Cited by 58,607Genomics and Phylogenetic StudiesAlgorithms and Data CompressionFractal and DNA sequence analysis

The DOI matches its Crossref record; 30 of the 32 references it cites were found in a registry or an index.

Fast and accurate short read alignment with Burrows-Wheeler transform

Open access
Li, Heng, Durbin, Richard·2009·Bioinformatics
DOI 10.1093/bioinformatics/btp324PMC PMC2705234
Open this paper in CoChat — free accountOpen PDF

Abstract

MOTIVATION: The enormous amount of short reads generated by the new DNA sequencing technologies call for the development of fast and accurate read alignment programs. A first generation of hash table-based methods has been developed, including MAQ, which is accurate, feature rich and fast enough to align short reads from a single individual. However, MAQ does not support gapped alignment for single-end reads, which makes it unsuitable for alignment of longer reads where indels may occur frequently. The speed of MAQ is also a concern when the alignment is scaled up to the resequencing of hundreds of individuals. RESULTS: We implemented Burrows-Wheeler Alignment tool (BWA), a new read alignment package that is based on backward search with Burrows-Wheeler Transform (BWT), to efficiently align short sequencing reads against a large reference sequence such as the human genome, allowing mismatches and gaps. BWA supports both base space reads, e.g. from Illumina sequencing machines, and color space reads from AB SOLiD machines. Evaluations on both simulated and real data suggest that BWA is approximately 10-20x faster than MAQ, while achieving similar accuracy. In addition, BWA outputs alignment in the new standard SAM (Sequence Alignment/Map) format. Variant calling and other downstream analyses after the alignment can be achieved with the open source SAMtools software package. AVAILABILITY: http://maq.sourceforge.net.

Overview

The claims and statistics of this paper haven’t been checked yet.

Run the check — free, no account needed. It reads the open-access text and checks the sources it cites.

A few free checks a day · papers already verified open instantly · results are public

Integrity signals

Registry

Crossref · 10.1093/bioinformatics/btp324

Cites

30 of 30 references verified0 citation errors · 0 not checkable

Statistics

Figures

Fig. 1. Prefix trie of string ‘GOOGOL’. Symbol ∧ marks the start of the string. The two numbers in a node give the SA interval of the string represented by the node (see Section 2.3). The dashed line shows the route of the brute-force search for a query string ‘LOL’, allowing at most one mismatch. Edge labels in squares mark the mismatches to the query in searching. The only hit is the bold node [1, 1] which represents string ‘GOL’.
Fig. 1. Prefix trie of string ‘GOOGOL’. Symbol ∧ marks the start of the string. The two numbers in a node give the SA interval of the string represented by the node (see Section 2.3). The dashed line shows the route of the brute-force search for a query string ‘LOL’, allowing at most one mismatch. Edge labels in squares mark the mismatches to the query in searching. The only hit is the bold node [1, 1] which represents string ‘GOL’.CC BY-NC · PubMed Central
Fig. 2. Constructing suffix array and BWT string for X=googol$. String X is circulated to generate seven strings, which are then lexicographically sorted. After sorting, the positions of the first symbols form the suffix array (6, 3, 0, 5, 2, 4, 1) and the concatenation of the last symbols of the circulated strings gives the BWT string lo$oogg.
Fig. 2. Constructing suffix array and BWT string for X=googol$. String X is circulated to generate seven strings, which are then lexicographically sorted. After sorting, the positions of the first symbols form the suffix array (6, 3, 0, 5, 2, 4, 1) and the concatenation of the last symbols of the circulated strings gives the BWT string lo$oogg.CC BY-NC · PubMed Central
Fig. 3. Algorithm for inexact search of SA intervals of substrings that match W. Reference X is $ terminated, while W is A/C/G/T terminated. Procedure InexactSearch(W, z) returns the SA intervals of substrings that match W with no more than z differences (mismatches or gaps); InexRecur(W, i, z, k, l) recursively calculates the SA intervals of substrings that match W[0, i] with no more than z differences on the condition that suffix Wi+1 matches interval [k, l]. Lines started with asterisk are for insertions to and deletions from X, respectively. D(i) is the lower bound of the number of differences in string W[0, i].
Fig. 3. Algorithm for inexact search of SA intervals of substrings that match W. Reference X is $ terminated, while W is A/C/G/T terminated. Procedure InexactSearch(W, z) returns the SA intervals of substrings that match W with no more than z differences (mismatches or gaps); InexRecur(W, i, z, k, l) recursively calculates the SA intervals of substrings that match W[0, i] with no more than z differences on the condition that suffix Wi+1 matches interval [k, l]. Lines started with asterisk are for insertions to and deletions from X, respectively. D(i) is the lower bound of the number of differences in string W[0, i].CC BY-NC · PubMed Central
Fig. 4. Equivalent algorithm to calculate D(i).
Fig. 4. Equivalent algorithm to calculate D(i).CC BY-NC · PubMed Central

Verification

Claims the paper makes

The claims and statistics of this paper haven’t been checked yet.

Run the check — free, no account needed. It reads the open-access text and checks the sources it cites.

A few free checks a day · papers already verified open instantly · results are public

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?

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

Show all 32 references

Cited by

Sorted by citations

Items 1,301–1,400 of 1,716

Related

See all

Metadata

Authors
Li, H., & Durbin, R.
Affiliations
Wellcome Sanger Institute (GB)
Corresponding author
Durbin, Richard
ORCID
Venue
Bioinformatics
Publisher
Oxford University Press (OUP)
Published
2009-05-18
Volume
25
Issue
14
Pages
1754-1760
ISSN
  • 1367-4803 (ISSN-L)
  • 1367-4811
DOI
10.1093/bioinformatics/btp324
PMC
PMC2705234
OpenAlex
W2103441770
Cited by
58,607
References
32
Citations by year
2026: 3541 · 2025: 4985 · 2024: 5800 · 2023: 5335 · 2022: 5575 · 2021: 5916 · 2020: 5161 · 2019: 4192 · 2018: 3819 · 2017: 3299 · 2016: 2900 · 2015: 2520 · 2014: 2193 · 2013: 1586 · 2012: 1007
FWCI
233.42
Type
journal article
Language
en
Open access
Licence
Locations
  • Bioinformatics (publishedVersion, cc-by-nc)
  • PubMed Central (publishedVersion, cc-by-nc)
  • PubMed (publishedVersion)
Funders
  • Wellcome Trust (077192/Z/05/Z)
  • Broad Institute
Topics
  • Life Sciences › Biochemistry, Genetics and Molecular Biology › Molecular Biology › Genomics and Phylogenetic Studies
  • Physical Sciences › Mathematics › Theoretical Computer Science › Algorithms and Data Compression
  • Life Sciences › Biochemistry, Genetics and Molecular Biology › Molecular Biology › Fractal and DNA sequence analysis
Keywords
short-read alignment, Burrows-Wheeler transform, BWA, gapped alignment, indels, backward search, variant calling, resequencing, human genome, DNA sequencing
MeSH terms
Algorithms, Software, Sequence Alignment, Sequence Analysis, DNA, Genomics

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