Grice J A, Hughey R, Speck D
University of California, Santa Cruz 95064, USA.
Proc Int Conf Intell Syst Mol Biol. 1995;3:145-53.
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(n2)-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(L square root of 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 on O(n) SIMD processing elements with only a mesh or linear interconnection network.
使用仿射间隙代价进行序列比较是一个在简单的单指令多数据流（SIMD）并行处理器上很容易并行化的问题，每个处理单元仅使用恒定空间。不幸的是，序列比对的孪生问题，即在两个序列之间找到最优的逐个字符对应关系，更为复杂。虽然创新的O(n²)时间和O(n)空间的串行算法已针对多指令多数据流（MIMD）计算机进行了并行化，通信时间仅有通常为O(log n)的减慢，但它不适用于仅具有局部通信的硬件高效SIMD并行处理器。本文提出了几种在每个处理单元内存有限的情况下计算序列比对的方法。这些算法也非常适合串行实现。更简单的算法对于任意整数L，以L倍的速度减慢为代价，将每个处理单元的空间需求从O(n)减少到O(L√n)。利用这一结果，我们描述了一种O(n log n)并行时间算法，该算法在仅具有网格或线性互连网络的O(n)个SIMD处理单元上，每个处理单元需要O(log n)的空间。
