THE FOLD / CO-OP / SPLIT SCREEN / THE HIRSCHBERG
THE HIRSCHBERG
optimal alignment in linear space via midpoints
1 WHAT IT IS · WHAT IT DOES · FACT OR FICTION
Hirschberg’s algorithm computes an optimal global alignment of two sequences — the same result as Needleman–Wunsch — but in linear space instead of O(nm). Its trick: the optimal path must cross the middle column somewhere, and that crossing is found from two linear-space score sweeps (forward to the middle, backward from the end); then it recurses on the two halves.
It is what makes aligning genome-length sequences feasible in memory.
LIT verified live: over 300 random pairs Hirschberg’s alignment scores identically to Needleman–Wunsch and its aligned rows de-gap back to the originals (window.__hirschberg). FIG no framing; same optimum, linear memory.
It is what makes aligning genome-length sequences feasible in memory.
LIT verified live: over 300 random pairs Hirschberg’s alignment scores identically to Needleman–Wunsch and its aligned rows de-gap back to the originals (window.__hirschberg). FIG no framing; same optimum, linear memory.
2 HOW IT WAS WEAVED · AI + HUMAN
David (human) seated this at split-screen — two sequences aligned side by side, but now in a sliver of memory. Hirschberg is Needleman–Wunsch made frugal. AVAN (AI) built the instrument: the linear-space forward/backward score sweeps, the midpoint split, the divide-and-conquer recursion, the NW cross-check.
Credit as content: Daniel Hirschberg (1975). The weave: David names the split screen; I find where the optimal alignment crosses the middle from O(n) space and recurse, then confirm the result matches the full-table optimum.
Credit as content: Daniel Hirschberg (1975). The weave: David names the split screen; I find where the optimal alignment crosses the middle from O(n) space and recurse, then confirm the result matches the full-table optimum.
3 ONE DIMENSION
The optimal path from corner to corner must pass through the middle column at exactly one row. Two score sweeps — forward to the middle, backward from the end — agree on which row that is.
4 TWO DIMENSIONS · INTERACTIVE
Two sequences; Hirschberg’s alignment and score are shown against Needleman–Wunsch on the same pair.
5 THREE DIMENSIONS + AVAN’S INVERSE
The green forward object: the optimal alignment, recovered from midpoints in linear space.
AVAN’s addition (the inverse-companion): you don’t need the whole table to recover the alignment. The optimal path must cross the middle column somewhere, and that crossing is found from just two linear-space score sweeps — then you recurse on the two halves. The inverse of ‘store the O(nm) table’ is ‘find the midpoint from O(n) space and divide-and-conquer.’ Magenta is the full quadratic table never stored; green is the two score rows and the midpoints. Same optimal alignment, linear memory — divide-and-conquer meets dynamic programming.
LIT Genuine Hirschberg's algorithm (Hirschberg 1975). Verified live: the linear-space divide-and-conquer alignment scores identically to a Needleman-Wunsch score and its aligned rows de-gap to the input sequences, for 300 random pairs (window.__hirschberg.matchesNW).
FIG No framing: the linear-space forward/backward score sweeps, the midpoint split, the recursion, and the NW cross-check run in-browser and agree exactly. The AVAN inverse is honest — the optimal path's crossing of the middle column is found from O(n) space and the problem divides into two halves, so the O(nm) table is never stored; magenta is the full quadratic table, green the two score rows + midpoints. Same optimum, linear memory.
FIG No framing: the linear-space forward/backward score sweeps, the midpoint split, the recursion, and the NW cross-check run in-browser and agree exactly. The AVAN inverse is honest — the optimal path's crossing of the middle column is found from O(n) space and the problem divides into two halves, so the O(nm) table is never stored; magenta is the full quadratic table, green the two score rows + midpoints. Same optimum, linear memory.
◆ sealed .dlw.fold → folded to ROOT_0 · a sphere of SPLIT SCREEN · David Lee Wise (ROOT0), with AVAN