A cell that has to know where it is

Under the unit cost model a gap of four characters costs four, because it is four insertions. Under almost any account of how two strings came to differ, it is one event: a stretch went missing, or a stretch was added, and the length of it is a detail of the same event rather than four separate ones.

An affine gap charge says that directly. A gap of $k$ characters costs

$$\gamma(k) = o + e \cdot k$$

— an opening price $o$ paid once, and an extension price $e$ paid per character. Set $o = 0$ and it is the linear charge every earlier table on this site used. Set $o = 8$ and $e = 1$ and a gap of four costs 12 where four separate gaps of one cost 36.

That looks like a change to one constant. It is a change to what a cell has to know.

Why one table cannot do it #

Consider a cell $(i, j)$ reached by putting a gap character in the lower string — stepping down from $(i-1, j)$. What does that step cost?

If the step into $(i-1, j)$ was also a downward step, the gap is already open and this character costs $e$. If it was a diagonal step, the gap starts here and the character costs $o + e$.

So the price of the step depends on how its predecessor was reached, and the cell at $(i-1, j)$ holds a number. It holds the cheapest way to get there, and the cheapest way to get there may well be a route that leaves the gap closed, at a total that is lower by less than $o$. A single-table recurrence has no way to ask the question and no way to pay for the answer.

The repair is to stop asking a cell for one number. Keep three:

• $M(i,j)$ — the cheapest way to reach $(i,j)$ having just aligned two characters;
• $D(i,j)$ — the cheapest way, having just extended a gap downwards;
• $I(i,j)$ — the cheapest way, having just extended one rightwards.

Write $B(i,j)$ for the cheapest way to reach a cell by any of the three routes — the minimum of the three tables there. Then

$$\begin{aligned} M(i,j) &= B(i-1,\,j-1) + s(a_i, b_j) \\ D(i,j) &= \min\{M(i-1,j) + o + e,\; D(i-1,j) + e\} \\ I(i,j) &= \min\{M(i,j-1) + o + e,\; I(i,j-1) + e\} \end{aligned}$$

Read the second line: opening a gap from a matched state costs $o + e$; continuing one from a gap state costs $e$. The third coordinate — which of the three — is exactly the fact a single number could not carry.

What it costs, exactly #

Three tables over the same rectangle, so three times the cells:

Seven rather than three, because $M$ takes a minimum over three predecessors and $D$ and $I$ take a minimum over two each.

Neither number changes the exponent. Both are $\Theta(nm)$, both grow the same way, and a statement that affine gaps are asymptotically free is correct.

Three times the memory is not free on a real problem. Aligning two sequences of thirty thousand characters is nine hundred million cells at one table and 2.7 billion at three, and the difference between those two numbers is the difference between a machine that can do it and one that cannot. Which is why the linear-space methods matter more here than they did with one table, and why they carry over: a rolling frontier keeps three rows instead of one, and the divide-and-conquer construction keeps three lines instead of one.

The version everybody writes first #

There is a shortcut, it is the natural thing to try, and it is worth taking seriously because it is not a bug. Charge every gap character $o + e$ in a single table:

$$D(i,j) = D(i-1,j) + (o + e)$$

This is a valid cost model. It is simply a different one — a linear charge at a higher rate, in which a gap of four costs four times what a gap of one costs. On any pair whose gaps are all of length one it agrees with the affine model exactly, which is why it survives casual testing.

On a pair with a real gap it does not agree, and it goes wrong in two ways at once.

The number is more than twice as large: 39 against 19. That much is expected — the flat charge is dearer per character by construction.

The shape is the part worth noticing. Under the flat charge every gap character costs 9 whatever its neighbours are doing, so nothing in the arithmetic prefers one run of four to three runs of one and two. The optimum is genuinely degenerate between them, the tie-break decides, and what comes out is a scattered alignment. Under the affine charge one run of four costs 12 and three runs costing $8 + k$ each cost 28, so the arithmetic prefers the single run and there is nothing for a tie-break to decide.

That is the practical difference. The wrong version does not merely mis-price an alignment; it stops preferring the alignment the model was introduced to prefer.

This site’s gate carries the discrepancy as a rejection rather than as a measurement. A run charging every gap character the opening price must report a total above the affine one and an alignment with more gap runs, or the check has stopped working.

