ニードルマン・ヴンシュアルゴリズム

図 1: Needleman-Wunsch ペアワイズ配列アライメント
クラス	配列アライメント
最悪の場合の パフォーマンス	${\displaystyle O(mn)}$
最悪の場合の 空間複雑度	${\displaystyle O(mn)}$

Needleman –Wunsch アルゴリズムは、バイオインフォマティクスで タンパク質またはヌクレオチド配列をアラインメントするために使用されるアルゴリズムです。これは、生物学的配列を比較するための動的プログラミングの最初のアプリケーションの 1 つです。このアルゴリズムは、Saul B. Needleman と Christian D. Wunsch によって開発され、1970 年に公開されました。^[1]このアルゴリズムは基本的に、大きな問題 (完全な配列など) を一連の小さな問題に分割し、小さな問題の解決策を使用して、大きな問題の最適解を見つけます。^{[2]これは、}最適マッチングアルゴリズムやグローバル アラインメントテクニックと呼ばれることもあります。Needleman–Wunsch アルゴリズムは、特にグローバル アラインメントの品質が最も重要である場合に、最適なグローバル アラインメントに今でも広く使用されています。このアルゴリズムは、考えられるすべてのアラインメントにスコアを割り当て、最高のスコアを持つ考えられるすべてのアラインメントを見つけることが目的です。

このアルゴリズムは、任意の 2 つの文字列に使用できます。このガイドでは、図 1 に示すように、2 つの小さなDNA 配列を例として 使用します。

GCATGCG
ガタカ

まず、上の図 1 のようなグリッドを作成します。最初の文字列を 3 列目の先頭から開始し、もう 1 つの文字列を 3 行目の先頭から開始します。図 1 のように、列と行の残りのヘッダーを入力します。グリッドにはまだ数字はありません。

次に、各文字のペアにスコアを付ける方法を決定します。上記の例を使用すると、考えられる配置候補の 1 つは次のようになります。

12345678
GCATG-CG
G-アッタカ

文字は一致する場合も、不一致の場合も、ギャップ（削除または挿入（インデル））と一致する場合もあります。

• 一致: 現在のインデックスの 2 つの文字は同じです。
• 不一致: 現在のインデックスの 2 つの文字が異なります。
• インデル (挿入または削除): 最適な配置では、1 つの文字が他の文字列のギャップに揃えられます。

これらのシナリオにはそれぞれスコアが割り当てられ、すべてのペアリングのスコアの合計がアライメント候補全体のスコアになります。スコアを割り当てるにはさまざまなシステムがあり、その一部は以下のスコアリングシステムのセクションで概説されています。ここでは、NeedlemanとWunsch ^{[1] [検証失敗]}が使用したシステムを使用します。

• マッチ: +1
• 不一致または挿入: −1

上記の例では、アライメントのスコアは 0 になります。

GCATG-CG
G-アッタカ
+−++−−＋− −> 1*4 + (−1)*4 = 0

最初の行、最初の列の 0 から始めます (ヌクレオチドを含むセルは含みません)。行ごとにセルを移動し、各セルのスコアを計算します。スコアは、セルの左、上、または左上 (対角) に隣接するセルのスコアを比較し、一致、不一致、またはインデルの適切なスコアを追加することによって計算されます。3 つの可能性のそれぞれについて、候補スコアの最大値を取得します。

• 上部または左のセルからのパスはインデルペアリングを表すため、左と上部のセルのスコアを取得し、それぞれにインデルのスコアを追加します。
• 対角パスは一致/不一致を表すため、左上の対角セルのスコアを取得し、行と列の対応するベース (文字) が一致する場合は一致のスコアを加算し、一致しない場合は不一致のスコアを加算します。

セルの結果スコアは、3 つの候補スコアのうち最も高いスコアになります。

