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

Needleman–Wunsch

Needleman–Wunsch アルゴリズムはグローバルアラインメントを求めるアルゴリズムの 1 つである。

具体的な計算方法として、アラインメントを行う 2 つの配列を以下のように、碁盤のように縦と横に並べて配置する。例えば ATTGC と ATGC のアラインメントを求める場合は、下図のように並べる。

needleman-wunschアルゴリズム

アラインメント、つまり 2 つの配列を「都合よく」合わせるためには、様々な制限を付ける必要がある。「都合よく」合わせるためには、例えば、「塩基 A と塩基 C 」が対応するよりも「塩基 A と塩基 A 」が対応した方がいい、といったルールが必要である。機械的にこのルールを実現するにはスコアと呼ばれるものを定義する必要がある。

2 つの配列を並べた時、各位置における塩基は 3 通りの状況が考えられる。

  • 2 つの配列を並べた時、位置 p にある 2 つの塩基が一致する場合。(マッチ)
  • 2 つの配列を並べた時、位置 p にある 2 つの塩基が不一致する場合。(ミスマッチ)
  • 2 つの配列を並べた時、位置 p において、片方の配列の塩基に対して、もう片方の配列の塩基が存在しない場合。(ギャップ)

ここでは計算が簡単に行えるように、マッチの場合は +2 点、ミスマッチは -1 点、ギャップは -2 点と定義する。(スコアの定義は生物種や実験の目的などに応じて決める必要がある、ここでは省略する。)

以上のスコアの定義を文字式で書くと、s(A, A) = 2、s(A, B) = -1、 s(A, -) = s(-, A) = -2 となる(ただし、A, B は塩基であり、かつ、A ≠ B)。また、ギャップの挿入による課されるペナルティは文字 d と表される場合が多い、従って、上の例では d = 2 となる。d はペナルティであるから正数である。

アラインメントは次のアルゴリズムに従って、1 格子ずつ計算する。

\[ \begin{equation} F(i, j) = \max\left\{ \begin{array}{ll} 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} \]

F(0, 0) = 0 として計算を進める。まず、F(1, 0)を計算する。

\[ \begin{equation} F(1, 0) = \max\left\{ \begin{array}{ll} F(0, -1) + s(x_{i}, y_{j}) \\ F(0, 0) - d\\ F(1, -1) - d \end{array} \right\} \end{equation} \]

F(0, -1) および F(1, -1) は値が存在しないため、ここでは計算を行わない。そのため、F(1, 0) = F(0, 0) = -d = -2になります。同様にして計算を進め、F(n, 0) = -nd、F(0, n) = -nd が求まる。

needleman-wunschアルゴリズム

次に、F(1, 1) を求める。F(1, 1) の格子では、2 つの塩基がともに A であるから、スコアの定義により、s(A, A) = 2。また、ペナルティ d = 2 であるから、F(1, 1) は以下のように計算される。

\[ \begin{equation} F(1, 1) = \max\left\{ \begin{array}{ll} F(0, 0) + 2 = 0 + 2 \\ F(0, 1) - 2 = -2 -2\\ F(1, 0) - 2 = -2 -2 \end{array} \right\} \end{equation} \]

F(1, 1) = F(0, 0) + 2 で計算されたものが最もスコアが高いことがわかる。以下のように、F(1, 1) のスコアを 2 とし、そのスコアは F(0, 0) から計算されていることがわかるように矢印を描き入れる。

needleman-wunschアルゴリズム

このように、格子を 1 つずつ計算していく。例えば、F(3, 2) の値については、次のように計算できる。

\[ \begin{equation} F(3, 2) = \max\left\{ \begin{array}{ll} F(2, 1) + 2 = 0 + 2 \\ F(3, 1) - 2 = -2 -2\\ F(2, 2) - 2 = 4 -2 \end{array} \right\} \end{equation} \]

F(3, 2) が最大値を与えるのは F(2, 1) と F(2, 2) の 2 つが確認できる。 この場合、下図のように両方に矢印を描き入れておく。(※下図では、F(3, 2) への道のりがわかりやすいように、それ以外の矢印を省略した。)

needleman-wunschアルゴリズム

最後の格子まで計算し終えたときの値がグローバルアラインメントのスコアとなる。この例では 6 となった。)

needleman-wunschアルゴリズム

そこで、グローバルアラインメントを作成するには、図に記録した矢印に従って、矢印方向をさかのぼることでアラインメントを作成する。

結果1(スコア:6)
ATTGC
AT-GC


結果2(スコア:6)
ATTGC
A-TGC