Needleman Wish Algorithm-Wikipedia

Posted on May 16, 2021 by lordneo

before-content-x4

Needleman Wish Algorithm バイオインフォマティクスの最適化アルゴリズムです。そこでは、2つのヌクレオチドまたはアミノ酸配列を比較するために使用されます。モデルを使用して、最適なグローバル類似性スコアを計算するか、2つのシーケンス間で1つ以上の最適なグローバルアライメントをバックトラックするのに役立ちます。類似性スコアは、2つのシーケンスの類似性の尺度です。スコアが高いほど、スコアリングモデルの下のシーケンスは使用されます。アルゴリズムは、アライメントのスコアを最適化します。アラインメントは、最初のシーケンスを2番目のシーケンスに転送するための編集手順のエピソードです。 2つの非自明なシーケンスには多くのアラインメントがあります。最適なアライメントには、最大類似性スコアがあります。このアルゴリズムは、動的プログラミングの方法を使用し、編集手順にスコアリングモデル（つまり、一般的なギャップコストの使用）を許可します。

after-content-x4

シーケンスAおよびBの可能なプレフィックスのすべてのカップルのマトリックスでは、needleman-wunsch-dpアルゴリズムは、最適なグローバル類似性アライメントスコアを計算します。要素

{displaystyle I、j}

$i,j$ マトリックスには、部分シーケンスの最適なグローバルアライメントの最適スコアが含まれています

{displaystyle a [0..i]}

$a[0..i]$ との

{displaystyle b [0..j]}

$b[0..j]$ bから。スペル

{displaystyle a [0..i]}

$a[0..i]$ I-Ten Praefixに対応します

{displaystyle a_ {1}、a_ {2}、dots、a_ {i}}

$a_1, a_2,dots,a_i$ から。 mがaまたはnのシーケンス長をbのシーケンス長を示す場合、スコアマトリックスmに含まれる

{displaystyle m+1}

$m+1$ 線と

after-content-x4

{displaystyle n+1}

$n+1$ 列。完全なシーケンスのアライメントスコアは、のアルゴリズムの実行にあります

{displaystyle m（m、n）}

$M(m,n)$ 含む。

スコアマトリックスは再帰的に計算されます。要素（i、j）の場合、マトリックスMは3つのケースで最大化されます。シーケンスの前のアライメントの拡張

{displaystyle a [0..i-1]}

$a[0..i-1]$ と

{displaystyle b [0..j-1]}

$b[0..j-1]$ 試合またはマスマッチの周りで、以前に計算されたスコアの追加が対応します

{displaystyle m（i-1、j-1）}

$M(i-1,j-1)$ 交換の費用

{displaystyle a [i]}

$a[i]$ 終えた

{displaystyle b [j]}

$b[j]$ 。最終的な削除によって既に計算されたアライメントの拡張は、削除の長さの一般的なギャップコストの追加に対応し、シーケンスの最適なアライメントのスコアに対応します

{displaystyle a [0..i-k]}

$a[0..i-k]$ と

{displaystyle b [0..j]}

$b[0..j]$ 、それによって

{displaystyle k}

$k$ 削除の長さ。削除に類似して、シーケンスの最適なアライメントの拡張は対応します

{displaystyle a [0..i]}

$a[0..i]$ と

{displaystyle b [0..j-l]}

$b[0..j-l]$ このアライメントのスコアの追加とギャップの長さのコストの最後の挿入に

{displaystyle l}

$l$ 挿入。これらの3つの選択肢の最大値は要素にあります

{displaystyle m（i、j）}

$M(i,j)$ 保存。

ギャップコスト関数は一般的です。 D. h。均一なコストまたはアフィンギャップコストが使用されることは必須ではありません。

これまでに説明されているマトリックス再帰は、次のセクションで正式に書き留められています。再帰の依存関係を考慮するには、スコアマトリックスを線または列に計算する必要があります。

アライメントは、追跡を焼くことで出力できます。可能なバックトラッキングプロセスとして、スコアマトリックスの計算中に各要素の補助マトリックスでできます

{displaystyle（i、j）}

$(i,j)$ 最大値が挿入、削除、または一致によって計算されたかどうかを保存します。要素の

{displaystyle（n、m）}

$(n,m)$ マトリックス

{displaystyle m}

