Loading article…
The Needleman–Wunsch algorithm is an algorithm used in bioinformatics to alignprotein or nucleotide sequences. It was one of the first applications of dynamic programming to compare biological sequences. The algorithm was developed by Saul B. Needleman and Christian D. Wunsch and published in 1970.[1] The algorithm essentially divides a large problem (e.g. the full sequence) into a series of smaller problems, and it uses the solutions to the smaller problems to find an optimal solution to the larger problem.[2] It is also sometimes referred to as the optimal matching algorithm and the global alignment technique. The Needleman–Wunsch algorithm is still widely used for optimal global alignment, particularly when the quality of the global alignment is of the utmost importance. The algorithm assigns a score to every possible alignment, and the purpose of the algorithm is to find all possible alignments having the highest score.
This algorithm can be used for any two strings. This guide will use two small DNA sequences as examples as shown in Figure 1:
GCATGCG GATTACA
First construct a grid such as one shown in Figure 1 above. Start the first string in the top of the third column and start the other string at the start of the third row. Fill out the rest of the column and row headers as in Figure 1. There should be no numbers in the grid yet.
Next, decide how to score each individual pair of letters. Using the example above, one possible alignment candidate might be:
12345678 GCATG-CGG-ATTACA
The letters may match, mismatch, or be matched to a gap (a deletion or insertion (indel)):
Each of these scenarios is assigned a score and the sum of the scores of all the pairings is the score of the whole alignment candidate. Different systems exist for assigning scores; some have been outlined in the Scoring systems section below. For now, the system used by Needleman and Wunsch[1] will be used:
For the Example above, the score of the alignment would be 0:
GCATG-CGG-ATTACA +−++−−+− −> 1*4 + (−1)*4 = 0
最初の行の最初の列（ヌクレオチドを含むセルを除く）をゼロから始めます。セルを1行ずつ見ていき、各セルのスコアを計算します。スコアは、セルの左、上、または左上（対角線）に隣接するセルのスコアを比較し、一致、不一致、または挿入・欠失に応じて適切なスコアを加算することによって計算されます。3つの可能性それぞれについて、候補スコアの最大値を取得します。
結果として得られた細胞のスコアは、3つの候補スコアの中で最も高い値である。
最初の行には「上」または「左上」のセルがないため、各セルのスコアを計算するには、左側の既存のセルのみを使用できます。したがって、前のスコアからの挿入・欠失を表すため、右にシフトするたびに -1 が加算されます。その結果、最初の行は 0、-1、-2、-3、-4、-5、-6、-7 となります。最初の列についても同様で、各セルの上にある既存のスコアのみを使用できます。したがって、結果として得られる表は次のようになります。
3方向すべてにスコアが存在する最初のケースは、最初の文字（この場合はGとG）の交点です。周囲のセルは以下のとおりです。
このセルには、3つの候補となる合計値があります。
最も高い候補は1で、セルに入力されます。
最も高い候補スコアを示したセルも記録する必要があります。上記の図1の完成図では、これは2行2列目のセルから1行1列目のセルへの矢印で表されます。
次の例では、XとYの両方の対角線上のステップが不一致を表しています。
X:
Y:
XとYの両方において、最高得点はゼロです。
最も高い候補スコアは、隣接する2つのセルによって達成される可能性がある。
この場合、最も高い候補スコアに達したすべての方向は、図1の完成した図の可能な始点セルとして記録する必要があります。たとえば、6行目と6列目のセルなどです。
このように表を埋めていくと、考えられるすべてのアライメント候補のスコアが得られ、右下のセルのスコアは最適なアライメントのスコアを表します。
右下のセルから左上のセルまで、矢印の方向に沿って経路をマークしてください。この経路から、以下のルールに従って数列が構築されます。
これらのルールに従うと、図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を使用しています。したがって、アライメントスコアが低いほど編集距離が大きくなり、このスコアリングシステムでは高いスコアが望ましいです。別のスコアリングシステムとしては、次のものが考えられます。
このシステムでは、アライメントスコアは2つの文字列間の編集距離を表します。状況に応じて異なるスコアリングシステムを考案できます。たとえば、ギャップがアライメントにとって非常に悪いとみなされる場合は、ギャップに大きなペナルティを与えるスコアリングシステムを使用できます。
より複雑なスコアリングシステムでは、変更の種類だけでなく、関連する文字にも値が割り当てられます。たとえば、AとAの一致には1が与えられますが、TとTの一致には4が与えられる場合があります。ここで（最初のスコアリングシステムを想定すると）、AよりもTの一致に重きが置かれ、つまりTの一致がアライメントにとってより重要であるとみなされます。この文字に基づく重み付けは、不一致にも適用されます。
文字のあらゆる組み合わせとそれによって得られるスコアを表現するために、類似度行列が使用されます。最も基本的なシステムの類似度行列は次のように表されます。
各スコアは、セルが一致させる文字の一方から他方への切り替えを表します。したがって、これは（ACGT のアルファベットの場合）すべての可能な一致と不一致を表します。すべての一致は対角線に沿って進むことに注意してください。また、スコアは相互であるため、表全体を埋める必要はなく、この三角形だけを埋めればよいのです。（A → C のスコア = C → A のスコア）。上記の TT = 4 ルールを適用すると、次の類似性行列が生成されます。
統計的に構築された様々なスコアリングマトリックスは、特定のシナリオに適した様々な行動に重み付けをしています。重み付けされたスコアリングマトリックスは、アミノ酸の種類によって出現頻度が異なるため、タンパク質配列アライメントにおいて特に重要です。スコアリングマトリックスには大きく分けて2つの種類があり、それぞれ特定のシナリオに合わせてさらに変更が加えられています。
配列をアラインメントすると、ギャップ（つまり挿入・欠失）が生じることが多く、時には大きなギャップが生じることもあります。生物学的には、大きなギャップは、複数の単一欠失ではなく、1つの大きな欠失として発生する可能性が高くなります。したがって、2つの小さな挿入・欠失は、1つの大きな挿入・欠失よりも悪いスコアになります。これを実現するシンプルで一般的な方法は、新しい挿入・欠失に対して大きなギャップ開始スコアを、挿入・欠失を延長する文字ごとに小さなギャップ延長スコアを設定することです。例えば、新しい挿入・欠失には-5、挿入・欠失には-1のコストがかかる場合があります。このようにして、次のようなアラインメントを作成します。
ガア G--AAT
複数の等しいアライメントを持つもの、複数の小さなアライメントを持つものは、次のようにアライメントされます。
ガア GAA----T
または、複数の小さなギャップよりも、4の長いギャップを持つ配置を優先します。
整列した文字のスコアは類似度行列によって指定されます。ここで、S ( a , b )は文字aとbの類似度です。ここではdと呼ばれる線形ギャップペナルティを使用します。
例えば、類似度行列が
次に、アライメントを行います。
AGACTAGTTAC CGA---GACGT
ギャップペナルティが-5の場合、スコアは次のようになります。
最も高いスコアを持つアライメントを見つけるために、2次元配列（または行列）Fが割り当てられます。行i、列jのエントリは、ここではで表されます。 シーケンスAの各文字に対して 1 行、シーケンスBの各文字に対して 1列があります。したがって、サイズnとmのシーケンスを整列する場合、使用されるメモリ量は次のようになります。ヒルシュベルグのアルゴリズムは配列のサブセットのみをメモリに保持し、スペースは不要だが、それ以外はNeedleman-Wunschと同様である（そして依然として時間）。
アルゴリズムが進むにつれて、最初のアライメントの最適なスコアとして割り当てられますAの文字と最初の文字Bの文字。最適性の原理は次のように適用されます。
したがって、F行列を計算するアルゴリズムの擬似コードは次のようになります。
d ← i = 0から長さ(A)までのギャップペナルティスコア F(i,0) ← d * i j = 0からlength (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) ← max (マッチ、挿入、削除) }F行列が計算されると、エントリすべての可能なアライメントの中で最大のスコアが得られます。実際にこのスコアが得られるアライメントを計算するには、右下のセルから始めて、その値を 3 つの可能なソース (上記のマッチ、挿入、削除) と比較して、それがどこから来たのかを確認します。マッチの場合、そして整列している場合、削除する場合は、ギャップに揃い、挿入する場合は、ギャップと整合している。（一般的に、複数の選択肢が同じ値を持つ場合があり、その結果、最適な整合が複数存在する可能性がある。）
配置A ← "" 配置B ← "" i ←長さ(A) j ← length (B) while (i > 0またはj > 0) { if (i > 0かつj > 0かつF(i, j) == F(i−1, j−1) + S(A i , B j )) { 配置A ← A i + 配置A AlignmentB ← B j + AlignmentB i ← i − 1 j ← j − 1 } else if (i > 0 and F(i, j) == F(i−1, j) + d) { 配置A ← A i + 配置A AlignmentB ← "−" + AlignmentB i ← i − 1 } それ以外 { アライメントA ← "−" + アライメントA AlignmentB ← B j + AlignmentB j ← j − 1 } }スコアの計算テーブルの各セルには操作。したがって、長さの 2 つのシーケンスに対するアルゴリズムの時間計算量は次のようになります。そしては[ 3 ]実行時間を改善できることが示されています。4人のロシア人法を使用する。[ 3 ] [ 4 ]アルゴリズムは表の空間計算量は[ 3 ]
NeedlemanとWunschによって記述されたアルゴリズムの本来の目的は、2つのタンパク質のアミノ酸配列の類似点を見つけることでした。[ 1 ]
NeedlemanとWunschは、アライメントがマッチとミスマッチのみによってペナルティを受け、ギャップにはペナルティがない場合（d = 0）について、アルゴリズムを明示的に説明しています。1970年の元の論文では、再帰が示唆されています。。
対応する動的計画法アルゴリズムは3乗時間を要する。また、この論文では、再帰処理によって任意のギャップペナルティ式に対応できることも指摘している。
ペナルティ係数（ギャップが発生するたびに減算される数値）は、ギャップの発生を阻止するための障壁として評価される場合がある。ペナルティ係数は、ギャップの大きさや方向、あるいはその両方に応じて決定される可能性がある。[444ページ]
同じ問題に対して、実行時間が2次であるより優れた動的計画法アルゴリズムが、後に1972年にDavid Sankoffによって導入されました[ 5 ]。同様の2次時間アルゴリズムは、1968年にTK Vintsyuk [ 6 ]によって音声処理（「タイムワーピング」 ）のために、また1974年にRobert A. WagnerとMichael J. Fischer [ 7 ]によって文字列照合のために独立に発見されました。
ニードルマンとヴンシュは、類似性を最大化するという観点から問題を定式化した。別の可能性としては、ウラジミール・レーベンシュタインによって導入された、配列間の編集距離を最小化する方法がある。ピーター・H・セラーズは1974年に[ 8 ]で、この2つの問題が等価であることを示した。
ニードルマン・ウンシュアルゴリズムは、特にグローバルアライメントの品質が極めて重要な場合において、最適なグローバルアライメントを行うために現在でも広く用いられています。しかしながら、このアルゴリズムは時間と空間の両面でコストが高く、2つの配列の長さの積に比例するため、長い配列には適していません。
最近の発展は、品質を維持しながらアルゴリズムの時間および空間コストを改善することに重点を置いている。たとえば、2013年にFast Optimal Global Sequence Alignment Algorithm (FOGSAA) [ 9 ]は、Needleman–Wunschアルゴリズムを含む他の最適なグローバルアライメント手法よりも高速にヌクレオチド/タンパク質配列をアライメントすることを提案した。この論文では、Needleman–Wunschアルゴリズムと比較した場合、FOGSAAは類似性の高いヌクレオチド配列（類似度>80%）で70～90%、類似度が30～80%の配列で54～70%の時間短縮を実現すると主張している。
ステレオマッチングは、一対のステレオ画像から3Dを再構成するプロセスにおいて不可欠なステップです。画像が補正された後、ヌクレオチド配列とタンパク質配列の整列と、走査線に属するピクセルのマッチングの間には類似性があります。どちらのタスクも、2つの文字列間の最適な対応関係を確立することを目的としているからです。
多くのアプリケーションでは、カメラの再切除やキャリブレーションなどによって画像補正を実行できますが、正確な補正モデルの計算コストがリアルタイムアプリケーションでの使用を妨げるため、不可能または非現実的な場合があります。さらに、雨滴、耐候性カバー、ほこりなどによって発生するような、カメラレンズに予期しない歪みがある場合、これらのモデルはどれも適していません。Needleman–Wunsch アルゴリズムを拡張することで、3 次元配列 (または行列) 内で最も高いスコアを持つアライメントを見つけることにより、「左」画像の線を「右」画像の曲線に関連付けることができます。実験では、このような拡張により、補正されていない画像または歪んだ画像間で高密度のピクセルマッチングが可能になることが実証されました。[ 10 ]
ニードルマン・ウンシュアルゴリズムは、人工ニューラルネットワークのアーキテクチャ比較にも応用されている。この手法は、前述の生物学的配列における類似性を識別するグローバル配列アライメントに着想を得ており、ニューラルネットワークを計算層またはブロックのシーケンスとして表現する。これらのシーケンスをアライメントすることで、アーキテクチャの類似性を原理的に定量化できる。
この方法は、ニューラルアーキテクチャ探索（NAS）において、特に進化アルゴリズムに基づくアプローチにおいて、成功裏に用いられてきた。アーキテクチャの類似性は、モデルのトレーニングを必要とせずに評価できるため、集団ベースの探索中に多様性をより効率的に誘導し、時期尚早な収束を防ぐことができる。[ 11 ]
