Sequential and parallel algorithms for local sequence similarities

We present two space-efficient sequential algorithms for finding similar regions of two sequences of symbols. The previous dynamic programming algorithms for this problem all require space proportional to the product of the two sequence lengths, and hence can only process sequences of a few thousand symbols on typical computers. Both of our dynamic programming algorithms require space proportional to the lengths of the sequences and the lengths of the similar regions; one is more efficient in time than the other. The fast algorithm takes about the same order of time as the best previous algorithm. The slow one is parallelized on a hypercube. We also present an algorithm for computing the distance between restriction maps.