Bioinformatics Stack Exchange is a question and answer site for researchers, developers, students, teachers, and end users interested in bioinformatics. It only takes a minute to sign up.
Sign up to join this community
Many of my colleagues recommend I use BWA-MEM instead of regular old BWA. The problem is I don't understand why and reading the BWA man page doesn't seem to help the matter.
What is the difference between BWA and BWA-MEM? And, in which instances would you employ one over the other?
TL;DR:
BWA-backtrack is based on backtracking. This approach is appropriate only when the dissimilarity between the reads and the reference is low, or when you want to find all best hits or enumerate all possible alignments up to a specified number of errors.
In all other situations, BWA-MEM is preferable as it can, thanks to its sophisticated strategy based on maximum exact matches, deal with errors better and also automatically switch between local and global alignment modes.
Long description:
I would like to provide some algorithmic insight since I believe that it can be very useful in this case. Both BWA-backtrack and BWA-MEM use the same indexing strategy (heavily relying on BWT-index), but the actual algorithms are quite different.
BWT-index (and also other full-text indexes such as suffix arrays or suffix trees) can easily find exact matches (imagine Ctrl+F-like search in a text editor), but any differences between the read and the reference, such as sequencing errors or genomic variants, make the situation complicated. One then needs to somehow transform inexact matching to exact matching, and all three BWA mappers (note that there exists also BWA-SW, but it is deprecated) use quite different strategies.
BWA-backtrack looks for substrings of the reference, which would be similar to the entire read (end-to-end) using an algorithm called backtracking. First, it searches occurences of the read without any "corrections". If nothing found, it consideres all possible single edits; then two edits, etc. To make mapping efficient, one usually wants to stop with the first found alignment as this would be the best one. When required, it is also possible to find the other equally good alignments or to enumerate all alignments up to some edit distance or withing some divergance rate (see the -N option of BWA-backtrack).
It turns out that the time required for finding an alignment can be exponential in the number of errors, which is probably the main problem of backtracking-based approaches. To prevent huge overheads due to dissimilar reads, one needs to limit the number of allowed errors to some reasonable number (see maxDiff in the BWA man page) and consider the other reads unaligned. In the case of BWA-backtrack, the minimum required identity level is ~97% with the default options (see the -n option).
In fact, the algorithm is more complicated and uses various heuristics such as seed-and-extend or Z-dropoff in order to make the computation fast enough (at the price of lower accuracy). If you are interested in more details, all these tricks are well described in the paper.
BWA-MEM uses quite a different strategy. It detects long exact matches between the read and the reference, and then chains them into local or global alignments, based on what is more appropriate in that specific case. Such an automatic local-global switching can be very powerful and BWA-MEM works well with various types of data (short reads, long reads, low error rates, high error rates, etc.).
To quote the Introduction to BWA on sourceforge:
BWA is a software package for mapping low-divergent sequences against a large reference genome, such as the human genome. It consists of three algorithms: BWA-backtrack, BWA-SW and BWA-MEM. The first algorithm is designed for Illumina sequence reads up to 100bp, while the rest two for longer sequences ranged from 70bp to 1Mbp. BWA-MEM and BWA-SW share similar features such as long-read support and split alignment, but BWA-MEM, which is the latest, is generally recommended for high-quality queries as it is faster and more accurate. BWA-MEM also has better performance than BWA-backtrack for 70-100bp Illumina reads.
In short, for anything where you have read lengths over 70bp BWA-MEM is faster, and more accurate.
-M flag for bwa mem if you are processing the alignments with older or less mainstream programs if they don't understand the BAM supplementary read flag yet.
$\endgroup$
-M? That flag was added for use with Picard < 1.96, which is now ancient — Picard itself hasn't benefited from or needed this flag for four years now. See also github.com/lh3/bwa/pull/26
$\endgroup$
May 18, 2017 at 8:17