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

CC BY-SA 4.0
2019-10-19T21:06:02.910Z
2019-10-20T10:40:10.560Z
2019-10-20T10:40:10.560Z
Eric Leung
<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>

<phylogenetics><read-mapping><minimap2>
What do the symbols mean in minimap2's gap cost equation?
# 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.
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}$.
# 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"])


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.


---

