Smith-Waterman はローカルアラインメントを求めるアルゴリズムである。グローバルアラインメントは、アラインメントする配列同士の両端を揃える必要があるのに対して、ローカルアラインメントの場合は、両端を揃えなくてもよい。そのため、2 つの配列の間に、保存度の高い領域と保存度の低い領域の両方が存在する時によく利用される。
例えば、次のような 2 つの配列を考える。
sequence 1 ACCACGATGCATGCTATTAGCTAGCCGAT
sequence 2 AAGCAAGCCTGTCATTAGCTAGCCGGAローカルアラインメントを行う上で、両端を揃える必要がなく、局所的にアラインメントを行うことができるため、以下のようにアラインメントができる。2 箇所アラインメントされていることがわかる。
sequence 1 ACCACGAAGCATGCTTTTTCGCTAGCCGAT
||||||| ||||||||
sequence 2 --AAGCAAGCATGTCATCAAGCTAGCCGGAこのようにローカルアラインメントを行う Smith-Waterman のアルゴリズム次の式で表すことができる。グローバルアラインメントを求める Needleman–Wunsch アルゴリズムの場合、スコアが負数でも構わないが、Smith-Waterman アルゴリズムの場合は、スコアが負数とならないように制限条件が付け加えられている。この制限条件がローカルアラインメントを可能にしている。
\[
\begin{equation}
F(i, j) = \max\left\{
\begin{array}{ll}
0 \\
F(i-1, j-1) + s(x_{i}, y_{j}) \\
F(i-1, j) - d\\
F(i, j-1) - d
\end{array}
\right\}
\end{equation}
\]
アラインメントを求めるアルゴリズムは、グローバルアラインメントを求める Needleman–Wunsch アルゴリズムと同じ方法でアラインメントを求める。Smith-Waterman アルゴリズムと Needleman–Wunsch アルゴリズムは、基本的にスコアの定義以外は同じである。