$M$ マトリックスの完全な計算後、パスを追跡して最大値を計算でき、最適なアライメントが構築されます。 2つのシーケンスには、スコアマトリックスに最適なスコアにつながる1つ以上の最適パスがあります。これは、2つのシーケンスに存在する可能性があり、最適なスコアを持ついくつかのアライメントです。

マトリックス参照によるアルゴリズムの指定：

{displaystyle m（0,0）= 0}

$M(0,0) = 0$

{displaystyle m（i、0）= m（i-1,0）+f（i）、; 1leq ileq m}}

$M(i,0) = M(i-1,0) + f(i),; 1le ile m$

{displaystyle m（0、j）= m（0、j-1）+f（j）、; 1leq jleq n}

$M(0,j) = M(0,j-1) + f(j),; 1le jle n$

{displaystyle M（i、j）= max {begin {bmatrix} m（i-1、j-1）+ w（a_ {i}、b_ {j}）＆{text {mate bzw. mismatch}} \ m（i-1、j）+ f（k）＆{text {deletion}}} \ m（i、j-1）+ f（l）＆{text {insertion}} end {bmatrix}}}

${displaystyle M(i,j)=max {begin{Bmatrix}M(i-1,j-1)+ w(a_{i},b_{j})&{text{Match bzw. Mismatch}}\M(i-1,j)+ f(k)&{text{Deletion}}\M(i,j-1)+ f(l)&{text{Insertion}}end{Bmatrix}},;1leq ileq m,1leq jleq n}$

${displaystyle a、b}$
${displaystyle M = operatorname {length}（a）}$
${displaystyle n = operatorname {length}（b）}$
${displaystyle m（i、j）}$
${displaystyle W（c、d）、; c、din sigma}$
${displaystyle f}$

小さな例を使用して、アルゴリズムの手順をここに示します。

次の関数は、評価関数として使用されます。

{displaystyle w（x、y）= {begin {cases} 1＆{text {for}} x = y \ -1＆{text {refing} \ end {cases}}}}

${displaystyle w(x,y)={begin{cases}1&{text{für }}x=y\-1&{text{sonst}}\end{cases}}}$

a = acgtcおよびb = agtc

より良い理解のために、線にはシーケンスAで作られた文字とシーケンスbからの文字が付いた列が付いていることを想像できます。数学的な観点からは、これはマトリックス内で意味をなさないため、これは視界のみです。

{displaystyle D={begin{pmatrix}&-&A&G&T&C\-&0&-1&-2&-3&-4\A&-1&0&0&0&0\C&-2&0&0&0&0\G&-3&0&0&0&0\T&-4&0&0&0&0\C&-5&0&0&0&0\end{pmatrix}}}

$D = begin{pmatrix} &-&A&G&T&C\ -&0&-1&-2&-3&-4 \ A&-1&0&0&0&0 \ C&-2&0&0&0&0 \ G&-3&0&0&0&0 \ T&-4&0&0&0&0 \ C&-5&0&0&0&0 \ end{pmatrix}$

0.ステップ：初期化

マトリックスのエントリ

{displaystyle d（i、j）}

$D(i,j )$ 最初の行と最初の列の場合、上記のように埋められます。エントリの評価

{displaystyle d（1,0）}

$D(1,0)$ 上記の評価から計算されます

{displaystyle d（i-1、j）= d（0,0）= 0}

$D(i-1,j )=D(0,0)=0$ ポイントでのスコア

{displaystyle w（a_ {i}、b_ {i}）= w（a_ {1}、 – ）= w（a、 – ）= -1}

$w(a_i,b_i) = w(a_1,-) = w(A,-) = -1$ 。また

{displaystyle d（1,0）= 0+（ – 1）= -1}

$D(1,0) = 0 + (-1) = -1$ 他の値は同様に計算されます。

{displayStyle d = {begin {pmatrix} 0＆-1＆-2＆-3＆-4 \ -1＆0＆0＆0＆0＆0 \ -3＆0＆0＆0＆0 \ -4＆0＆0＆0＆0＆0＆0＆0 \ -5＆0＆0＆0＆0 {pmatrix}}}}

