A cost that is not one

Every distance on this site so far has charged one for an insertion, one for a deletion and one for a substitution. Every one of them. It is such a natural thing to do that it is easy to miss that it is a decision, and that it is the only decision under which the answer is a count of anything at all.

Take two strings of eight characters and fill the same eighty-one cells four times, changing nothing but what a change costs:

The two tens are not the same number. One counts a substitution as one or two according to which pair of symbols it is; the other is a sum of logarithms and is measured in bits. Nothing in the arithmetic distinguishes them, and a plate that printed distance 10 without naming the model would be printing something that is not a quantity.

What unit cost assumes #

It is worth stating the assumption plainly, because it is invisible in the recurrence.

$$D(i,j) = \min\begin{cases} D(i-1,j-1) + [a_i \ne b_j] \\ D(i-1,j) + 1 \\ D(i,j-1) + 1 \end{cases}$$

The bracket is an indicator: one when the characters differ, zero when they agree. Written this way the model is a single character of notation, and what it claims is that every substitution is equally surprising. Reading a g where an a was expected costs exactly what reading a q where an a was expected costs. So does every insertion, and so does every deletion, and an insertion costs the same as a substitution.

For the case the measure was invented for — one keystroke wrong in a short word — that is defensible and works well. For almost everything else it is a claim nobody would make out loud. A single mutation in a nucleotide sequence is far more likely to swap one purine for the other than to swap a purine for a pyrimidine; a single slip at a keyboard is far more likely to hit a neighbouring key than a distant one; and a gap of four characters in a text is usually one event rather than four.

The first two are about the substitution rule and are this essay’s subject. The third is about the gap rule and needs three tables rather than one.

Where a matrix comes from #

Published substitution matrices exist, they are good, and quoting one here would be useless — a number copied out of a table is a number this collection cannot check, and every claim on these pages is supposed to be recomputable from a rule written beside it.

So the matrices here are derived. State a mutation process and let the arithmetic produce the costs:

A symbol drifts by a random walk. At each step it stays where it is with a stated probability and otherwise moves to another symbol, with a weight $w$ times higher for a neighbour — which for nucleotides means the other member of its purine or pyrimidine pair, and for a typed letter means a key adjacent on the keyboard. Run the walk for one step, compute its stationary distribution $\pi$ by iterating the chain, and the cost of seeing $b$ where $a$ was expected is the log-odds

$$s(a,b) = \left\lceil -\log_2 \frac{P(b \mid a)}{\pi(b)} \right\rfloor$$

rounded to a whole number, with identity set to zero and everything else floored at one so that the table can be minimised unchanged.

The same derivation runs over any alphabet that has a process behind it, and the process does not have to be biology. Typing is a walk as well: a finger aiming at one key lands on a neighbour far more often than on a key across the board, so the log-odds of that walk is a substitution matrix over the letters with no chemistry in it anywhere.

The construction has one property worth flagging now and arguing later: a log-odds score has no reason to obey the triangle inequality, and over the keyboard it does not. That makes the answer a score rather than a distance, and it breaks things that assume otherwise — which is an essay of its own.

Only the ratios matter, and two of them are edges #

A cost model here has two kinds of number in it — what a substitution costs and what a gap character costs — and scaling both by the same factor changes every total and no alignment. So the model has fewer degrees of freedom than it looks to have: what decides the shape of the answer is the ratio between a substitution and a gap, and there are two values of that ratio at which the behaviour changes qualitatively.

Set the substitution cost to $s$ and the gap character to $g$. Aligning $a$ against $b$ directly costs $s$; the alternative is to delete $a$ and insert $b$, which costs $2g$ and achieves the same thing. So:

• when $s > 2g$, no substitution is ever chosen — every mismatch is cheaper as a deletion followed by an insertion, and the model has quietly stopped being an edit distance and become a longest-common-subsequence measure with a scale factor;
• when $s < g$, no gap is ever chosen unless the strings differ in length, because a substitution is cheaper than either half of the pair it replaces.

Both are reachable and neither announces itself. On the pair above:

The last row is a model that will never report a substitution on any pair of strings, and the numbers in it — 3 and 1 — are not extreme. Somebody typing plausible-looking costs into a configuration file can land there, and the output remains a perfectly well-formed alignment with a perfectly reasonable-looking total.

