ローカルアラインメントを求めるアルゴリズム

Smith-Waterman

Smith-Waterman はローカルアラインメントを求めるアルゴリズムである。

グローバルアラインメントは、アラインメントする配列同士の両端を揃える必要があるのに対して、ローカルアラインメントの場合は、両端を揃えなくてもよい。そのため、2 つの配列の間に、保存度の高い領域と保存度の低い領域の両方が存在する時によく利用される。

例えば、次のような 2 つの配列を考える。

配列1  ACCACGATGCATGCTATTAGCTAGCCGAT
配列2  AAGCAAGCCTGTCATTAGCTAGCCGGA

ローカルアラインメントを行う上で、両端を揃える必要がなく、局所的にアラインメントを行うことができるため、以下のようにアラインメントができる。2 箇所アラインメントされていることがわかる。

配列1  ACCACGAAGCATGCTTTTTCGCTAGCCGAT
           |||||||       |||||||
配列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 アルゴリズムと同じ方法でアラインメントを求める。