Parallel pattern-recognition using dynamic-programming

The well-known alignment of sequences representing patterns problem is defined and parallel algorithms for solving it are presented. The authors give two versions for the problem-a basic and a cyclic one. Systolic solutions which need (N+M+1) clock periods and (M(M+1)) PEs of a linear array are proposed. For the cyclic algorith (2N+M+2) clock periods are needed. They also describe possible improvements which lead to designs with a lower computational complexity estimation, for the basic task it is ([(M+N)/2]+[logM]+1) clock periods with 2M-1 (tree) or M (perfect-shuffle) PEs of the systolic array. Finally, the authors give a theoretical result for solving this problem on such models of parallel computers as PRAM and hypercube.