text: user425: Is there any resource (paper, blogpost, Github gist, etc.) describing the BWA-MEM algorithm for assigning mapping qualities? I vaguely remember that I have somewhere seen a formula for SE reads, which looked like
  $C * (s_1 - s_2) / s_1,$
  where $s_1$ and $s_2$ denoted the alignment scores of two best alignments and C was some constant.
  I believe that a reimplementation of this algorithm in some scripting language could be very useful for the bioinfo community. For instance, I sometimes test various mapping methods and some of them tend to find good alignments, but fail in assigning appropriate qualities. Therefore, I would like to re-assign all the mapping qualities in a SAM file with the BWA-MEM algorithm.
  Btw. This algorithm must already have been implemented outside BWA, see the BWA-MEM paper: 
  
  GEM does not compute mapping quality. Its
    mapping quality is estimated with a BWA-like algorithm with suboptimal
    alignments available.
  
  Unfortunately, the BWA-MEM paper repo contains only the resulting .eval files.
  Update: The question is not about the algorithm for computing alignment scores. Mapping qualities and alignment scores are two different things:
  
  Alignment score quantifies the similarity between two sequences (e.g., a read and a reference sequence)
  Mapping quality (MAQ) quantifies the probability that a read is aligned to a wrong position.
  
  Even alignments with high scores can have a very low mapping quality.
  
  user57: Yes, there bwa-mem was published as a preprint
  
  BWA-MEM’s seed extension differs from the standard seed extension in two aspects. Firstly, suppose at a certain extension step we come to reference
    position x with the best extension score achieved at query position y.
  ...
  Secondly, while extending a seed, BWA-MEM tries to keep track of the
    best extension score reaching the end of the query sequence
  
  And there is a description of the scoring algorithm directly in the source code of bwa-mem (lines 22 - 44), but maybe the only solution is really to go though the source code.
  
original_text: 425: <p>Is there any resource (paper, blogpost, Github gist, etc.) describing the BWA-MEM algorithm for assigning mapping qualities? I vaguely remember that I have somewhere seen a formula for SE reads, which looked like</p>
  
  <p>$C * (s_1 - s_2) / s_1,$</p>
  
  <p>where $s_1$ and $s_2$ denoted the alignment scores of two best alignments and <code>C</code> was some constant.</p>
  
  <p>I believe that a reimplementation of this algorithm in some scripting language could be very useful for the bioinfo community. For instance, I sometimes test various mapping methods and some of them tend to find good alignments, but fail in assigning appropriate qualities. Therefore, I would like to re-assign all the mapping qualities in a SAM file with the BWA-MEM algorithm.</p>
  
  <p>Btw. This algorithm must already have been implemented outside BWA, see the BWA-MEM paper: </p>
  
  <blockquote>
    <p>GEM does not compute mapping quality. Its
    mapping quality is estimated with a BWA-like algorithm with suboptimal
    alignments available.</p>
  </blockquote>
  
  <p>Unfortunately, the <a href="https://github.com/lh3/mem-paper/" rel="noreferrer">BWA-MEM paper repo</a> contains only the resulting <code>.eval</code> files.</p>
  
  <p><strong>Update:</strong> The question is <em>not</em> about the algorithm for computing alignment scores. Mapping qualities and alignment scores are two different things:</p>
  
  <ul>
  <li>Alignment score quantifies the similarity between two sequences (e.g., a read and a reference sequence)</li>
  <li>Mapping quality (MAQ) quantifies the probability that a read is aligned to a wrong position.</li>
  </ul>
  
  <p>Even alignments with high scores can have a very low mapping quality.</p>
   57: <p>Yes, there bwa-mem was published as a <a href="https://arxiv.org/pdf/1303.3997.pdf" rel="nofollow noreferrer">preprint</a></p>
  
  <blockquote>
    <p>BWA-MEM’s seed extension differs from the standard seed extension in two aspects. Firstly, suppose at a certain extension step we come to reference
    position x with the best extension score achieved at query position y.</p>
    
    <p>...</p>
    
    <p>Secondly, while extending a seed, BWA-MEM tries to keep track of the
    best extension score reaching the end of the query sequence</p>
  </blockquote>
  
  <p>And there is a description of the scoring algorithm directly in the source code of <a href="https://github.com/lh3/bwa/blob/master/bwamem.c" rel="nofollow noreferrer">bwa-mem</a> (lines 22 - 44), but maybe the only solution is really to go though the source code.</p>
  