Parallel sequence alignment in limited space

Sequence comparison with a ne gap costs is a problem that is readily parallelizable on simple singleinstruction, multiple-data stream (SIMD) parallel processors using only constant space per processing element. Unfortunately, the twin problem of sequence alignment, nding the optimal characterby-character correspondence between two sequences, is more complicated. While the innovative O(n 2)time and O(n)-space serial algorithm has been parallelized for multiple-instruction, multiple-data stream (MIMD) computers with only a communication-time slowdown, typically O(log n), it is not suitable for hardware-e cient SIMD parallel processors with only local communication. This paper proposes several methods of computing sequence alignments with limited memory per processing element. The algorithms are also well-suited to serial implementation. The simpler algorithms feature, for an arbitrary integer L, a factor of L slowdown in exchange for reducing space requirements from O(n) toO ( Lp n) per processing element. Using this result, we describe an O(n log n) parallel time algorithm that requires O(log n) space per processing element onO(n) SIMD processing elements with only a mesh or linear interconnection network