The infinities are load-bearing #

Three tables need three sets of boundary values, and two of the three are unreachable states rather than cheap ones.

$M(0,j)$ asks the cost of reaching column $j$ of the top row having just aligned two characters — and no characters have been aligned. It is not zero. It is not $j \cdot e$. It is impossible, and it has to be represented as something no minimum will ever choose.

This matters more than it sounds. The tables field’s own rule is that a cell which has not been computed must be distinguishable from a cell holding zero, because a zero absorbed into a minimum produces a smooth wrong curve rather than a crash. The same failure is available here one level up: initialise $M(0,j)$ to zero and the table will cheerfully report that a gap costs nothing provided it starts at the beginning, and the answer will look plausible on every pair whose optimal alignment does not begin with a gap.

So the corner is read as $B(m,n)$ — the cheapest of the three states the alignment could end in — and the three boundaries are three different statements about what is reachable.

The traceback has to know too #

Recovering the alignment is where the three tables stop being an implementation detail.

A traceback over a single table asks, at each cell, which predecessor’s value plus the step cost equals this cell’s value. Over three tables the same question needs the third coordinate: from $D(i,j)$ the predecessor is $D(i-1,j)$ if the gap was already open and $M(i-1,j)$ if it was not, and the two are distinguished by which of $D(i-1,j) + e$ and $M(i-1,j) + o + e$ achieved the minimum.

A traceback that consults only the cell-wise minimum gets this wrong in a specific and quiet way: it re-derives the gap opening cost at every step of a run, finds that the arithmetic does not close, and falls through to whichever branch its final else names. The alignment it returns is a legal alignment and its cost is not the number the table reported.

What the two parameters do #

The opening price and the extension price are two numbers and their ratio is what matters — the same observation as the ratio between a substitution and a gap, one level along.

Swept properly, the opening price does its work in a narrow band and then stops:

Three things are visible in that table and only one of them is obvious.

The obvious one is that the answer climbs — of course it does, the gaps are getting dearer.

The second is that the number of gap characters never moves. It is four at every setting, and it has to be: these strings differ in length by four, so four gap characters are forced by arithmetic and no cost model can avoid them. What the opening price buys is not fewer gap characters but fewer runs of them, and it buys the last of that by $o = 3$.

The third is that beyond $o = 4$ nothing changes at all except the total. The alignment is frozen, the ties are gone, and every further increase is a scale factor on a decision that has already been made. A parameter sweep that reported only the answer would show a straight line climbing forever and would show none of this.

At $o = 0$ the three tables collapse: $D$ and $I$ become $M$ plus a constant per step and the whole construction is the ordinary one doing three times the work for nothing. At $o$ very large, gaps stop being used at all and the alignment becomes a straight diagonal with substitutions everywhere — the same degenerate edge the substitution-against-gap ratio has, reached from the other side.

Between the two there is a range in which the model is doing what it was introduced to do, and where that range sits depends on the substitution costs, because a gap competes against a substitution and not against nothing.

Three tables, one set of rules about reading them #

The ordering discipline the tables field enforces — a cell may be written once, may not be read before it is written, and raises a different error when it is read after being released — applies across all three tables here, and it catches one thing it could not catch with one.

$M(i,j)$ reads three cells at $(i-1,j-1)$, one from each table. $D(i,j)$ reads two at $(i-1,j)$. $I(i,j)$ reads two at $(i,j-1)$. Fill the three tables in the wrong interleaving — all of $M$, then all of $D$, then all of $I$ — and every one of those reads is a read of a cell that has not been written yet, and the discipline says so at the first one.

Against three zero-filled arrays it would say nothing. It would report a smaller answer, because a zero absorbed into a minimum is always an improvement, and the answer would be smaller by an amount that depends on the strings. That is the exact failure mode the tables field was built around, and having three tables instead of one multiplies the number of ways to arrive at it rather than reducing them.

The opening charge is a parameter, and moving it moves the answer without moving anything about the machinery. Charge 3 to open rather than 8, on the same pair and through the same three tables: the cells and the transitions are the same numbers, because the shape of the computation is set by the rectangle rather than by the prices in it.

The gaps at the ends are not events #

There is a second thing an affine model is usually asked for and it is not in the recurrence above: the gaps at the two ends should be free.

