Source-linked AI summary
Aligning sequence reads, clone sequences and assembly contigs with BWA-MEM
Heng Li
TL;DR
Longer sequencing reads challenge aligners built for short, end-to-end mappings and require robust handling of gaps, local hits, and variable sequence lengths. BWA-MEM introduces a seed-and-extend aligner with adaptive local or end-to-end alignment, achieving fast, accurate mapping across reads from 70 bp to a few megabases.
Problem
Longer reads require aligners that handle gaps, multiple local hits, variable lengths, and structural variation more effectively than many existing mappers.
Method
BWA-MEM uses SMEM seeding, re-seeding, seed chaining, banded extension, and adaptive selection between local and end-to-end alignments.
Results
BWA-MEM is fast and accurate across 70 bp reads to sequences of a few megabases, with strong performance across simulated read-mapping tasks and long-read datasets.
Takeaways & Limitations
BWA-MEM provides a broadly applicable aligner for sequence reads, long queries, and contig alignment, including chimeric-read detection.
Abstract
from arXiv · showhide
Summary: BWA-MEM is a new alignment algorithm for aligning sequence reads or long query sequences against a large reference genome such as human. It automatically chooses between local and end-to-end alignments, supports paired-end reads and performs chimeric alignment. The algorithm is robust to sequencing errors and applicable to a wide range of sequence lengths from 70bp to a few megabases. For mapping 100bp sequences, BWA-MEM shows better performance than several state-of-art read aligners to date. Availability and implementation: BWA-MEM is implemented as a component of BWA, which is available at http://github.com/lh3/bwa. Contact: hengli@broadinstitute.org
Summary: · 1 INTRODUCTION
Short-read mappers were designed around 36bp reads, but longer and more variable sequences create alignment challenges. Existing algorithms have important speed, accuracy, and robustness limitations, motivating a new alignment algorithm.
- 1 INTRODUCTION: Most short-read mappers were developed when next-generation sequencing reads were about 36bp long.
- 1 INTRODUCTION: For 36bp reads, end-to-end alignment and reporting hits within specified Hamming or edit distances were reasonable requirements.
- 1 INTRODUCTION: Emerging technologies and improved chemistry produced reads that were no longer short, creating new alignment challenges for 100bp or longer reads.
- 1 INTRODUCTION: Several long-read alignment algorithms were developed, including BWA-SW, Bowtie2, Cushaw2, and GEM.
- 1 INTRODUCTION: BWA-SW is slower than Bowtie2 for 100bp reads at comparable accuracy and less accurate than Cushaw2 at comparable speed.
- 1 INTRODUCTION: Very few algorithms can align highly variable sequence lengths accurately while remaining robust to translocations in assemblies, motivating development of a new algorithm.
2 METHODS
BWA-MEM uses a seed-and-extend strategy built on SMEM seeding, reseeding, colinear seed chaining, and banded affine-gap dynamic programming. Its extension heuristics select between local and end-to-end alignments, while paired-end processing estimates insert-size distributions and scores candidate hit pairs.
- Seeding: BWA-MEM seeds alignments with supermaximal exact matches and introduces reseeding to reduce mismappings when true alignments lack SMEMs.SMEMs identify the longest exact match covering each query position.
- Seed chaining: Colinear, nearby seeds are greedily chained, and short chains largely contained in substantially longer chains are filtered before extension.By default, filtering removes chains that are both 50% and 38bp shorter than the long chain.
- Seed extension: Seeds are ranked by chain length and then seed length; contained seeds are dropped, while others undergo banded affine-gap dynamic-programming extension.Extension is attempted only when a seed may lead to a new alignment.
- Seed extension: BWA-MEM stops extension across poorly aligned regions using a score-drop cutoff and rejects some local alignments when end-reaching scores are sufficiently close, choosing local or end-to-end alignment automatically.The stopping criterion uses Z+|x−y|×pgapExt, where pgapExt is the gap extension penalty.
- Paired-end alignment: For paired-end reads, BWA-MEM estimates insert-size mean and variance from reliable single-end hits, rescues unmapped mates with Smith-Waterman alignment, and scores compatible hit pairs using insert-size probabilities.Mate rescue searches within [µ −4σ, µ + 4σ] windows for the top 100 hits by default.
3 RESULTS AND DISCUSSIONS
BWA-MEM provides accurate and fast alignment across short reads and sequences up to a few megabases, with strong performance on paired-end and long-read data. Its seeding, banded dynamic programming, and chimeric-read detection support efficient alignment across these query lengths.
- Simulated data: BWA-MEM is close to NovoAlign in accuracy for PE reads and comparable to GEM and Cushaw2 for SE reads.On the evaluated simulated data, NovoAlign had the best accuracy.
- Simulated data: 6 times as fast as Bowtie2 and Cushaw2 for a 650bp long-read data set, BWA-MEM had speed similar to GEM and Bowtie2 on the evaluated data.The sixfold comparison applies specifically to the 650bp long-read data set.
- Algorithmic performance: BWA-MEM’s advanced seeding identifies most standing seeds in one read pass, while banded dynamic programming guarantees linear time complexity in query length.Seeding is the bottleneck for short sequences, whereas banded dynamic programming is the bottleneck for long sequences.
- Algorithmic performance: BWA-MEM and BWA-SW identify chimeric reads, a crucial feature for contig alignment that most NGS long-read mappers lack.This capability is highlighted specifically in the context of contig alignment.
- Long-query alignment: 131 seconds versus nucmer’s 25 seconds, BWA-MEM aligned the 4.6Mb E. coli sequences and reported 104,321 substitutions, including 102,241 overlapping nucmer’s output.Nucmer reported 105,505 substitution differences; most substitutions unique to either aligner occurred in short, highly divergent regions, making the better aligner unclear.
- Applicability: BWA-MEM works well for both 70bp reads and long sequences up to a few megabases.The paper identifies BWA-MEM as a fast and accurate aligner across this range.