ニードルマン-ブンシュアルゴリズム

ウィキペディアから、無料の百科事典
ナビゲーションにジャンプ 検索にジャンプ
クラス配列アラインメント
最悪の場合の パフォーマンス
最悪の場合の スペースの複雑さ

Needleman-Wunschアルゴリズムは、タンパク質またはヌクレオチド配列整列させるためにバイオインフォマティクスで使用される アルゴリズムです。これは、生物学的配列を比較するための動的計画法の最初のアプリケーションの1つでした。このアルゴリズムは、ソールB.ニードルマンとクリスチャンD.ヴンシュによって開発され、1970年に公開されました。より大きな問題に対する最適な解決策を見つけるための問題。[2]これは、最適マッチングアルゴリズムと呼ばれることもあります。 グローバルアライメントテクニック。Needleman-Wunschアルゴリズムは、特にグローバルアラインメントの品質が最も重要である場合に、最適なグローバルアラインメントのために依然として広く使用されています。アルゴリズムは、すべての可能な配置にスコアを割り当てます。アルゴリズムの目的は、最高のスコアを持つすべての可能な配置を見つけることです。

図1:ニードルマン-ブンシュペアワイズ配列アラインメント

はじめに

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

GCATGCG
ガッタカ

グリッドの構築

まず、上の図1に示すようなグリッドを作成します。3番目の列の先頭で最初の文字列を開始し、3番目の行の先頭で他の文字列を開始します。図1のように、残りの列ヘッダーと行ヘッダーに入力します。グリッドにはまだ数字がないはずです。

G C A T G C G
 
G
A
T
T
A
C
A

スコアリングシステムの選択

次に、個々の文字のペアをスコアリングする方法を決定します。上記の例を使用すると、考えられるアライメント候補の1つは次のようになります。
12345678
GCATG-CG
G-ATTACA
文字は、一致、不一致、またはギャップに一致する可能性があります(削除または挿入(indel)):

  • 一致:現在のインデックスの2文字は同じです。
  • 不一致:現在のインデックスの2文字が異なります。
  • インデル(挿入または削除):最適な配置には、一方の文字をもう一方の文字列のギャップに配置することが含まれます。

これらの各シナリオにはスコアが割り当てられ、すべてのペアリングのスコアの合計がアライメント候補全体のスコアになります。スコアを割り当てるためのさまざまなシステムが存在します。いくつかは、以下のスコアリングシステムのセクションで概説されています。今のところ、NeedlemanとWunsch [1]が使用するシステムが使用されます。

  • 一致:+1
  • 不一致またはインデル:-1

上記の例の場合、アライメントのスコアは0になります。
GCATG-CG
G-ATTACA

+ − ++-+ − −> 1 * 4 +(−1)* 4 = 0

表に記入する

2行2列目のゼロから始めます。各セルのスコアを計算しながら、セルを1行ずつ移動します。スコアは、セルの左、左上、または左上(対角)に隣接するセルのスコアを比較し、一致、不一致、またはインデルの適切なスコアを追加することによって計算されます。3つの可能性のそれぞれについて候補スコアを計算します。

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

結果として得られるセルのスコアは、3つの候補スコアの中で最も高いものです。

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

G C A T G C G
0 -1 −2 −3 −4 −5 −6 −7
G -1
A −2
T −3
T −4
A −5
C −6
A −7

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

G
0 -1
G -1 バツ

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

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

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

G
0 -1
G -1 1

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

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

G C
0 -1 −2
G -1 1 バツ
A −2 Y

バツ:

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

Y:

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

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

G C
0 -1 −2
G -1 1 0
A −2 0

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

T G
T 1 1
A 0 バツ
  • 上:(1)+(-1)=(0)
  • 左上:(1)+(-1)=(0)
  • 左:(0)+(-1)=(-1)

この場合、最高の候補スコアに到達するすべての方向は、図1の完成した図、たとえば行と列の7のセルで、可能な起点セルとして記録する必要があります。

この方法で表に入力すると、考えられるすべての配置候補のスコアが得られます。右下のセルのスコアは、最適な配置の配置スコアを表します。

矢印を原点に戻す

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

  • 対角線の矢印は一致または不一致を表すため、元のセルの列の文字と行の文字が整列します。
  • 水平または垂直の矢印はインデルを表します。垂直方向の矢印は、ギャップ( "-")を行の文字( "side"シーケンス)に揃え、水平方向の矢印は、ギャップ( "-")を列の文字( "top"シーケンス)に揃えます。
  • 選択する矢印が複数ある場合、それらは線形の分岐を表します。2つ以上のブランチがすべて、右下から左上のセルへのパスに属している場合、それらは等しく実行可能な配置です。この場合、個別の配置候補としてパスに注意してください。

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

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

スコアリングシステム

基本的なスコアリングスキーム

最も単純なスコアリングスキームは、一致、不一致、およびインデルごとに値を与えるだけです。上記のステップバイステップガイドでは、match = 1、mismatch = -1、indel=-1を使用しています。したがって、位置合わせスコアが低いほど編集距離が長くなります。このスコアリングシステムでは、高いスコアが必要です。別のスコアリングシステムは次のとおりです。

  • 一致=0
  • インデル=1
  • 不一致=1

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

  • 一致=0
  • 不一致=1
  • インデル=10

類似性マトリックス

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

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

A G C T
A 1 -1 -1 -1
G -1 1 -1 -1
C -1 -1 1 -1
T -1 -1 -1 1

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