The reason is the same reason the opening price exists. A short sequence compared against a long one — a read against a reference, a quotation against a document, a fragment against a whole — is not a shorter version of the long one with material deleted. It is a piece of it. The characters of the reference before and after the piece were never removed by any event; they are simply outside the comparison, and charging $o + e k$ for each end is charging for two events that did not happen.

The repair is a boundary condition rather than a fourth table, and it is exactly the manoeuvre zeroing the top row performs on the unit-cost table, done twice and in the right state. Let the leading gap be entered for nothing — initialise the appropriate gap table’s boundary to zero rather than to $o + ek$ — and read the answer as the best cell along the final row or column rather than at the corner, so the trailing gap is unpaid too.

Which boundary and which table is where this goes wrong, and the failure is the quiet kind.

Zeroing the gap state’s boundary is correct: it says a run of leading gap characters is free, and the alignment proper begins when the first characters are matched. Zeroing the matched state’s boundary instead says something quite different — that an alignment may restart at any column with no penalty — and since that boundary is the one an implementer reaches for first, by analogy with the unit-cost table where there is only one, the mistake is easy to make and produces a table that quietly answers the local-alignment question instead.

Both tables produce plausible numbers on a pair whose match is in the middle. They diverge on a pair with two separated similar regions, where the correct semi-global answer must choose one and the accidental local one stitches both together across a free gap. Three of these four things are one-line edits to a boundary and each of them names a different problem, which is the same finding the unit-cost table produced and is worth having twice, because with three tables there are three times as many boundaries to get wrong.

The number of tables is the model’s state count #

Standing back from Gotoh’s construction, the shape of it is more general than the affine model and worth naming, because it says immediately what any new gap rule will cost.

The single-table recurrence assumes the price of a step depends only on where the step goes. The affine rule breaks that: a step’s price depends on what the previous step was. So the alignment is not a path through a grid any more — it is a path through a grid crossed with a small automaton, whose states are matched, in a downward gap and in a rightward gap, and whose transitions carry the prices. Three states, three tables, and the recurrence above is that automaton written out.

Read that way, three things follow without any further argument.

The cell count is the grid times the state count. Three states, three times the cells; and the transition count per cell is the automaton’s in-degree, which is why it is seven rather than three. Nothing about this is specific to gaps.

A richer gap rule costs states, not classes. Modern aligners use a two-piece rule — one affine charge for short gaps and a second, cheaper-per-character one for long ones — because a single line does not fit both a three-character indel and a ten-thousand-character structural variant. That is five states rather than three, so five tables, and every property in this essay carries over unchanged with a five in place of a three. The class is untouched, the constant is nearly doubled, and the alignment stops fragmenting a second kind of gap.

And a general gap function has an unbounded state count, which is exactly why it does not fit. Knowing how much a step costs requires knowing how long the current run is, the run can be as long as the string, and an automaton with $n$ states over a grid of $nm$ cells is the $\Theta(nm(n+m))$ the next section names. The concave and convex methods escape not by shrinking the automaton but by refusing to enumerate its states, which is a different kind of move and is why they need their own machinery.

The transferable rule is compact enough to carry to any recurrence at all: a dynamic program’s table count is the number of things a cell must remember besides where it is, and the moment a cost depends on how a cell was reached, that number is at least two.

Where affine stops #

Affine is not the general case. It is the largest family of gap costs that fits in a constant number of tables, and that is why it is the one everybody uses.

A general gap function $\gamma(k)$ — anything that is not $o + ek$ — brings back the problem the three tables solved, because a cell would need to know not merely whether it is inside a gap but how long the gap has been going. Written naively that is a minimum over all $k$ at every cell, which turns $\Theta(nm)$ into $\Theta(nm(n+m))$: on two strings of three hundred characters, about twenty-seven million transitions instead of a hundred and eighty thousand.

There are better methods for the concave and convex cases, which exploit the shape of $\gamma$ to keep a candidate list per row rather than reconsidering every $k$. They are real, they are not implemented here, and quoting their bounds beside measured numbers would be mixing two kinds of statement — so this is a boundary of what this collection has measured rather than a boundary of what is known.

What is measured is the shape of the trade at the point everybody sits on: three times the cells, seven transitions instead of three per cell, no change to the class, and an alignment that stops fragmenting. The first three are prices and the last is the reason to pay them.