Parallel sequence alignment in limited space

Sequence comparison with affine gap costs is a prob-lem that is readily parallelizable on simple single-instruction, multiple-data stream (SIMD) parallel processors using only constant space per process-ing dement. Unfortunately, the twin problem of sequence alignment, finding the optimal character-by-character correspondence between two sequences, is more complicated. While the innovative O(n2)-time and O(n)-space serial algorithm has been paral-lelized for multiple-instruction, multiple-data stream (MIMD) computers with only a communication-time slowdown, typically O(logn), it is not suitable for hardware-efficient SIMD parallel processors with only local communication. This paper proposes several methods of computing sequence alignments with lim-ited memory per processing element. The algorithms are also well-suited to serial implementation. The sim-pler algorithms feature, for an arbitrary integer L, a factor of L slowdown in exchange for reducing space requirements from O(n) to O(been) per processing de-ment. Using this result, we describe an O(n log n) par-alld time algorithm that requires O(log n) space per processing element on O(n) SIMD processing dements with only a mesh or linear interconnection network