$D = begin{pmatrix} 0&-1&-2&-3&-4 \ -1&0&0&0&0 \ -2&0&0&0&0 \ -3&0&0&0&0 \ -4&0&0&0&0 \ -5&0&0&0&0 \ end{pmatrix}$

最初のステップ：
の計算

{displaystyle d（1,1）}

$D(1,1)$ ：

{displaystyle {begin {cases} d（0,0）+w（a、a）rightArrow 0+1 \ d（0,1）+w（a、 – ）rightArrow -1+（ – 1）\ d（1,0）+w（ – 、a）rightarrow -1+（ – 1）\ end {case}}}}}

$begin{cases} D(0,0) + w(A,A) Rightarrow 0 + 1 \ D(0,1) + w(A,-) Rightarrow -1 +(-1) \ D(1,0) + w(-,A) Rightarrow -1 +(-1) \ end{cases}$

→最大は最初のケースから生じます、i。 H. AはAと整列しています。

{displayStyle d = {begin {pmatrix} 0＆-1＆-2＆-3＆-4 \ -1＆1＆0＆0＆0＆0 \ -3＆0＆0＆0＆0 \ -4＆0＆0＆0＆0＆0＆0＆0 \ -5＆0＆0＆0＆0 {pmatrix}}}}}

$D= begin{pmatrix} 0&-1&-2&-3&-4 \ -1&1&0&0&0 \ -2&0&0&0&0 \ -3&0&0&0&0 \ -4&0&0&0&0 \ -5&0&0&0&0 \ end{pmatrix}$

→Jの増加1、私は同じままです

2番目のステップ：
の計算

{displaystyle d（1,2）}

$D(1,2)$ ：

{displaystyle {begin {cases} d（0,1）+w（a、c）rightArrow -1+（ – 1）\ d（0,2）+w（a、 – ）rightArrow -2+（ – 1）\ d（1,1）+w（ – 、c）rightArrow 1+（ – 1）

$begin{cases} D(0,1) + w(A,C) Rightarrow -1 +(-1) \ D(0,2) + w(A,-) Rightarrow -2 +(-1) \ D(1,1) + w(-,C) Rightarrow 1 +(-1) \ end{cases}$

→計算の最大値、つまり0がここに作成されるため、最大値は3番目のケースから生じます。 H.ギャップ（ – ）はCと整列します。

{displayStyle d = {begin {pmatrix} 0＆-1＆-2＆-3＆-4 \ -1＆1＆0＆0＆0＆0 \ -3＆0＆0＆0＆0 \ -4＆0＆0＆0＆0＆0＆0＆0 \ -5＆0＆0＆0＆0 {pmatrix}}}}}

$D= begin{pmatrix} 0&-1&-2&-3&-4 \ -1&1&0&0&0 \ -2&0&0&0&0 \ -3&0&0&0&0 \ -4&0&0&0&0 \ -5&0&0&0&0 \ end{pmatrix}$

{displaystyle vdots}

$vdots$

塗りつぶされたマトリックスは、上記の手順を完全に実行した後に次のように見えます。

{displaystyle D={begin{pmatrix}0&-1&-2&-3&-4\-1&1&0&-1&-2\-2&0&0&-1&0\-3&-1&1&0&-1\-4&-2&0&2&1\-5&-3&-1&1&3\end{pmatrix}}}

$D= begin{pmatrix} 0&-1&-2&-3&-4 \ -1&1&0&-1&-2 \ -2&0&0&-1&0 \ -3&-1&1&0&-1 \ -4&-2&0&2&1 \ -5&-3&-1&1&3 \ end{pmatrix}$

このアライメントの評価は3です。

関連するアライメントは次のようになります：

{displaystyle {begin {matrix} {text {sequenz}} a：＆a＆c＆g＆t＆c \ {text {sequenz}} b：＆a＆ – ＆ – ＆t＆cend {matrix}}}}

$begin{matrix} text{Sequenz} a: &A&C&G&T&C \ text{Sequenz} b: &A&-&G&T&Cend{matrix}$

トレースバックによって計算されます。