最初の行には「上」または「左上」のセルがないため、各セルのスコアを計算するために使用できるのは、左側の既存のセルのみです。したがって、右にシフトするたびに -1 が追加されます。これは、前のスコアからのインデルを表すためです。この結果、最初の行は 0、-1、-2、-3、-4、-5、-6、-7 になります。最初の列にも同じことが当てはまり、各セルの上にある既存のスコアのみを使用できます。したがって、結果の表は次のようになります。

3 方向すべてにスコアが存在する最初のケースは、最初の文字 (この場合は G と G) の交差点です。周囲のセルは以下のとおりです。

このセルには 3 つの候補合計があります。

• 対角左上の隣のスコアは0です。GとGのペアは一致しているので、一致のスコアを加算します: 0+1 = 1
• 一番上の隣接ノードのスコアは−1で、そこから移動するとインデルとなるため、インデルのスコアを加算します: (−1) + (−1) = (−2)
• 左隣の配列もスコア−1を持ち、インデルを表し、(−2)も生成します。

最も高い候補は 1 で、セルに入力されます。

最も高い候補スコアを与えたセルも記録する必要があります。上の図 1 の完成した図では、これは行 2 列目のセルから行 1 列目のセルへの矢印として表されています。

次の例では、X と Y の両方の対角ステップが不一致を表しています。

バツ:

• 上: (−2)+(−1) = (−3)
• 左: (+1)+(−1) = (0)
• 左上: (−1)+(−1) = (−2)

や:

• 上: (1)+(−1) = (0)
• 左: (−2)+(−1) = (−3)
• 左上: (−1)+(−1) = (−2)

X と Y の両方で、最高スコアは 0 です。

最高の候補スコアは、隣接するセルのうちの 2 つによって達成される可能性があります。

• 上: (1)+(−1) = (0)
• 左上: (1)+(−1) = (0)
• 左: (0)+(−1) = (−1)

この場合、最高の候補スコアに達するすべての方向は、図 1 の完成した図の可能な起点セルとして記録される必要があります (例: 行 6 列のセル)。

このように表に記入すると、すべての可能なアライメント候補のスコアが表示され、右下のセルのスコアは最適なアライメントのアライメント スコアを表します。

矢印の方向に従って、右下のセルから左上のセルに戻るパスをマークします。このパスから、次のルールに従ってシーケンスが構築されます。

• 斜めの矢印は一致または不一致を表し、元のセルの列の文字と行の文字が揃います。
• 水平または垂直の矢印はインデルを表します。垂直の矢印はギャップ (「-」) を行の文字 (「サイド」シーケンス) に揃え、水平の矢印はギャップを列の文字 (「トップ」シーケンス) に揃えます。
• 選択できる矢印が複数ある場合、それらはアラインメントの分岐を表します。2 つ以上の分岐がすべて右下のセルから左上のセルまでのパスに属している場合、それらは同等に実行可能なアラインメントです。この場合、パスは個別のアラインメント候補として記録されます。

これらのルールに従うと、図 1 の 1 つの可能なアライメント候補の手順は次のようになります。

G → CG → GCG → -GCG → T-GCG → AT-GCG → CAT-GCG → GCAT-GCG 
A → CA → ACA → TACA → TTACA → ATTACA → -ATTACA → G-ATTACA
             ↓
    (ブランチ) → TGCG → -TGCG → ...
             → TACA → TTACA → ...

最も単純なスコアリング方式では、一致、不一致、および挿入のそれぞれに値を与えるだけです。上記のステップバイステップのガイドでは、一致 = 1、不一致 = −1、挿入 = −1 を使用しています。したがって、アライメント スコアが低いほど編集距離は大きくなり、このスコアリング システムでは高いスコアが望まれます。別のスコアリング システムとしては、次のようなものがあります。

• マッチ = 0
• インデル = -1
• 不一致 = -1

このシステムでは、アラインメント スコアは 2 つの文字列間の編集距離を表します。状況に応じて異なるスコアリング システムを考案できます。たとえば、ギャップがアラインメントにとって非常に悪いと判断された場合は、ギャップに重いペナルティを課す次のようなスコアリング システムを使用できます。