That is the practical reason to derive a matrix from a process rather than choose one. The walk above produces a transversion cost of 3 against a gap of 2; three is under twice two, so substitutions survive, and the fact that they do is a consequence of the mutation probability rather than something that had to be noticed.

The alignment moves, not just the number #

If the cost model only changed the total, it would be a matter of units and not much else. It changes the answer.

Score each model’s chosen alignment under the other model and the picture sharpens into a number:

Read down the last column. The alignment unit cost picked costs 16 bits under the log-odds model, whose own answer is 10 — a 60% overstatement from taking one table’s alignment and pricing it with another table’s rule. That is a specific and common error: an alignment produced under whatever the tool defaulted to, reported with a score computed under the model somebody wanted.

Read along the diagonal and every model prefers its own alignment, which is what makes the table a check rather than a display. That property is asserted in this site’s gate, and so is its opposite: an alignment quoted with a foreign model’s number is a case the gate is required to catch.

The row that is the actual finding #

Read the first column instead and something more interesting happens. The log-odds alignment costs 6 under unit cost — which is unit cost’s own optimum.

The finer model’s answer was available to the coarser one all along. Unit cost simply had no way to prefer it.

Twenty-one alignments of these two strings cost exactly 6 edits. They are not all equally sensible — some of them pair a purine with a pyrimidine where another pairs it with the other purine — and unit cost cannot see the difference, because under unit cost every one of those pairings costs 1.

So when a program prints an alignment under unit cost, what it has printed is one of twenty-one, chosen by whichever way its traceback happened to break ties. Mine breaks them towards substitution, then deletion, then insertion. That is a stated convention and it is not a result, which is why every plate here that draws an alignment prints how many were optimal beside it.

A matrix is a claim about the data, not about the algorithm #

There is a temptation to treat the cost model as a tuning knob — try a few, keep the one whose output looks best — and it is worth resisting for a reason that has nothing to do with taste.

The rule above is a model of how the data was produced. It says: symbols drift, drift within a class is eight times more likely than drift between classes, and one step of drift separates the two strings. If that is true of the strings being compared, the alignment the model returns is the most probable explanation of their difference, and the total is the number of bits of surprise in that explanation. If it is false, the alignment is the most probable explanation under an assumption that does not hold, and nothing in the output says so.

Which means the honest way to choose a matrix is to state what process is assumed and check whether it is plausible, and the dishonest way is to try several and keep the prettiest. The two produce identical-looking output.

This is the same shape as the entropy floor two fields over, where one stream has five correct floors and which one applies is decided by the model rather than by the data. Here the parallel is exact: one pair of strings has as many correct distances as there are cost models, every one of them is right, and choosing between them is a claim about how the strings came to differ.

What the finer model costs #

Nothing measurable, which is the last thing worth saying about it.

Every linear model above fills 81 cells and considers 192 transitions on this pair. The recurrence takes three arguments per interior cell whatever the substitution rule is, and looking a cost up in a matrix is not more work than testing two characters for equality. The whole difference between unit cost and a derived matrix is which numbers are added.

The affine model is the exception and it is a real one: 243 cells and 448 transitions on the same pair, three times the table, because a cell has to hold three numbers to know where it is. That is a cost in cells, not in the rule; the substitution matrix is still a lookup.

It also only shows itself on strings that have something for a gap model to be right about. The pair used above is eight characters against eight and its optimal alignment has one gap in it, so charging gap openings differently from gap characters has almost nothing to price.

The symmetry nobody declared #

There is a third assumption in the recurrence, alongside the two the essay has named, and it is the one that is hardest to see because the notation makes it look like a fact about arithmetic.

$D(i-1,j)+1$ and $D(i,j-1)+1$ charge the same for consuming a character of the first string and for consuming one of the second. The substitution term charges $s(a,b)$ with no suggestion that $s(b,a)$ might differ. Together those say the two strings are interchangeable: whatever is being measured, it is a property of the unordered pair.

For the derived matrix that turns out to be true, and it is true for a reason rather than by construction. The walk is a random walk on an undirected graph — the purine and pyrimidine pairing is symmetric, keyboard adjacency is symmetric — so the chain is reversible and its stationary distribution satisfies $\pi(a)P(b\mid a) = \pi(b)P(a\mid b)$. Divide through and the two log-odds scores are equal:

