Fast and Accurate Long-read Alignment with Burrows-Wheeler Transform

Overview

Journal Bioinformatics

Publisher Oxford University Press

Specialty Biology

Date 2010 Jan 19

PMID 20080505

Citations 6280

Authors

Heng Li

Richard Durbin

Affiliations

Soon will be listed here.

Abstract

Motivation: Many programs for aligning short sequencing reads to a reference genome have been developed in the last 2 years. Most of them are very efficient for short reads but inefficient or not applicable for reads >200 bp because the algorithms are heavily and specifically tuned for short queries with low sequencing error rate. However, some sequencing platforms already produce longer reads and others are expected to become available soon. For longer reads, hashing-based software such as BLAT and SSAHA2 remain the only choices. Nonetheless, these methods are substantially slower than short-read aligners in terms of aligned bases per unit time.

Results: We designed and implemented a new algorithm, Burrows-Wheeler Aligner's Smith-Waterman Alignment (BWA-SW), to align long sequences up to 1 Mb against a large sequence database (e.g. the human genome) with a few gigabytes of memory. The algorithm is as accurate as SSAHA2, more accurate than BLAT, and is several to tens of times faster than both.

Availability: http://bio-bwa.sourceforge.net

Citing Articles

Structural basis of thymidine-rich DNA recognition by Drosophila P75 PWWP domain.

Jin Z, Meng Z, Liu Y, Li C, Zhang X, Yin Y Commun Biol. 2025; 8(1):445.

PMID: 40089621 DOI: 10.1038/s42003-025-07895-2.

Proteogenomic characterization of molecular and cellular targets for treatment-resistant subtypes in locally advanced cervical cancers.

Hyeon D, Nam D, Shin H, Jeong J, Jung E, Cho S Mol Cancer. 2025; 24(1):77.

PMID: 40087745 DOI: 10.1186/s12943-025-02256-3.

Contributions of interspecific hybrids to genetic variability in Glycyrrhiza uralensis and G. glabra.

Kim J, Lee J, Kang J, Shim H, Kang D, Lee S Sci Rep. 2025; 15(1):8764.

PMID: 40082484 PMC: 11906797. DOI: 10.1038/s41598-025-92115-4.

Chromosome-level genome assembly of the spangled emperor, Lethrinus nebulosus (Forsskål 1775).

Parata L, Anstiss L, de Jong E, Doran A, Edwards R, Newman S Sci Data. 2025; 12(1):435.

PMID: 40082478 PMC: 11906739. DOI: 10.1038/s41597-025-04690-w.

Flax domesticationprocesses as inferred from genome-wide SNP data.

Fu Y Sci Rep. 2025; 15(1):8731.

PMID: 40082459 PMC: 11906640. DOI: 10.1038/s41598-025-89498-9.

References

Ning Z, Cox A, Mullikin J . SSAHA: a fast search method for large DNA databases. Genome Res. 2001; 11(10):1725-9. PMC: 311141. DOI: 10.1101/gr.194201. View

Li H, Durbin R . Fast and accurate short read alignment with Burrows-Wheeler transform. Bioinformatics. 2009; 25(14):1754-60. PMC: 2705234. DOI: 10.1093/bioinformatics/btp324. View

Weese D, Emde A, Rausch T, Doring A, Reinert K . RazerS--fast read mapping with sensitivity control. Genome Res. 2009; 19(9):1646-54. PMC: 2752123. DOI: 10.1101/gr.088823.108. View

Morgulis A, Coulouris G, Raytselis Y, Madden T, Agarwala R, Schaffer A . Database indexing for production MegaBLAST searches. Bioinformatics. 2008; 24(16):1757-64. PMC: 2696921. DOI: 10.1093/bioinformatics/btn322. View

Langmead B, Trapnell C, Pop M, Salzberg S . Ultrafast and memory-efficient alignment of short DNA sequences to the human genome. Genome Biol. 2009; 10(3):R25. PMC: 2690996. DOI: 10.1186/gb-2009-10-3-r25. View

Rumble S, Lacroute P, Dalca A, Fiume M, Sidow A, Brudno M . SHRiMP: accurate mapping of short color-space reads. PLoS Comput Biol. 2009; 5(5):e1000386. PMC: 2678294. DOI: 10.1371/journal.pcbi.1000386. View

Lam T, Sung W, Tam S, Wong C, Yiu S . Compressed indexing and local alignment of DNA. Bioinformatics. 2008; 24(6):791-7. DOI: 10.1093/bioinformatics/btn032. View

Altschul S, Madden T, Schaffer A, Zhang J, Zhang Z, Miller W . Gapped BLAST and PSI-BLAST: a new generation of protein database search programs. Nucleic Acids Res. 1997; 25(17):3389-402. PMC: 146917. DOI: 10.1093/nar/25.17.3389. View

Zhang Z, Schwartz S, Wagner L, Miller W . A greedy algorithm for aligning DNA sequences. J Comput Biol. 2000; 7(1-2):203-14. DOI: 10.1089/10665270050081478. View

10.

Lin H, Zhang Z, Zhang M, Ma B, Li M . ZOOM! Zillions of oligos mapped. Bioinformatics. 2008; 24(21):2431-7. PMC: 2732274. DOI: 10.1093/bioinformatics/btn416. View

11.

Li H, Handsaker B, Wysoker A, Fennell T, Ruan J, Homer N . The Sequence Alignment/Map format and SAMtools. Bioinformatics. 2009; 25(16):2078-9. PMC: 2723002. DOI: 10.1093/bioinformatics/btp352. View

12.

Eid J, Fehr A, Gray J, Luong K, Lyle J, Otto G . Real-time DNA sequencing from single polymerase molecules. Science. 2008; 323(5910):133-8. DOI: 10.1126/science.1162986. View

13.

Pearson W, Lipman D . Improved tools for biological sequence comparison. Proc Natl Acad Sci U S A. 1988; 85(8):2444-8. PMC: 280013. DOI: 10.1073/pnas.85.8.2444. View

14.

Smith A, Xuan Z, Zhang M . Using quality scores and longer reads improves accuracy of Solexa read mapping. BMC Bioinformatics. 2008; 9:128. PMC: 2335322. DOI: 10.1186/1471-2105-9-128. View

15.

Ma B, Tromp J, Li M . PatternHunter: faster and more sensitive homology search. Bioinformatics. 2002; 18(3):440-5. DOI: 10.1093/bioinformatics/18.3.440. View

16.

Li R, Li Y, Kristiansen K, Wang J . SOAP: short oligonucleotide alignment program. Bioinformatics. 2008; 24(5):713-4. DOI: 10.1093/bioinformatics/btn025. View

17.

Jiang H, Wong W . SeqMap: mapping massive amount of oligonucleotides to the genome. Bioinformatics. 2008; 24(20):2395-6. PMC: 2562015. DOI: 10.1093/bioinformatics/btn429. View

18.

Li H, Ruan J, Durbin R . Mapping short DNA sequencing reads and calling variants using mapping quality scores. Genome Res. 2008; 18(11):1851-8. PMC: 2577856. DOI: 10.1101/gr.078212.108. View

19.

Kent W . BLAT--the BLAST-like alignment tool. Genome Res. 2002; 12(4):656-64. PMC: 187518. DOI: 10.1101/gr.229202. View