Reduced Space Sequence Alignment

Sequence alignment is the problem of finding the optimal character-by-character correspondence between two sequences. It can be readily solved in O(n²) time and O(n²) space on a serial machine, or in O(n) time with O(n) space per O(n) processing elements on a parallel machine. Hirschberg's divide-and-conquer approach for nding the single best path reduces space use by a factor of n while inducing only a small constant slowdown to the serial version