A G C T
A 1 -1 -1 -1
G -1 1 -1 -1
C -1 -1 1 -1
T -1 -1 -1 4

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

ギャップペナルティ

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

GAAAAAAT
G--AAT

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

GAAAAAAT
GAA----T

または、複数の小さなギャップよりも4つの長いギャップが優先されるアライメント。

アルゴリズムの高度なプレゼンテーション

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

たとえば、類似性マトリックスが

A G C T
A 10 -1 −3 −4
G -1 7 −5 −3
C −3 −5 9 0
T −4 −3 0 8

次に、配置:

AGACTAGTTAC
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つの列があります。したがって、サイズnmのシーケンスを整列させる場合、使用されるメモリの量は次のようになります。Hirschbergのアルゴリズムは、配列のサブセットのみをメモリに保持し、スペースですが、それ以外はNeedleman-Wunschに似ています(それでも必要です時間)。

アルゴリズムが進むにつれて、最初のアライメントの最適なスコアになるように割り当てられますAと最初の文字Bの文字次に、最適性の原則が次のように適用されます。

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

したがって、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)← max(一致、挿入、削除)
    }

F行列が計算されると、エントリ可能なすべての配置の中で最大のスコアを与えます。実際にこのスコアを与える配置を計算するには、右下のセルから開始し、値を3つの可能なソース(上記の[一致]、[挿入]、および[削除])と比較して、どちらからのものかを確認します。一致する場合は、整列されている場合、削除する場合、ギャップと位置合わせされ、挿入する場合は、ギャップと整列しています。(一般に、複数の選択肢が同じ値を持つ場合があり、代替の最適な配置につながります。)

AlignmentA←""
AlignmentB←""
i←長さ(A)
j←長さ(B)
 while(i>0またはj>0)
{{
    if(i>0かつj>0かつF(i、j)== F(i−1、j−1)+ S(A i、B j))
    {{
        AlignmentA← Ai + AlignmentA
        AlignmentB← Bj + AlignmentB
        i←i− 1
        j←j− 1
    }
    それ以外の 場合(i> 0かつF(i、j)== F(i-1、j)+ d)
    {{
        AlignmentA← Ai + AlignmentA
        AlignmentB←"−" + AlignmentB
        i←i− 1
    }
    そうしないと
    {{
        AlignmentA←"−" + AlignmentA
        AlignmentB← Bj + 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年のRobertA.WagnerとMichaelJ.Fischer [7]による文字列照合。

NeedlemanとWunschは、類似性を最大化するという観点から問題を定式化しました。別の可能性は、ウラジミール・レベンシュテインによって導入された、シーケンス間の編集距離を最小化することです。Peter H. Sellersは、1974年に[8]、2つの問題が同等であることを示しました。

Needleman-Wunschアルゴリズムは、特にグローバルアラインメントの品質が最も重要である場合に、最適なグローバルアラインメントのために依然として広く使用されています。ただし、このアルゴリズムは、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]

も参照してください

参照

  1. ^ a b c ニードルマン、ソールB.&ヴンシュ、クリスチャンD.(1970)。「2つのタンパク質のアミノ酸配列の類似性の検索に適用できる一般的な方法」。分子生物学ジャーナル48(3):443–53。土井10.1016 / 0022-2836(70)90057-4PMID5420325 _
  2. ^ 「バイオインフォマティクス」2014年9月10日取得
  3. ^ a b c Wing-Kin。、Sung(2010)。バイオインフォマティクスのアルゴリズム:実用的な紹介ボカラトン:チャップマン&ホール/CRCプレス。pp。34–35。ISBN 9781420070330OCLC429634761 _
  4. ^ マセック、ウィリアム; パターソン、マイケル(1980年2月)。「文字列編集距離を計算するより高速なアルゴリズム」コンピュータとシステム科学のジャーナル20:18–31。土井10.1016 / 0022-0000(80)90002-1
  5. ^ サンコフD(1972)。「削除/挿入の制約下でのシーケンスのマッチング」米国科学アカデミー紀要69(1):4–6。Bibcode1972PNAS ... 69....4S土井10.1073/pnas.69.1.4PMC427531_ PMID4500555_  
  6. ^ Vintsyuk TK(1968)。「動的計画法による音声弁別」。キベルネティカ4:81–88。土井10.1007/BF01074755S2CID123081024_ 
  7. ^ Wagner RA、Fischer MJ(1974)。「文字列間の修正の問題」。ACMのジャーナル21(1):168–173。土井10.1145/321796.321811S2CID13381535_ 
  8. ^ セラーズPH(1974)。「進化距離の理論と計算について」。応用数学に関するSIAMジャーナル26(4):787–793。土井10.1137/0126070
  9. ^ チャクラボルティ、アンガナ; Bandyopadhyay、Sanghamitra(2013年4月29日)。「FOGSAA:高速最適グローバルシーケンスアラインメントアルゴリズム」ScientificReports31746。Bibcode2013NatSR...3E1746C土井10.1038/srep01746PMC3638164_ PMID23624407_  
  10. ^ Thevenon、J; Martinez-del-Rincon、J; ディエニー、R; ネベル、JC(2012)。動的計画法を使用した、補正されていない画像と歪んだ画像の間の高密度ピクセルマッチングコンピュータビジョン理論と応用に関する国際会議。ローマ。

外部リンク