Hirschberg's algorithm

Hirschberg's algorithm is a divide-and-conquer variant of the Needleman-Wunsch algorithm that computes optimal global sequence alignment in O(nm) time while using only O(min(n,m)) space. Published by Daniel Hirschberg in 1975, it solved the space-complexity problem that had made full-sequence alignment infeasible for long biological sequences.

The algorithm's key insight is that the optimal alignment path through the dynamic programming matrix must cross the midpoint row. Hirschberg computes the forward scores from the top to the midpoint and the reverse scores from the bottom to the midpoint, finds the column where these scores sum to the optimal total, and then recursively aligns the two halves. The recursion terminates when the subproblems become small enough to solve by standard methods.

This space reduction was transformative before the era of abundant memory. Even today, it enables alignment of sequences that would otherwise exceed available RAM, and it forms the basis of space-efficient variants used in genome assembly and multiple sequence alignment where many sequences must be aligned simultaneously.

Hirschberg's algorithm demonstrates a recurring pattern in computer science: when the straightforward dynamic programming solution is correct but infeasible, a structural insight about the problem's geometry — in this case, that optimal paths must cross midpoints — yields an asymptotic improvement without sacrificing correctness.