評価関数の選択は、Needleman Wishアルゴリズムから得られる結果に大きな影響を与えます。
上記で選択したように、単純な評価機能は、アラインメントの生物学的背景を反映していないため、実用的な目的にはかなり不適切です。
現時点で最も一般的な評価関数は、SO -Called Scoring Matrixからの評価を読み取ります。タンパク質の場合、PAMまたは青斑マトリックスを使用できます。サイズ20×20（またはいくつかの特別なケースがまだ観察されている場合は24×24）のこれらのマトリックスには、別のマトリックに代わったアミノ酸のレビュー（いわゆるlog-odds）が含まれています。 log-oddは確率に基づいています。
これらのスコアリングマトリックスは、シーケンスアライメントからも計算されます。

上記で使用した評価関数は、2つのシーケンスの類似性を決定するために使用されます。距離を決定できるようにするために、評価機能を単純に変更できます。 H.不平等が発生した場合、プラスの値を返すことができます。これは、罰と平等0または負の値で解釈できます。ただし、距離ベースの評価関数での再帰は決定する必要はなく、最小値であることに注意する必要があります。

距離ベースの評価関数の例：

{displaystyle w（x、y）= {begin {cases} 0＆{text {for}} x = y \ 1＆{text {for}} xnot = y \ end {cases}}}}

${displaystyle w(x,y)={begin{cases}0&{text{für }}x=y\1&{text{für }}xnot =y\end{cases}}}$

Needleman Request Algorithmの用語があります

{displaystyle o}

$O$

{displaystyle（mcdot n）}

${displaystyle (mcdot n)}$ 。しなければならない

{displaystyle mcdot n}

$mcdot n$ マトリックスの要素は計算され、これらのそれぞれに対して3つ以上で最大化されます ^[初め]。これは、マトリックス参照から簡単に導出できます。メモリの要件は、テーブル全体の構築にあります

{displaystyle o}

$O$

{displaystyle（nm）}

$(nm)$ 。

1970年のNeedleman Wish Paperでは、マトリックス参照はありません。アルゴリズムは非公式で説明されています。ここに示されているマトリックス参照は、この説明から生じます。

1976年のウォーターマン、スミスとベイヤーによる論文で ^[2]Needleman Wish Algorithmは、Matrix Referenceで明示的に指定されています。そのため、一部の著者は、必要なウィッシュアルゴリズムをウォーターマンスミスベイヤーアルゴリズムと呼んでいます。 ^[3]

いくつかの文献では、基準があります

{displaystyle o（n^{2}）}

$O(n^2)$ 均一なギャップの下でのグローバルアライメントを計算するためのDPアルゴリズムコストは誤ってニードルウィッシュアルゴリズムと呼ばれます。 ^[4]ただし、編集操作に均一なギャップコストを使用する場合は3つの隣接セルのみを観察する必要があるため、これはNeedleman Requestアルゴリズムの専門化です。

立方体の期間のため、Needleman Wishアルゴリズムは実際には使用されていません。均一なコストに限定されている場合、最適なアライメント

{displaystyle o（n^{2}）}

$O(n^2)$ 計算されます。 GOTOHアルゴリズムを使用すると、最適なアライメントは、アフィンギャップコストで平方用語で計算できます。
Hirschbergアルゴリズムは、線形ストレージスペースの均一またはアフィンギャップコストのグローバルアライメントを計算します

{displaystyle o（m+n）}

$O(m+n)$ やがて

{displaystyletheta（mn）}

$Theta(m n)$ と
Smith Watermanアルゴリズムは、2つのシーケンスの最適な局所アライメントを計算します。

正方形のメモリ要件のため、より長いシーケンスを調整するためのアルゴリズムはかなり不適切です。 zの場合。 B.サイズが4バイトのマトリックス整数値では、10,000文字のシーケンスのアライメントスコアの計算には、

{DisplayStyle 10.000Times 10.000}

$10.000times 10.000$ エントリ。マトリックスもそうです

{displaystyle 100.000.000Times 4、{text {byte}} arth 381、{text {megabyte}}}}

$100.000.000times 4, text{Byte} approx 381, text{Megabyte}$ 証明されています。ゲノム全体のアライメントを効率的に実行することはできません。たとえば、中程度の細菌ゲノムには約1〜400万ペアの塩基があり、ヒトゲノムは約30億塩基対です。

それとは別に、ゲノム全体のグローバルなアライメントは、必ずしも高い生物学的ゲインを持っているわけではありません。

均一なギャップコスト [ 編集 | ソーステキストを編集します ]

