The alignment that fits in one line

The rolling frontier gave up the alignment to save the space. This is the algorithm that takes it back, and the price is stated exactly rather than asymptotically: twice the cells.

The idea is one sentence. Every route through the grid crosses the middle row exactly once, because a route only ever moves downwards or sideways and never back up. So if the column where it crosses were known, the problem would split into two smaller rectangles that could be solved independently — and the crossing column can be found without knowing the route, by computing the middle row twice.

Why the split is exact #

Two claims are doing the work and both are easy to state precisely.

A route crosses the middle row once. Steps are $(+1, 0)$, $(0, +1)$ and $(+1, +1)$, so the row index never decreases and increases by at most one per step. It therefore takes the value $\mathrm{mid}$ at exactly one or two consecutive positions, and taking the first is a well-defined choice.

The cost splits at the crossing. A shortest path through a fixed cell is a shortest path to that cell followed by a shortest path from it — this is the same optimal-substructure property the recurrence itself rests on, applied to a cell in the middle rather than to a corner. So the minimum over all routes equals the minimum over columns $j$ of (best cost to $(\mathrm{mid}, j)$) + (best cost from $(\mathrm{mid}, j)$).

The second quantity is the first quantity of the reversed problem, which is why the backward pass is the forward pass run on both strings reversed. No new machinery is needed and no new recurrence: the same code, twice, on smaller inputs.

Both halves can then be recursed on, and the recursion bottoms out when one string has a single character, where the alignment is read off directly.

The factor of two, which is a series and not an estimate #

The top level computes the full rectangle — once forwards over the top half and once backwards over the bottom half, which between them is $nm$ cells.

Each half is then an independent problem of half the height, and the two of them together cover the rectangle again but only over the columns their own halves span, so between them they touch $nm/2$. Their four children touch $nm/4$. The series is

$$nm + \frac{nm}{2} + \frac{nm}{4} + \cdots = 2nm,$$

which is not an asymptotic statement — it is the sum of the work at every level, and the levels are exactly halved.

Measured, the ratio comes down towards two from above:

The excess over two is the base cases. The series counts a rectangle of height $h$ as $h \times$ width, and a rectangle of height one still has a boundary row above it, so every leaf of the recursion pays a constant the series does not account for. There are $n$ leaves and the overhead per leaf is a row, which is exactly the $O(nm/n) = O(m)$ per level of extra work the numbers show, shrinking as a fraction as $n$ grows.

What it holds #

Three rows and a stack of frames.

The forward pass holds two rows while it runs and one row when it finishes; the backward pass does the same; and the divide step holds both finished rows while it adds them. Measured, the peak is exactly $3(m+1)$ cells at every size: 195 at $m = 64$, 387 at 128, 771 at 256, 1,539 at 512.

The right-hand column is $(n+1)/3$, and it grows without limit — which is the whole point. Below it there is a recursion, and the recursion is $\log_2 n$ deep because each level halves the height, so the frames are negligible against the rows. That is the difference between this and a top-down memoised fill, whose stack is linear.

The base case, where the constant comes from #

The recursion stops when the first string has one character or none, and that boundary is where the excess over two lives.

