Reference: Galper, A. R. & Brutlag, D. L. Parallel Similarity Search and Alignment with the Dynamic Programming Method. Knowledge Systems Laboratory, October, 1990.
Abstract: We consider the problem of similarity search and alignment of biological sequence data using mulitiple processors operating in parallel. We review the basic dynamic programming method commonly used in sequential algorithms and outline several practical approaches for decomposing the method to run on shared-memory multiprocessors. Finally, we present preliminary results of our parallel decompositions, written for a 16-node Encore Multimax.