均一なギャップコストを使用する場合、Needleman Wishアルゴリズムへのマトリックス参照が可能です。

{displaystyle o（n^{3}）}

$O(n^{3})$ の上

{displaystyle o（n^{2}）}

$O(n^2)$ 削減。売り手は、1974年の論文でこれらの再帰を明示的に指定しました。 ^[5]

均一なギャップコスト関数

{displaystyle f}

$f$ で定義されています

{displaystyle f（l）= lcdot c}

$f(l) = lcdot c$ 、d。 H.ギャップのすべての場所は同じです。接頭辞の最適なアライメントを見るとき、均一なギャップコストを使用する

{displaystyle a [0..i]}

$a[0..i]$ と

{displaystyle b [0..j]}

$b[0..j]$ 、長さの挿入ギャップにあります

{displaystyle k_ {1}}

$k_{1}$ と

{displaystyle k_ {1}> 1}

$k_1 > 1″></span>終了、プレフィックスの最適なアライメントがすぐに表示される <span class=$

{displaystyle a [0..i-1]}

$a[0..i-1]$ と

{displaystyle b [0..j]}

$b[0..j]$ 挿入ギャップで終わります。したがって、最適な挿入ギャップ（任意の長さ）のコストを計算するだけで十分です

{displaystyle m（i、j）}

$M(i,j)$ 、

{displaystyle m（i-1、j）+c}

$M(i-1, j)+c$ 期待する。削除ギャップコストの計算は同様です。

これにより、次の専門的な再帰が発生します。

{displaystyle m（0,0）= 0}

$M(0,0) = 0$

{displaystyle m（i、0）= m（i-1,0）+c、; 1leq ileq m}

$M(i,0) = M(i-1,0) + c,; 1le ile m$

{displaystyle m（0、j）= m（0、j-1）+c、; 1leq jleq n}

$M(0,j) = M(0,j-1) + c,; 1le jle n$

{displaystyle M（i、j）= max {begin {bmatrix} m（i-1、j-1）+ w（a_ {i}、b_ {j}）＆{text {mate bzw. mismatch}} \ m（i-1、j）+c＆{text {deletion}}} \ m（i、j-1）+c＆{text {insertion}} end {bmatrix}}}

$M(i,j) = max begin{Bmatrix} M(i-1,j-1) + w(a_i,b_j) & text{Match bzw. Mismatch} \ M(i-1,j) + c & text{Deletion} \ M(i,j-1) + c & text{Insertion} end{Bmatrix} ,; 1le ile m, 1le jle n$

フリーシフトアライメント [ 編集 | ソーステキストを編集します ]

最適なフリーシフトアラインメント（またはエンドギャップフリーアライメント）の計算は、スコア計算のアライメントの開始または終了時に挿入または削除のシーケンスが考慮されない、Needleman Wish Algorithmのバリアントです。この目的のために、グローバルアライメントを計算するためのアルゴリズムが変更され、最初の行または最初の列が

{displaystyle 0}

${displaystyle 0}$ 初期化されます。トラッキングを焼くと、最後の列または線の最大値が検索され、出発点として使用されます。

↑ R.ワグナー、M。フィッシャー：文字列間補正の問題。の： J. ACM 。 21年、1974年、 S. 172 、doi： 10.1145/321796.321811 。
↑ ウォーターマン、スミス、ベイヤー：いくつかの生物学的配列メトリック。の：数学の進歩。バンド 20 、1976年、 S. 367–387 、doi： 10.1016/0001-8708（76）90202-4 （定理3）。
↑ P.クロート、R。オーブン：計算分子生物学。 Wiley、2000、ISBN 0-471-87251-2。
↑ D.ガスフィールド：文字列、木、シーケンスのアルゴリズム。 1997、ISBN 0-521-58519-8、11.7.3、 S. 234 。
↑ ピーターH.セラーズ：進化距離の理論と計算について。の： Applied MathematicsのSiam Journal 。バンド 26 、いいえ。 4 、1974年6月、 S. 787–793 、jstor： 2099985 。

after-content-x4

Needleman Wish Algorithm-Wikipedia

均一なギャップコスト [ 編集 | ソーステキストを編集します ]

フリーシフトアライメント [ 編集 | ソーステキストを編集します ]

Recent Posts

Recent Comments

Archives

Categories

Meta