The zero that moves the answer out of the corner

Three modes of one rectangle have appeared in this field and two of them have been measured. A global alignment runs both strings end to end and reads the answer from the corner. A search sets the top row to zero, which makes a prefix of the text free, and reads the answer from the minimum of the last row. The third is local, and it is the one where the change is not one line but four.

The question it answers is different from either. Not how far apart are these two sequences and not where in this text does this pattern nearly occur, but which region of one resembles which region of the other — with both ends of both regions unknown and to be discovered.

That difference in question is what makes the mode worth a page of its own rather than a paragraph. A global alignment asked of two sequences that share a short region and nothing else will report the whole of both, aligned badly, because it has no permission to stop — and the number it returns will be dominated by the parts that do not correspond. Run on the two sequences the plate above uses, a global alignment under unit cost costs twenty across a table of 1,040 cells, and that twenty says almost nothing about the fifteen characters they actually have in common.

Four lines, and what each of them does #

The global recurrence over a cost model is a minimum of three ways to reach a cell. The local one is a maximum of four, and the sign flip is the first of the four changes:

$$H(i,j) = \max\big(0,\ H(i-1,j-1) + s(a_i, b_j),\ H(i-1,j) - g,\ H(i,j-1) - g\big)$$

The model is read as a score rather than as a cost. A match is worth something positive and everything else is negative. That is not a presentational change: a minimisation over costs and a maximisation over scores are the same computation only when the scores are the negated costs, and the term that follows makes them not.

The first row and the first column are zero. Both of them, where the search mode zeroes only the top row. That makes both a prefix of one sequence and a prefix of the other free, which is the half of “local” the search mode does not have.

Every cell is floored at zero. A running alignment whose score has fallen to nothing is abandoned and a new one may begin at that cell for free. This is the term that makes the mode local rather than merely two-sided.

And the answer is the maximum over the whole table rather than a designated cell. It is not in the corner, it is not in the last row, and finding it requires looking at all of them.

Read together, those four changes are one idea: an alignment is allowed to start and to stop. The zeroed row and column let it start anywhere, the floor lets it stop and restart anywhere, and the maximum over the table is how it is found afterwards. Everything else about the computation — the cell count, the dependency structure, the fill order, the space that a rolling frontier could save — is untouched, which is why this field’s counter reports the identical number of cells for a local and a global fill on the same pair.

The answer is not where it used to be, and that costs something #

A global alignment’s traceback starts at $(n, m)$ because that is where the answer is. A local one starts wherever the maximum happened to be, and walks back until it hits a cell holding zero. So both ends of the reported region are discovered rather than given, and neither is available until the table is filled.

Three consequences follow and each is a real cost.

The maximum must be tracked as the fill proceeds, or found by a second pass over the table. Either is $O(nm)$ and neither is free; the fill’s inner loop gains a comparison, which is a constant on a computation that is already the dominant term.

A rolling frontier cannot answer the question at all. The table nobody has to keep showed that the number can be computed in two rows and the alignment cannot; and the alignment that fits in one line recovers the path at twice the cells. Here even the location of the answer is part of what is wanted — a region is a pair of intervals, not a score — so the two-row version keeps a number that names a place it can no longer find. The linear-space method that recovers a global alignment does adapt, at the usual doubling of the cells, and the adaptation has to be told where to recurse from.

And there is more than one answer. The table’s second-highest local maximum is a second region, the third is a third, and a search that wanted all the regions above some score has to enumerate them — with the additional difficulty that two nearby maxima can be two ends of one region rather than two regions, which no rule in the recurrence distinguishes.

There is a fourth consequence that is easy to miss and is the one that bites in practice. A local alignment’s score cannot be compared with a global one’s, even under the same model, because the two are optimising different things over different regions. A global cost of twenty and a local score of twenty-seven on the same pair are not two measurements of one quantity; they are two quantities. This site has been insisting on that since a cost that is not one found four numbers on eighty-one cells of which only one was a count of anything, and the local mode adds a fifth.

The precondition, which is on the scoring scheme #

Here is the part that no statement of the algorithm contains and that decides whether its output means anything.

Take two positions at random, one from each sequence. Under a four-letter alphabet used evenly, they agree a quarter of the time and disagree three quarters. If a match is worth $+m$ and a mismatch costs $-1$, the expected score of that pair is $\frac{m}{4} - \frac{3}{4}$, which is negative for $m < 3$, zero at $m = 3$ and positive above it.