• マッチ = 1
• インデル = -10
• 不一致 = -1

より複雑なスコアリング システムでは、変更の種類だけでなく、関係する文字にも値が付けられます。たとえば、A と A の一致には 1 が与えられますが、T と T の一致には 4 が与えられます。ここでは (最初のスコアリング システムを想定)、A よりも T の一致に重点が置かれます。つまり、T の一致はアラインメントにとってより重要であると想定されます。文字に基づくこの重み付けは、不一致にも適用されます。

文字の可能なすべての組み合わせとその結果のスコアを表すために、類似度マトリックスが使用されます。最も基本的なシステムの類似度マトリックスは次のように表されます。

各スコアは、セルが一致する文字の 1 つから他の文字への切り替えを表します。したがって、これはすべての可能な一致と不一致を表します (ACGT のアルファベットの場合)。すべての一致は対角線に沿っていることに留意してください。また、スコアは相互的であるため、テーブル全体を記入する必要はなく、この三角形のみ記入する必要があります。= (A → C のスコア = C → A のスコア)。上記の TT = 4 ルールを実装すると、次の類似性マトリックスが生成されます。

さまざまなスコアリング マトリックスが統計的に構築されており、特定のシナリオに適したさまざまなアクションに重みが与えられます。重み付けされたスコアリング マトリックスを持つことは、さまざまなアミノ酸の頻度が異なるため、タンパク質配列のアラインメントにおいて特に重要です。スコアリング マトリックスには 2 つの大きなファミリーがあり、それぞれ特定のシナリオに合わせてさらに変更が加えられています。

• パム
• ブロサム

配列をアラインメントすると、ギャップ (つまりインデル) がしばしば発生し、大きなギャップが発生することもあります。生物学的には、大きなギャップは、複数の単一欠失ではなく、1 つの大きな欠失として発生する可能性が高くなります。したがって、2 つの小さなインデルは、1 つの大きなインデルよりもスコアが低くなります。これを行う簡単で一般的な方法は、新しいインデルに対して大きなギャップ開始スコアを使用し、インデルを拡張するすべての文字に対してより小さなギャップ拡張スコアを使用することです。たとえば、新しいインデルは -5 のコスト、拡張インデルは -1 のコストになります。この方法では、次のようなアラインメントが考えられます。

ガァァァァァァ
G--AAT

複数の等しい配置を持つものもあれば、複数の小さな配置を持つものもあり、次のように配置されます。

ガァァァァァァ
GAA----T

または、複数の小さなギャップよりも 4 の長いギャップを優先する配置。

整列した文字のスコアは類似度マトリックスによって指定されます。ここで、S ( a , b ) は文字aとbの類似度です。ここではdと呼ばれる線形ギャップペナルティを使用します。

例えば、類似度行列が

次に配置します:

アガクタタック
CGA---GACGT

ギャップペナルティが -5 の場合、スコアは次のようになります。

S (A,C) + S (G,G) + S (A,A) + (3 × d ) + S (G,G) + S (T,A) + S (T,C) + S (A,G) + S (C,T)

= −3 + 7 + 10 − (3 × 5) + 7 + (−4) + 0 + (−1) + 0 = 1

最高スコアのアラインメントを見つけるために、2 次元配列(または行列) Fが割り当てられます。ここでは、 行iと列jのエントリは で示されます。シーケンスAの各文字に対して 1 つの行があり、シーケンスBの各文字に対して 1 つの列があります。したがって、サイズnとmのシーケンスをアラインメントする場合、使用されるメモリの量は です。Hirschbergのアルゴリズムは、メモリ内に配列のサブセットのみを保持し、スペースを使用しますが、それ以外は Needleman-Wunsch と似ています (それでも時間がかかります)。 ${\displaystyle F_{ij}}$${\displaystyle O(nm)}$${\displaystyle \Theta (\min\{n,m\})}$${\displaystyle O(nm)}$

