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.
[Back to Doug] [Address] [Academics] [Honors] [Publications] [Presentations] [Public Service]