Answers.Body: <p>Here is the translation:</p>
  
  <ul>
  <li><span class="math-container">$l$</span> = gap length</li>
  <li><span class="math-container">$q$</span> = initial gap penalty for <em>shorter</em> gaps</li>
  <li><span class="math-container">$e$</span> = <em>short</em> gap extension penalty per every additional gap</li>
  <li><span class="math-container">$\tilde{q}$</span> = initial gap penalty for <em>longer</em> gaps</li>
  <li><span class="math-container">$\tilde{e}$</span> = <em>long</em> gap extension penalty per every additional gap</li>
  </ul>
  
  <p>To understand the first of the two expressions being minimized, see the Wikipedia section on <a href="https://en.wikipedia.org/wiki/Gap_penalty#Affine" rel="noreferrer">affine gap penalties</a>.</p>
  
  <p>Notice the similar notation structure</p>
  
  <p><span class="math-container">$$A + B \cdot L$$</span></p>
  
  <p>where </p>
  
  <ul>
  <li><span class="math-container">$A$</span> is the known gap penalty,</li>
  <li><span class="math-container">$B$</span> is the gap extension penalty, and</li>
  <li><span class="math-container">$L$</span> is the length of the gap</li>
  </ul>
  
  <p>To understand the other variables with the tildes on top, see the text below Equation 2 (emphasis added to key explanation):</p>
  
  <blockquote>
    <p>On the condition that <span class="math-container">$e &gt; \tilde{e}$</span>⁠,
    it applies cost
    <span class="math-container">$q + |l| \cdot e$</span>
    to gaps shorter than
    <span class="math-container">$[(\tilde{q} - q)/(e - \tilde{e})]$</span>
    and applies
    <span class="math-container">$\tilde{q} + |l| \cdot \tilde{e}$</span>
    to longer gaps. <strong>This scheme helps to recover longer insertions and deletions (INDELs)</strong>.</p>
  </blockquote>
  
  <p>In other words, we make the assertion that we should penalize longer gaps differently than shorter gaps.</p>
  
  <p>As a bonus, here's a visual understanding of why we use the minimization function on those two expressions using Python and some made-up (and probably not biologically useful) penalty terms. <strong>Note</strong> the requirement that <span class="math-container">$e &gt; \tilde{e}$</span>.</p>
  
  <pre class="lang-py prettyprint-override"><code># Import libraries
  import numpy as np
  import matplotlib.pyplot as plt
  
  # Setup
  l = np.array(range(0, 15, 1))  
  y_short = eval('10 + 5*l') # Q=10, E=5
  y_long = eval('20 + 3*l')  # Q=20, E=3
  
  # Plot
  plt.plot(l, y_short)
  plt.plot(l, y_long)
  plt.legend(["Short Gap Penalty", "Long Gap Penalty"])
  </code></pre>
  
  <p><img src="https://i.sstatic.net/VZlcn.png" alt="Plot example expressions for long and short gap penalty expressions"></p>
  
  <p>Using our example and the expression <span class="math-container">$[(\tilde{q} - q)/(e - \tilde{e})]$</span>, it will apply the first expression in the minimization function (the one without the tildes) when the gap length is shorter than 5.</p>
  
  <p><span class="math-container">$$
  [(\tilde{q} - q)/(e - \tilde{e})]
  =
  [20 - 10)/(5 - 3)]
  =
  10 / 2
  = 5
  $$</span></p>
  
  <p>We can see from our plot that the two lines intersect at 5, which we've verified through some arithmetic.</p>
  
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2019-10-19T21:06:02.910Z
Answers.LastActivityDate: 2019-10-20T10:40:10.560Z
Answers.LastEditDate: 2019-10-20T10:40:10.560Z
Answers.UserDisplayName: Eric Leung
Body: <p>Heng Li's <a href="https://academic.oup.com/bioinformatics/article/34/18/3094/4994778" rel="nofollow noreferrer">paper on minimap2</a> is understandable to me right up until the moment that it gives this definition of gap cost:</p>
  
  <blockquote>
    <h3>2.2.1 Alignment with 2-piece affine gap cost</h3>
    
    <p>Minimap2 performs DP-based global alignment between adjacent anchors in a chain. It uses a 2-piece affine gap cost <a href="http://dx.doi.org/10.1007/BF02458577" rel="nofollow noreferrer">(Gotoh, 1990)</a>:</p>
    
    <p><span class="math-container">$$\gamma_a(l) = \min \{ q + |l| \cdot e, \tilde{q} + |l| \cdot \tilde{e} \}$$</span></p>
  </blockquote>
  
  <p>Suddenly, out of nowhere, we've got <em>five</em> variables used without prior introduction: <span class="math-container">$l$</span>, <span class="math-container">$q$</span>, <span class="math-container">$e$</span>, <span class="math-container">$\tilde{q}$</span>, and <span class="math-container">$\tilde{e}$</span>.</p>
  
  <p>Heng doesn't state their meanings, and based on a quick skim and text search of the cited paper by Gotoh, that paper doesn't use these variable names anywhere either.</p>
  
  <p>What does this equation mean?</p>
  