アルゴリズムが進むにつれて、 はAの最初の文字とBの最初の文字の配置の最適スコアとして割り当てられます。最適性の原則は次のように適用されます。 ${\displaystyle F_{ij}}$${\displaystyle i=0,\dotsc ,n}$${\displaystyle j=0,\dotsc,m}$

• 基礎：

${\displaystyle F_{0j}=d*j}$

${\displaystyle F_{i0}=d*i}$

• 最適性の原則に基づく再帰:

${\displaystyle F_{ij}=\max(F_{i-1,j-1}+S(A_{i},B_{j}),\;F_{i,j-1}+d,\;F_{i-1,j}+d)}$

したがって、F 行列を計算するアルゴリズムの疑似コードは次のようになります。

d ← i = 0から長さ(A)までのギャップペナルティスコア
 
    F(i,0) ← d * i
j = 0から 長さ(B)
    F(0,j) ← d * j
i = 1から 長さ(A)
     j = 1から 長さ(B)
    {
        マッチ ← F(i−1, j−1) + S(A i , B j )
        削除 ← F(i−1, j) + d
        ← F(i, j−1) + dを挿入
        F(i,j) ←最大(一致、挿入、削除)
    }

Fマトリックスが計算されると、エントリはすべての可能なアラインメントの中で最大のスコアを与えます。実際にこのスコアを与えるアラインメントを計算するには、右下のセルから始めて、値を 3 つの可能なソース (上記の Match、Insert、Delete) と比較して、その値がどこから来たのかを確認します。Match の場合、およびはアラインされ、Delete の場合、はギャップを伴ってアラインされ、Insert の場合、はギャップを伴ってアラインされます。(一般に、複数の選択肢が同じ値を持つ場合があり、代替の最適なアラインメントにつながります。) ${\displaystyle F_{nm}}$${\displaystyle A_{i}}$${\displaystyle B_{j}}$${\displaystyle A_{i}}$${\displaystyle B_{j}}$

配置A ← ""
配置B ← ""
i ←長さ(A)
j ←長さ(B)
 （ i > 0またはj > 0）
{
    i > 0かつj > 0かつF(i, j) == F(i−1, j−1) + S(A i , B j )の場合
    {
        アライメントA ← A i + アライメントA
        アライメントB ← B j + アライメントB
        私 ← 私 − 1
        j ← j − 1
    }
    そうでない 場合(i > 0かつF(i, j) == F(i−1, j) + d)
    {
        アライメントA ← A i + アライメントA
        アライメントB ← "−" + アライメントB
        私 ← 私 − 1
    }
    それ以外
    {
        アライメントA ← "−" + アライメントA
        アライメントB ← B j + アライメントB
        j ← j − 1
    }
}

表の各セルのスコアを計算することは操作である。したがって、長さが との2つのシーケンスに対するアルゴリズムの時間計算量は である。^[3] Four Russians法を使用すると実行時間を まで改善できることが示されている。^{[3] [4]}アルゴリズムは表を埋めるため、空間計算量は^{[3]である。}${\displaystyle F_{ij}}$${\displaystyle O(1)}$${\displaystyle n}$${\displaystyle m}$${\displaystyle O(mn)}$${\displaystyle O(mn/\log n)}$${\displaystyle n\times m}$${\displaystyle O(mn).}$

ニードルマンとヴンシュが説明したアルゴリズムの本来の目的は、2つのタンパク質のアミノ酸配列の類似点を見つけることでした。^[1]

Needleman と Wunsch は、アラインメントが一致と不一致によってのみペナルティを受け、ギャップにはペナルティがない ( d =0)場合のアルゴリズムを明示的に説明しています。1970 年の元の出版物では、再帰 が提案されています。 ${\displaystyle F_{ij}=\max _{h<i,k<j}\{F_{h,j-1}+S(A_{i},B_{j}),F_{i-1,k}+S(A_{i},B_{j})\}}$

