*J Alicia Grice, Richard Hughey, and Don Speck*

Sequence comparison
with affine gap costs is a problem that is readily parallelizable on simple
single-instruction, multiple-data stream (SIMD) parallel processors using only
constant space per processing element. Unfortunately, the twin problem of
sequence *alignment,* finding the optimal character-by-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-efficient 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) to
O(n**(1/L)) per processing element. Taking this series to the limit, we
describe an O(n log n) parallel time algorithm that requires O(log n) space per
processing element on O(n) SIMD processing elements with only a mesh or linear
interconnection network.

This page is copyrighted by AAAI. All rights reserved. Your use of this site constitutes acceptance of all of AAAI's terms and conditions and privacy policy.