Tags: <phylogenetics><read-mapping><minimap2>
Title: What do the symbols mean in minimap2's gap cost equation?
ThreadText: # What do the symbols mean in minimap2's gap cost equation?
  
  (Asked by: username_0 on 2019-10-15)
  
  Heng Li's [paper on minimap2](https://academic.oup.com/bioinformatics/article/34/18/3094/4994778) is understandable to me right up until the moment that it gives this definition of gap cost:
  
  > ### 2.2.1 Alignment with 2-piece affine gap cost
  >
  > Minimap2 performs DP-based global alignment between adjacent anchors in a chain. It uses a 2-piece affine gap cost [(Gotoh, 1990)](http://dx.doi.org/10.1007/BF02458577):
  >
  > $$\gamma\_a(l) = \min \{ q + |l| \cdot e, \tilde{q} + |l| \cdot \tilde{e} \}$$
  
  Suddenly, out of nowhere, we've got *five* variables used without prior introduction: $l$, $q$, $e$, $\tilde{q}$, and $\tilde{e}$.
  
  Heng doesn't state their meanings, and based on a quick skim and text search of the cited paper by Gotoh, that paper doesn't use these variable names anywhere either.
  
  What does this equation mean?
  
  **Tags:** phylogenetics, read-mapping, minimap2
  
  
  ---
  
  ## 1 answers
  
  ### Answer by username_1 on 2019-10-19. Score: 5
  
  Here is the translation:
  
  * $l$ = gap length
  * $q$ = initial gap penalty for *shorter* gaps
  * $e$ = *short* gap extension penalty per every additional gap
  * $\tilde{q}$ = initial gap penalty for *longer* gaps
  * $\tilde{e}$ = *long* gap extension penalty per every additional gap
  
  To understand the first of the two expressions being minimized, see the Wikipedia section on [affine gap penalties](https://en.wikipedia.org/wiki/Gap_penalty#Affine).
  
  Notice the similar notation structure
  
  $$A + B \cdot L$$
  
  where
  
  * $A$ is the known gap penalty,
  * $B$ is the gap extension penalty, and
  * $L$ is the length of the gap
  
  To understand the other variables with the tildes on top, see the text below Equation 2 (emphasis added to key explanation):
  
  > On the condition that $e > \tilde{e}$⁠,
  > it applies cost
  > $q + |l| \cdot e$
  > to gaps shorter than
  > $[(\tilde{q} - q)/(e - \tilde{e})]$
  > and applies
  > $\tilde{q} + |l| \cdot \tilde{e}$
  > to longer gaps. **This scheme helps to recover longer insertions and deletions (INDELs)**.
  
  In other words, we make the assertion that we should penalize longer gaps differently than shorter gaps.
  
  As a bonus, here's a visual understanding of why we use the minimization function on those two expressions using Python and some made-up (and probably not biologically useful) penalty terms. **Note** the requirement that $e > \tilde{e}$.
  
  ```py
  # Import libraries
  import numpy as np
  import matplotlib.pyplot as plt
  
  # Setup
  l = np.array(range(0, 15, 1))  
  y_short = eval('10 + 5*l') # Q=10, E=5
  y_long = eval('20 + 3*l')  # Q=20, E=3
  
  # Plot
  plt.plot(l, y_short)
  plt.plot(l, y_long)
  plt.legend(["Short Gap Penalty", "Long Gap Penalty"])
  
  ```
  
  ![Plot example expressions for long and short gap penalty expressions](https://i.sstatic.net/VZlcn.png)
  
  Using our example and the expression $[(\tilde{q} - q)/(e - \tilde{e})]$, it will apply the first expression in the minimization function (the one without the tildes) when the gap length is shorter than 5.
  
  $$
  [(\tilde{q} - q)/(e - \tilde{e})]
  =
  [20 - 10)/(5 - 3)]
  =
  10 / 2
  = 5
  $$
  
  We can see from our plot that the two lines intersect at 5, which we've verified through some arithmetic.
  
  
  ---
  
  