対応する動的プログラミングアルゴリズムは 3 乗の時間がかかります。この論文では、再帰によって任意のギャップペナルティ式に対応できることも指摘しています。

ギャップを許容することに対する障壁として、ギャップが生じるたびに減算される数値であるペナルティ係数が評価されることがあります。ペナルティ係数は、ギャップの大きさや方向の関数である可能性があります。[444 ページ]

同じ問題（ギャップペナルティなし）に対して2次実行時間を持つより優れた動的計画法アルゴリズムは、後に1972年にDavid Sankoffによって導入されました^[5]。同様の2次時間アルゴリズムは、1968年にTK Vintsyuk ^[6]によって音声処理（「タイムワーピング」）用に、また1974年にRobert A. WagnerとMichael J. Fischer ^[7]によって文字列マッチング用に独立して発見されました。

ニードルマンとヴンシュは類似性を最大化するという観点から問題を定式化した。もう一つの可能​​性は、ウラジミール・レーベンシュタインが提唱したシーケンス間の編集距離を最小化することである。ピーター・H・セラーズは1974年に^[8]、この2つの問題は同等であることを示した。

Needleman-Wunsch アルゴリズムは、特にグローバル アラインメントの品質が最も重要である場合に、最適なグローバル アラインメントに今でも広く使用されています。ただし、このアルゴリズムは、2 つのシーケンスの長さの積に比例して時間とスペースの点でコストがかかるため、長いシーケンスには適していません。

最近の開発では、品質を維持しながらアルゴリズムの時間と空間のコストを改善することに重点が置かれています。たとえば、2013 年には、高速最適グローバル配列アライメント アルゴリズム (FOGSAA) ^{[9] が}、Needleman–Wunsch アルゴリズムを含む他の最適グローバル アライメント方法よりも高速にヌクレオチド/タンパク質配列をアライメントすることを提案しました。この論文では、Needleman–Wunsch アルゴリズムと比較した場合、FOGSAA は類似性の高いヌクレオチド配列 (類似度 > 80%) で 70～90%、類似度 30～80% の配列で 54～70% の時間短縮を実現すると主張しています。

ステレオマッチングは、一対のステレオ画像から 3D を再構築するプロセスにおいて不可欠なステップです。画像が修正されると、ヌクレオチドとタンパク質の配列を整列させることと、スキャン ラインに属するピクセルをマッチングさせることの間に類似点が生まれます。これは、両方のタスクが 2 つの文字列間の最適な対応を確立することを目的としているためです。

多くのアプリケーションでは、カメラの再切除やキャリブレーションなどによって画像の補正を行うことができますが、正確な補正モデルの計算コストがリアルタイムアプリケーションでの使用を妨げるため、不可能または非実用的になる場合があります。さらに、これらのモデルは、雨滴、耐候性カバー、ほこりなどによってカメラレンズに予期しない歪みが発生する場合には適していません。Needleman–Wunsch アルゴリズムを拡張すると、3 次元配列 (またはマトリックス) で最高スコアの位置合わせを見つけることで、「左」画像の線を「右」画像の曲線に関連付けることができます。実験では、このような拡張により、補正されていない画像や歪んだ画像間での高密度のピクセルマッチングが可能になることが実証されています。^[10]

• ワグナー・フィッシャーアルゴリズム
• スミス・ウォーターマンアルゴリズム
• シーケンスマイニング
• レーベンシュタイン距離
• ダイナミックタイムワーピング
• 配列アライメント

• NW-align: Needleman-Wunsch アルゴリズムによるタンパク質配列間のアラインメント プログラム (オンライン サーバーとソース コード)
• Needleman–Wunsch のライブ Javascript デモ
• Needleman-Wunsch アルゴリズムのインタラクティブな Javascript ベースの視覚的説明
• テクノロジーブログの配列アライメント技術
• Needleman–Wunsch アルゴリズムなどを実装した Biostrings R パッケージ