From Wikipedia,
the free encyclopedia.
The Smith-Waterman algorithm
is a well-known algorithm for
performing local sequence
alignment; that is, for
determining similar regions
between two nucleotide or protein
sequences. The algorithm was first
proposed by
Temple Smith and
Michael Waterman in 1981. Like
the
Needleman-Wunsch algorithm, on
which it is a variation,
Smith-Waterman is a
dynamic programming algorithm.
As such, it has the desirable
property that it is guaranteed to
find the optimal local alignment
with respect to the scoring system
being used (which includes the
substitution matrix and the
gap-scoring scheme). However, the
Smith-Waterman algorithm is fairly
demanding of time and memory
resources: in order to align two
sequences of lengths m and n, O(mn)
time and space are required. As a
result, it has largely been
replaced in practical use by the
BLAST algorithm; although not
guaranteed to find optimal
alignments, BLAST is much more
efficient.
References
