Aligning sequences in linear space

The standard dynamic programming algorithm requires storage of at least one $m \times n$ matrix in order to calculate the alignment. On current computers, this is not a problem for protein sequences, but for large DNA sequences, or complete genomes, space requirements can be prohibitive. Linear-space algorithms for dynamic programming [Myers & Miller, 1988] overcome this problem by a recursive strategy, albeit at some sacrifice in execution time.