Brutlag, D. L., Dautricourt, J. P., Diaz, R., Fier, J., Moxon, B. and Stamm, R. (1993). BLAZE: An implementation of the Smith-Waterman Comparison Algorithm on a Massively Parallel Computer. Computers and Chemistry, 17, 203-207.
Department of Biochemistry, Stanford University School of Medicine, Stanford CA, IntelliGenetics Inc., Mountain View California, MasPar Computer, Sunnyvale California.
We have implemented the Smith and Waterman dynamic programming
algorithm on the massively parallel MP1104 computer from MasPar and
compared its ability to detect remote protein sequence homologies
with that of other commonly used database search algorithms. Dynamic
programming algorithms are normally too computer intensive to permit
full databases search, however on the MP1104 a search of the
Swiss-Prot database takes about 15 seconds. This nearly interactive
speed of database searching permits one to optimize the parameters
for each query.
Most of the common database search methods (FASTA, FASTDB and BLAST)
gain their speed by using approximations such as word matching or
eliminating gaps from the alignments which prevents them from
detecting remote homologies. By using queries from protein super
families containing a large number of family members of diverse
similarities, we have measured the ability of each of these
algorithms to detect the remotest members of each super family. Using
these super families, we have found that the algorithms, in order of
decreasing sensitivity are BLAZE, FASTDB, FASTA and BLAST. Hence the
massively parallel computers allow one to have maximal sensitivity
and search speed simultaneously.
To
get Acrobat: 
[Back to Doug] [Address] [Academics] [Honors] [Publications] [Presentations] [Public Service]