If the expectation is positive, extending an alignment is profitable regardless of what is being aligned. The running score drifts upward on unrelated sequence, it never falls back to the floor, and the highest-scoring local alignment is essentially the whole of both sequences. The mode has answered a question nobody asked, with a large number, and nothing in the output says so.

That is what the plate measures. At a reward of two the region reported is fifteen characters and the sequences share fifteen characters. At a reward of four it is thirty-four, and the extra nineteen are noise the scoring scheme has made profitable to include. The sequences are the same in both runs.

The condition generalises past this toy: for an alphabet with frequencies $p_x$ and a scoring matrix $s$, the requirement is $\sum_{x,y} p_x p_y\, s(x,y) < 0$. Every published substitution matrix is constructed to satisfy it, and the construction is the reason those matrices are built as log-odds ratios rather than written down by hand — a log-odds score against a background distribution has negative expectation under that distribution automatically.

There is a neat way to see why the failure is total rather than gradual. A local alignment’s running score is a random walk: each column adds the score of one aligned pair, and the floor at zero reflects the walk whenever it goes negative. A random walk with negative drift, reflected at zero, has a stationary distribution and its maximum over $nm$ steps grows like the logarithm of $nm$. A walk with positive drift has no stationary distribution at all: its maximum grows linearly in the number of steps, so the best local alignment is the longest one available. The two regimes are not two ends of a scale, they are two different behaviours of the same process, and the sign of the drift is the whole of what separates them.

What the mode is worth when the precondition holds #

The plate measures the failure. It is worth stating what the success looks like, because it is the reason the mode exists at all.

Two sequences that share a fifteen-character region and otherwise have nothing to do with each other are, to a global alignment, two sequences that are very different. Its answer is dominated by the twenty-odd characters of noise on either side, and no amount of care with the gap model rescues it — the alignment is forced to account for material that does not correspond, because it is forced to run to the corner.

The local mode’s answer on the same pair is the fifteen characters, their positions in both sequences, and a score that describes them and nothing else. It found both ends without being told where to look. That is a genuinely different capability rather than a refinement, and it is what makes this the mode every sequence-search tool is built on rather than the global one.

What it costs is the precondition, and the precondition is unusual in this collection because it is statistical rather than structural. Every other precondition on this site is a property that either holds or does not — a graph is acyclic or it is not, weights are non-negative or one of them is not, a cost matrix satisfies the triangle inequality or a triple breaks it. This one is a statement about an average over a distribution, it can be nearly violated, and near it the mode degrades smoothly rather than failing. The plate’s step between three and four is where that degradation stops being smooth.

What “the answer” is when the answer is a score #

This field has been careful since a cost that is not one that a number produced by a table means nothing until the model is named. A local alignment sharpens that, because its output is not merely in an arbitrary unit — it is in a unit chosen to make the computation behave.

A global edit distance under unit cost is a count of edits. It has an interpretation independent of the algorithm, and two implementations that disagree about it disagree about a fact. A local alignment score of 27 is a number in a unit invented for the purpose, its magnitude depends on the reward chosen, and comparing two local scores computed under two schemes is comparing nothing at all.

What makes it usable is a second layer nobody in this field has built: a statistical model saying how large a score of 27 would be by chance on sequences of these lengths, which converts the score into a probability and makes two of them comparable. That is what a real sequence-search tool reports, it is the reason those tools quote an expectation value rather than a score, and it is a whole apparatus sitting on top of the recurrence.

The honest position for this page is therefore narrow. The recurrence is measured here. The interpretation of its output is not, and the number is a score rather than a quantity. That is the same distinction a guarantee names its model draws throughout this collection, arriving in the case where the model is a distribution over inputs rather than a machine.

It also puts a familiar defect in a new place. A distance that is not a distance found that a stated substitution matrix can break the triangle inequality, which takes with it every structure that prunes by distance. A local alignment score is not a distance at all and never claimed to be — it is not symmetric in the way a cost is, it does not vanish on identical inputs, and it grows rather than shrinks with similarity. So the pruning structures were never available here in the first place, and a system that indexes local alignment scores has to do something else entirely, usually a filter on shared short substrings.

Where the third mode sits beside the other two #

Setting the three modes side by side makes the family visible, and the family is small.

Four columns, three rows, and every difference between the three modes is in this table. The search row is the one the filter that feeds the table is built on, and its single zeroed row is what makes a pattern free to begin anywhere in a text. The fill is identical, the cell count is identical, and the transitions per cell go from three to four in the last row.

