Collins et al. [58][15] are responsible for much of the
early work on scanning sequence databases with dynamic programming.
They implemented a variant of the Smith and Waterman [30]
algorithm on the parallel AMT-DAP computer. This provided them with
sufficient processing speed to not only record the top scoring local
alignment between the query and each sequence, but also to record
alternative local alignments. As such, the DAP implementation of
local alignment with gaps is currently the only program to provide
this service on the Internet (Send the text HELP to
dapmail@biocomp.ed.ac.uk). Collins et al. [59][15]
also provide a method to estimate the statistical significance of
their alignments. They fit a straight line to , where
is the number of aligments with a given score, versus score
to the lower 97%of the top 16,384 alignments, then express the score
for alignment as a probability derived from the distance from this
line. This scoring method was used since there is currently no formal
statistical method of estimating the expected score for a local
alignment with gaps. The Collins et al approach provides a
convenient way of correcting for changes in the score distribution for
unrelated alignments due to differences in composition and length of
the query sequence database.
A development of Collins' work is a parallel Smith-Waterman implementation for the MasPar range of massively parallel computers [60]. Scans can be made using this program using a service at EMBL Heidelberg (Send the text HELP to BLITZ@embl-heidelberg.de). Unfortunately, the BLITZ service currently only returns a single top scoring alignment, but like the DAP program it gives an estimate of the alignment significance. A further Smith-Waterman implementation (BLAZE) has been developed by Intelligenetics and is commercially available for the MasPar. The GenQuest system at Oak Ridge National Laboratory USA, also supports database searching with the Smith-Waterman algorithm using a specialised parallel computing environment (send the text HELP to grail@ornl.gov for instructions).