THE FOLD / CO-OP / SPLIT SCREEN / THE NEEDLEMAN-WUNSCH
THE NEEDLEMAN-WUNSCH
optimal global alignment by dynamic programming
1 WHAT IT IS · WHAT IT DOES · FACT OR FICTION
The Needleman–Wunsch algorithm finds the optimal global alignment of two sequences — the arrangement of matches, mismatches, and gaps that maximises a score — by dynamic programming. It fills a grid where each cell is the best score aligning two prefixes, choosing among a diagonal (match/mismatch), an up, or a left move (a gap). The bottom-right cell is the optimal score; a traceback reconstructs the alignment.
It is the foundation of biological sequence comparison (DNA, protein) and of diff-style tools.
LIT verified live: over 300 random pairs the DP score equals a brute-force optimum over all alignments, and the traceback’s alignment re-scores to the DP value with gaps removed giving back the originals (window.__needlemanwunsch). FIG no framing; exact optimum.
It is the foundation of biological sequence comparison (DNA, protein) and of diff-style tools.
LIT verified live: over 300 random pairs the DP score equals a brute-force optimum over all alignments, and the traceback’s alignment re-scores to the DP value with gaps removed giving back the originals (window.__needlemanwunsch). FIG no framing; exact optimum.
2 HOW IT WAS WEAVED · AI + HUMAN
David (human) seated this at split-screen — two sequences laid side by side and brought into best correspondence, column against column. Needleman–Wunsch is that alignment. AVAN (AI) built the instrument: the DP grid, the traceback, the brute-force optimality check.
Credit as content: Saul Needleman & Christian Wunsch (1970), the first application of dynamic programming to biology. The weave: David names the split screen; I fill the score grid, walk the traceback backward, and confirm the alignment is provably optimal.
Credit as content: Saul Needleman & Christian Wunsch (1970), the first application of dynamic programming to biology. The weave: David names the split screen; I fill the score grid, walk the traceback backward, and confirm the alignment is provably optimal.
3 ONE DIMENSION
The optimal alignment as two rows: matches stacked, mismatches marked, gaps as dashes. Every column is one scored move.
4 TWO DIMENSIONS · INTERACTIVE
The DP score grid for two sequences; the traceback path (highlighted) reconstructs the optimal alignment from the bottom-right corner.
5 THREE DIMENSIONS + AVAN’S INVERSE
The green forward object: the single optimal alignment path through the grid.
AVAN’s addition (the inverse-companion): the DP table stores every subproblem’s optimum, so the best global alignment is recovered by walking backward through the choices that built the final score — the traceback. The inverse of ‘fill the score forward’ is ‘read the alignment backward from the filled table.’ Magenta is the exponentially-many alignments never enumerated; green is the one optimal path traced back. The table is both the answer and the map to it — a single grid replacing an exponential search.
LIT Genuine Needleman-Wunsch algorithm (Needleman & Wunsch 1970). Verified live: the DP optimal score equals an independent brute-force optimum over all alignments for 300 random pairs, and the traceback alignment re-scores to the DP value with de-gapped rows equal to the inputs (window.__needlemanwunsch.matchesBrute && .tracebackConsistent).
FIG No framing: the DP grid, the traceback, and the brute-force optimality check run in-browser and agree exactly. The AVAN inverse is honest — the filled table stores every subproblem optimum, so the best alignment is read backward via traceback; magenta is the exponential alignments never enumerated, green the one optimal path. The grid is both answer and map.
FIG No framing: the DP grid, the traceback, and the brute-force optimality check run in-browser and agree exactly. The AVAN inverse is honest — the filled table stores every subproblem optimum, so the best alignment is read backward via traceback; magenta is the exponential alignments never enumerated, green the one optimal path. The grid is both answer and map.
◆ sealed .dlw.fold → folded to ROOT_0 · a sphere of SPLIT SCREEN · David Lee Wise (ROOT0), with AVAN