With a single character the alignment is read off directly: it is a run of insertions with at most one match or substitution in it, and finding where costs a rectangle of height one. But a rectangle of height one still has two rows — the boundary row above it and the row itself — so the leaf costs $2(m'+1)$ cells where the series budgeted $m'+1$.

There are $n$ leaves and their widths sum to $m$, so the total excess is about $m + n$ cells against a series of $2nm$. That is a fraction of order $1/n$, which is exactly the shape the measured ratios show: 2.269 at $n = 64$ is 2 plus 0.27, and 2.052 at 512 is 2 plus 0.05, and the two excesses are in the ratio 5.4 against a predicted 8. The remaining discrepancy is that the leaves are not all the same width and the recursion is not perfectly balanced — the split column can land anywhere, so one child can be much wider than the other.

That last point is worth dwelling on because it is a genuine asymmetry with the usual divide-and-conquer analysis. The rows are halved exactly, which is what makes the depth $\log_2 n$ and the series clean. The columns are split wherever the alignment happens to cross, which can be at either end. A pathological split does not hurt the total work — the series is over rows — but it does make the tree lopsided, and on strings of very different lengths the recursion can be $\log_2 n$ deep with leaves whose widths vary by orders of magnitude.

The general shape of the exchange #

Hirschberg’s method is one point on a curve, and it is worth seeing the curve because the point is not obviously the right one.

Keep every row. $nm$ space, $nm$ work, alignment available.

Keep every $k$-th row. $nm/k$ space. To recover the alignment, walk backwards and recompute each band of $k$ rows from the checkpoint above it, which costs one extra pass over the table: $2nm$ work. This is checkpointing, it is what long-running scientific codes do for adjoint computations, and it has a free parameter.

Keep two rows and divide. $3m$ space, $2nm$ work. Hirschberg’s method is the limit of checkpointing as $k \to n$, with the recursion replacing the single recompute pass.

Keep nothing. $m$ space, and the alignment is unavailable at any price short of recomputation from scratch.

The interesting thing about that list is that the work column has only two values in it: $nm$ and $2nm$. Buying the alignment back costs a single factor of two whatever the space target, and choosing between the middle two lines is a choice about constants and implementation complexity rather than about growth. The frontier between time and space drew the same kind of curve for sorting, and found the same thing there: the interesting positions are few and the space between them is not populated by anything worth having.

What it composes with #

Two things, and neither needs the method to be modified.

Bit-parallelism. The forward and backward passes each produce one row of the table, which is exactly what a column computed in machine words produces as a by-product of its running score. Substituting the word-parallel routine for the row computation leaves the divide-and-conquer structure untouched and takes a factor of $w/15$ off the work at every level.

Banding. If the distance is known to be at most $k$, each rectangle in the recursion can be computed inside a band, and the crossing search restricted to the columns the band reaches. The combination is what production aligners run.

What it does not compose with is a top-down memoised fill, and the reason is instructive: the method depends on being able to compute a specific row of a specific rectangle and then discard it, which is a statement about evaluation order, and a recursion that chooses its own order cannot make it.

Why this is not simply “recompute the table” #

There is a much simpler idea that gets the space down and does not work, and it is worth naming because it is the first thing anybody proposes.

Run the rolling frontier to get the distance. Then, to recover the alignment, walk backwards from the corner: at each cell, work out which of its three predecessors it came from, and to do that recompute the cell above it. Recomputing one cell means recomputing the whole rectangle above it, which is $\Theta(nm)$ per step of a path with $\Theta(n + m)$ steps — cubic, and worse than simply storing the table on any machine where the table fits.

The reason Hirschberg’s method escapes that is the halving. Each recomputation covers half the remaining problem rather than all of it, so the total is a geometric series rather than a product. That is the same distinction between a linear recurrence and a halving one that separates a quadratic sort from a linearithmic one, appearing here in the space dimension, and it is the reason the answer is $2nm$ and not something between $nm$ and $n^2m$.

The choice of which string to split #

One detail of the implementation is a decision rather than a consequence, and it is worth naming because it is where the method’s worst case lives.

The recursion halves the first string and searches over positions in the second. So the depth is $\log_2 n$ and the space is $\Theta(m)$, and swapping the arguments swaps those: a hundred-character string against a million-character one wants the hundred on the axis being searched, not on the axis being halved.

The rule is to split the longer string and hold a row of the shorter, which makes the space $\Theta(\min(n, m))$ and the depth $\log_2 \max(n, m)$. An implementation that does not check which is which is correct and can be a factor of ten thousand off on its space, which is the resource the whole method exists to manage — and no test of the answer would notice.

That is a recurring shape on this site: a method whose claim is about a resource, with an implementation detail that silently violates the claim while producing the right output. It is the same class of defect as an unbalanced recursion or a memo keyed on too little state, and the same remedy applies — assert the resource, not the answer.

What the split does not buy, which is parallelism #

A divide-and-conquer method looks as though it should parallelise, and this one barely does. The arithmetic is short enough to do here and the answer is a number worth knowing before anybody builds it.

After the first split the two halves are genuinely independent: different rectangles, no shared state, no communication. So the obvious plan is to run them on separate processors and recurse. The obstruction is that the first level has to finish before either of them can start, and the first level is half of all the work.

Count the span — the length of the longest chain of dependent work — on a balanced instance. Level zero computes the full rectangle twice over its two halves, which is $nm$ and is unavoidably sequential with respect to everything below it. Level one has two children of a quarter the area each, run at the same time, so it adds $nm/4$ to the span rather than $nm/2$. Level two adds $nm/16$. The series is

$$nm\left(1 + \tfrac14 + \tfrac1{16} + \cdots\right) = \tfrac43\,nm$$

against total work of $2nm$. The maximum speedup available from any number of processors is $2 / (4/3) = 1.5$, and half of that is recovered at the first split — two processors get most of what infinitely many would.

That is a poor return, and it is poor for a structural reason rather than an implementation one: the recursion halves the problem but the top level already touched everything, so the parallelism arrives after the expensive part is over. It is the opposite of a merge sort, where the leaves are cheap and independent and the merging is what has to be sequenced.

The consequence for a real aligner is that parallelism has to come from somewhere else, and there are two places it does come from. The rows themselves can be computed with word-level parallelism, which is the composition already noted above and which applies at every level including the first. And a batch of alignments can be run at once, which is what a read aligner actually does — thousands of independent queries against one reference is embarrassingly parallel in a way one alignment is not.

A method that reduces space by a constant factor of extra work does not thereby become a method that scales across processors, and the two properties are so often discussed together that it is worth having the number.

What has to cross the middle when a cell knows where it is #

The whole construction rests on one sentence: a route crosses the middle row exactly once, so the cost splits at the crossing column. Change the cost model to affine gaps and that sentence needs a repair, which is worth working through because it is the commonest way this method is got wrong when it is carried to a new recurrence.

Under affine gaps a cell holds three numbers rather than one — the best cost arriving in a match state, in a horizontal-gap state, and in a vertical-gap state — because what a step costs depends on what the previous step was. A route crossing the middle row is therefore in one of three states when it crosses, and the two halves cannot be joined by adding two numbers.

The repair is to minimise over crossings and states rather than over crossings alone: the forward pass reports three values per column, the backward pass reports three, and the join takes the best of nine combinations per column with one correction. The correction is the part that is easy to miss. A route that is in the middle of a horizontal gap when it crosses has already paid that gap’s opening cost in the forward half, and the backward half — which was computed as though the gap started at the crossing — has paid it again. One of the nine combinations must have an opening cost subtracted from it, and an implementation that does not is silently biased against alignments whose gaps happen to straddle the middle.

The failure that produces is exactly the kind this essay’s last section is about. The returned alignment is valid, its cost is within a gap-opening penalty of optimal, and on most inputs it is optimal — because most gaps do not straddle the middle row. It shows up as a handful of instances in a large batch where the linear-space aligner and the full-table aligner disagree by a constant, which is a bug report that looks like a rounding difference and is not.

The general rule is that the crossing has to carry everything the recurrence needs to resume, and in the unit-cost case that is nothing but the column. Any recurrence whose cell carries state carries that state across the split too, and the number of things to minimise over is multiplied by the number of states rather than added to.

The measurement that would have caught the mistake #

There is one thing worth recording about building this, because it is the sort of error that survives a lot of testing.

The obvious way to check the method is to compare its distance against the full table’s. That check passes on an implementation whose split column is off by one, whose recursion is unbalanced, or whose backward pass reverses only one of the two strings — because the distance is recoverable from the returned edit script by counting non-matches, and a wrong split still produces a valid, slightly-too-expensive alignment on many inputs.

The check that fires is on the cells: the method must compute close to twice the table and not four times, and not one and a half times. A ratio of 3.1 says the recursion is not halving; a ratio of 1.6 says a level is being skipped. This site’s gate asserts the ratio lies between 1.5 and 2.6 alongside the answer, and both bounds have caught something.

That is the same lesson measured, not asserted collects elsewhere on this site, in the form it takes here: when an algorithm’s whole claim is about a resource, the resource is what has to be asserted, and the answer being right is not evidence that it was obtained the way it was supposed to be.