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.
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
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
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.).