Galper, A. R. and Brutlag, D. L. (1990). Parallel Similarity Search and Alignment with the Dynamic Programming Method (KSL Report 90-74). Stanford University.
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.
To
get Acrobat: 
[Back to Doug] [Address] [Academics] [Honors] [Publications] [Presentations] [Public Service]