[Back to Doug] [Address] [Academics] [Honors] [Publications] [Presentations] [Public Service]

Galper, A. R. and Brutlag, D. L. (1990). Parallel Similarity Search and Alignment with the Dynamic Programming Method (KSL Report 90-74). Stanford University.

Parallel Similarity Search and Alignment with the Dynamic Programming Method

A. R. Galper & D. L. Brutlag

Department of Biochemistry & the Section on Medical Informatics, Stanford University School of Medicine, Stanford, California 94305-5307.

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.

Full Text: To get Acrobat:

[Back to Doug] [Address] [Academics] [Honors] [Publications] [Presentations] [Public Service]