That is worth stating plainly because the three are usually taught as three algorithms with three names attached to three people. They are one rectangle with three initialisations and two places to read from, and this field’s counter reports the same number of cells for all three — which is the strongest argument available that the distinction is about the question rather than about the method.

What the mode costs to search with #

Local alignment is not usually run once on two sequences. It is run once per candidate against a database of millions, and the arithmetic of that is what turned the mode from a recurrence into an industry.

The cost of one comparison is $nm$ cells, which for a query of three hundred characters against a sequence of a thousand is three hundred thousand — trivial. Against a database of a million such sequences it is $3\times 10^{11}$, which is not.

So no real system runs the recurrence against everything. It runs a filter first: find candidates sharing a short exact substring with the query, and align only those. That is the same architecture the filter that feeds the table describes for approximate string search, and it has the same two properties — the filter is one-sided, so it may propose candidates that fail, and it may in principle miss candidates the alignment would have found.

The second property is the one that matters and it is rarely stated as plainly as it should be. A filtered local-alignment search is not a search for the best local alignment; it is a search for the best local alignment among candidates the filter proposed. The recurrence is exact and the system built on it is not, and the approximation lives in a step that the recurrence knows nothing about.

That is worth carrying because it changes what a score means one more time. The number a filtered search reports is the best score found, its relationship to the best score available is governed by the filter’s sensitivity, and the sensitivity is a parameter — the length of the exact substring required — that the user usually leaves at its default.

Three ways an answer can leave the corner #

Setting this rung’s move beside two others in the tables field makes the family visible, and the family is about where an answer is allowed to be.

A global alignment’s answer is at a fixed cell, the corner, and every other cell exists to get there. The traceback starts where the answer is.

A search’s answer is in a fixed row, and which column is discovered. That is one degree of freedom, it costs a scan of the last row, and it turns the same table into a different question.

A local alignment’s answer is anywhere, and both its ends are discovered. Two degrees of freedom for the end, and the start is found by walking back to a zero.

Each step outward costs something concrete: the search mode costs a scan of a row, the local mode costs a scan of the table plus the floor’s comparison in every cell, and each step makes the space-saving techniques less available — a rolling frontier can answer the first, can answer the second, and cannot answer the third at all.

The degrees of freedom in where the answer sits are a resource, and this field has been paying for them a step at a time without naming the currency.

What is not measured here #

No published matrix is used. Every score here comes from a stated rule, which is this field’s practice and the reason a cost that is not one refuses to quote a table. Every score on this page comes from a stated rule, in keeping with this field’s practice: a number copied out of a published table is a number that cannot be checked. The consequence is that the precondition arithmetic is exact here and would be approximate on a real matrix, whose background frequencies are the ones its authors used rather than the ones an application has.

The gap model is linear. A cell that has to know where it is established that a gap of four is one event rather than four and that expressing it needs three tables. All three modes accept an affine gap and the local one is drawn here with a linear one, so the regions reported are a little more fragmented than an affine version would give.

The alphabet is used evenly. The precondition arithmetic above assumes each of the four symbols is equally likely, which makes the expected score a clean quarter-minus-three-quarters. Real sequence has skewed composition, and a scoring scheme tuned for one composition has a different expectation under another — so a matrix that is safely negative on one organism’s sequence can be marginal on another’s. That is the same class of failure a corpus that was not generated is about: the statistics of the input are part of the method’s precondition and the input does not come with them attached.

And the second-best region is never shown. Every plate reports one maximum. A real use of this mode wants all the regions above a threshold, the enumeration has its own difficulties, and none of them is on this page.

Where this ladder goes next: a distance divided by a length #

The zero on this page changes what is optimised. The next rung changes what optimal means.

Three edits between two five-character words and thirty between two five-hundred-character ones are the same distance and are plainly not the same amount of difference. Everybody who has ever used one of these numbers has wanted to divide it by something, and the obvious division — take the optimal alignment and divide its cost by its length — is not what it appears to be.

The reason is exactly the reason the zero mattered here: changing the objective changes which alignment wins. The alignment with the lowest cost need not be the alignment with the lowest cost per column; some other alignment may cost more over a much greater length and have a better ratio. Minimising a quotient is a different optimisation from minimising a numerator, dividing afterwards does not perform it, and there is an instance on two-character strings.

That is a small, exactly checkable claim with an enumerable counter-example, which makes it the right next rung — and it lands in the same place this one did, on the observation that the recurrence computes whatever it was asked to compute and nothing in it says what was wanted.