Galper, A. R. and Brutlag, D. L. (1990). Parallel Similarity Search and Alignment with the Dynamic Programming Method (KSL Report 90-74). Stanford University.
Biochemistry & the Section
on Medical Informatics, Stanford
University School of Medicine, Stanford,
We consider the problem of similarity search and alignment of biological sequence data using multiple processors operating in parallel. We review the basic dynamic programming method commonly used in sequential algorithms and adapt the theory to permit multiple processors to cooperatively solve the problem. Fast parallel algorithms exist that do not employ the basic dynamic programming method, but they require hypothetical computational architectures. We outline several practical approaches for parallelizing the basic method to run on existing architectures. Finally, we present results of our parallel implementations, written in C for the Encore Multimax, a 16-node shared-memory multiprocessor.
[Back to Doug] [Address] [Academics] [Honors] [Publications] [Presentations] [Public Service]