What do the symbols mean in minimap2's gap cost equation?

Question

Heng Li's paper on minimap2 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):

$$\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?

Answer 1

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.