Answers.Body: <p><strong>TL;DR:</strong></p>
  
  <p>BWA-backtrack is based on <a href="https://en.wikipedia.org/wiki/Backtracking" rel="noreferrer">backtracking</a>.
  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.</p>
  
  <p>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.</p>
  
  <p><strong>Long description:</strong></p>
  
  <p>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.</p>
  
  <p><a href="https://en.wikipedia.org/wiki/FM-index" rel="noreferrer">BWT-index</a> (and also other full-text indexes such as
  <a href="https://en.wikipedia.org/wiki/Suffix_array" rel="noreferrer">suffix arrays</a> or <a href="https://en.wikipedia.org/wiki/Suffix_tree" rel="noreferrer">suffix trees</a>)
  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.</p>
  
  <p><strong>BWA-backtrack</strong> looks for substrings of the reference, which would be similar
  to the entire read (end-to-end) using an algorithm
  called <a href="https://en.wikipedia.org/wiki/Backtracking" rel="noreferrer">backtracking</a>.
  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).</p>
  
  <p>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 <a href="http://bio-bwa.sourceforge.net/bwa.shtml" rel="noreferrer">BWA man page</a>)
  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).</p>
  
  <p>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 <a href="https://www.ncbi.nlm.nih.gov/pubmed/19451168" rel="noreferrer">paper</a>.</p>
  
  <p><strong>BWA-MEM</strong> 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.).</p>
  
Answers.ContentLicense: CC BY-SA 3.0
Answers.CreationDate: 2017-06-07T15:34:51.743Z
Answers.LastActivityDate: 2017-06-07T15:34:51.743Z
Answers.UserDisplayName: Karel Břinda
Answers.Body: <p>To quote the Introduction to <code>BWA</code> on <a href="http://bio-bwa.sourceforge.net/" rel="noreferrer">sourceforge</a>:</p>
  
  <blockquote>
    <p>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.</p>
  </blockquote>
  
  <p>In short, for anything where you have read lengths over 70bp BWA-MEM is faster, and more accurate.</p>
  
Answers.ContentLicense: CC BY-SA 3.0
Answers.CreationDate: 2017-05-17T15:31:16.567Z
Answers.Text: One important addition is that BWA-MEM will split reads more aggressively. Whereas BWA-ALN requires (if I remember correctly) one end-to-end alignment for anchoring, BWA-MEM allows for partial alignments.
  
  Practicable, use the `-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.
Answers.UserDisplayName: Manuel
Answers.ContentLicense: CC BY-SA 3.0
Answers.CreationDate: 2017-05-18T08:17:43.687Z
Answers.Text: @Manuel: What specific programs do you have in mind that need `-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 https://github.com/lh3/bwa/pull/26
Answers.UserDisplayName: John Marshall
Answers.ContentLicense: CC BY-SA 3.0
Answers.CreationDate: 2017-05-16T22:49:39.000Z
Answers.LastActivityDate: 2017-05-16T22:49:39.000Z
Answers.UserDisplayName: Michael Hall
Body: <p>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.</p>
  
  <p>What is the difference between BWA and BWA-MEM? And, in which instances would you employ one over the other?</p>
  
Comments.ContentLicense: CC BY-SA 3.0
Comments.CreationDate: 2017-06-07T16:10:47.377Z
Comments.Text: Possible duplicate: https://bioinformatics.stackexchange.com/questions/418/why-is-bwa-mem-the-standard-algorithm-when-using-bwa
Comments.UserDisplayName: morgantaschuk
Comments.ContentLicense: CC BY-SA 3.0
Comments.CreationDate: 2017-05-16T18:52:37.807Z
Comments.Text: You should read the [BWA](https://www.ncbi.nlm.nih.gov/pubmed/19451168) and [BWA mem](https://arxiv.org/abs/1303.3997) publications.
Comments.UserDisplayName: GWW
Comments.ContentLicense: CC BY-SA 3.0
Comments.CreationDate: 2017-05-16T22:06:50.380Z
Comments.Text: This paper: https://arxiv.org/abs/1303.3997
Comments.UserDisplayName: ShanZhengYang
Tags: <phylogenetics><bwa><read-mapping><reads>
Title: Difference between BWA-backtrack and BWA-MEM
ThreadText: # Difference between BWA-backtrack and BWA-MEM
  
  (Asked by: username_0 on 2017-05-16)
  
  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?
  
  **Tags:** phylogenetics, bwa, read-mapping, reads
  
  > **Comments:**
  > **username_2**: You should read the [BWA](https://www.ncbi.nlm.nih.gov/pubmed/19451168) and [BWA mem](https://arxiv.org/abs/1303.3997) publications.  
  > **username_3**: This paper: https://arxiv.org/abs/1303.3997  
  > **username_1**: Possible duplicate: https://bioinformatics.stackexchange.com/questions/418/why-is-bwa-mem-the-standard-algorithm-when-using-bwa  
  
  ---
  
  ## 2 answers
  
  ### Answer by username_4 on 2017-06-07. Score: 12
  
  **TL;DR:**
  
  BWA-backtrack is based on [backtracking](https://en.wikipedia.org/wiki/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](https://en.wikipedia.org/wiki/FM-index) (and also other full-text indexes such as
  [suffix arrays](https://en.wikipedia.org/wiki/Suffix_array) or [suffix trees](https://en.wikipedia.org/wiki/Suffix_tree))
  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](https://en.wikipedia.org/wiki/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](http://bio-bwa.sourceforge.net/bwa.shtml))
  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](https://www.ncbi.nlm.nih.gov/pubmed/19451168).
  
  **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.).
  
  
  ---
  
  ### Answer by username_5 on 2017-05-16. Score: 9
  
  To quote the Introduction to `BWA` on [sourceforge](http://bio-bwa.sourceforge.net/):
  
  > 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.
  
  > **Comments:**
  > **username_6**: One important addition is that BWA-MEM will split reads more aggressively. Whereas BWA-ALN requires (if I remember correctly) one end-to-end alignment for anchoring, BWA-MEM allows for partial alignments.  Practicable, use the `-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.  
  > **username_7**: @username_6: What specific programs do you have in mind that need `-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 https://github.com/lh3/bwa/pull/26  
  
  ---
  
  