$$\frac{P(b\mid a)}{\pi(b)} = \frac{P(a\mid b)}{\pi(a)} \quad\Longrightarrow\quad s(a,b) = s(b,a)$$

So the matrix is symmetric because the process is reversible, and not because anybody imposed it. That is worth knowing chiefly because it says what would break it. A mutation process with a direction — a drift towards one composition, a keyboard slip that is likelier to land to the right of the intended key, a sequencer that miscalls in one direction more than the other — is not a reversible walk, its log-odds table is not symmetric, and $s(a,b) \ne s(b,a)$.

Nothing in the recurrence stops that. The table fills perfectly well with an asymmetric matrix; what changes is that the answer depends on which string was put along the rows. A tool that computes an asymmetric score without saying which argument is the reference is reporting a number whose meaning depends on argument order, and the failure is silent in both directions — reversing the arguments produces a different total with no indication that anything was different.

The gap terms carry the same assumption and break more often. Comparing a reference against a read, an original against an edit, or a specification against an implementation are all situations where deleting from the first and inserting into the second are different events with different likelihoods, and charging them equally is a claim that they are not. The repair is two gap costs rather than one, it costs nothing in the table, and it converts the answer from a distance into a directed score — which is the same conversion the log-odds model already performed and which is why this collection is careful to call the result a score.

Counting the ties costs one number per cell #

The tie counts printed beside every alignment here — twenty-one, six, two, one — look like an expensive thing to know. They are not, and the cheapness is worth spelling out because it is the reason there is no excuse for a tool that does not report them.

Fill a second table alongside the first. Where the first cell takes the minimum of three candidates, the second takes the sum of the counts of whichever candidates achieved that minimum, with the origin seeded at one. That is one addition and up to three comparisons per cell, on a table that already exists, and the final corner holds the number of distinct optimal alignments.

The whole machinery is the same recurrence read over a different pair of operations — minimise-and-add becomes count-the-minimisers — and it is the standard trick for turning an optimisation into an enumeration. Every model in this essay is scored by exactly that method, which is why the counts can be printed for four different cost rules without four different implementations.

Two practical cautions come with it, and both are the kind of thing that turns up as a bug rather than as a caveat.

The count grows exponentially. Two strings of a few hundred characters under unit cost can have more optimal alignments than there are atoms worth counting, so the second table needs arbitrary-precision integers or has to be kept in logarithms. On the eight-character pairs here the numbers are small; on anything real they are not, and a count silently overflowing a machine word reports a plausible small number rather than an error.

And the count is a property of the cost model, not of the strings — which is the essay’s whole subject arriving in the one place a reader might not expect it. Twenty-one under unit cost and one under affine gaps are counts of the same set of alignments, partitioned differently by two rules about what things cost. A tie is not an ambiguity in the data; it is a distinction the model declined to make, and the number of them is the most direct measurement available of how much resolution a cost model actually has.

What to take from this #

Three things, in the order they bite.

A distance is not a property of two strings. It is a property of two strings and a rule, and the rule is an input to the computation in exactly the sense that the strings are. Every earlier table on this site is a statement under one particular rule and none of them says so — which is the same omission a guarantee quoted without its model makes one field over, and it is worth being embarrassed about in both places.

The unit is part of the answer. Edits, arbitrary cost units, and bits are three currencies. Averaging across them, comparing them, or plotting them on one axis is an error that no assertion about the arithmetic will catch, because the arithmetic is fine.

A model that makes no distinctions has ties it cannot see. Twenty-one to two is a large ratio, and the number that matters is not which alignment is right but how many the model considered indistinguishable. A tool that reports one of them without saying so is reporting its tie-break.

And one thing this essay has deliberately not done. Nothing above compares any of these models against a correct answer, because on this material there is no such thing to compare against: the strings were generated, not observed, and no rule external to the models says which alignment of them is the true one. What has been measured is that the models disagree, by how much, in which direction, and at what cost — which is a set of facts about the models. Whether a particular matrix suits a particular corpus is an empirical question about that corpus and it is not one this collection can settle from a stated rule.