3

Needleman-Wunsch アルゴリズム (通常、ヌクレオチド/タンパク質配列の整列に使用されます) の結果をどのように定量化できるのでしょうか。

一定のスコアリング スキームと、長さが異なる と の 2 つのシーケンスを考えてみましょS1うS2。と のすべての可能なアラインメントを力ずくで計算S1しS2、最高スコアのアラインメントにはスコアがあるとしxます。もちろん、これは Needleman-Wunsch アプローチよりもかなり複雑です。

Needleman-Wunsch アルゴリズムを使用して配列アラインメントを見つける場合、スコアがあると言いますy。

は、2 つのランダム シーケンスおよびrに対して Needleman-Wunsch によって生成されたスコアであると考えてください。R1R2

xと比べてどうyですか？相同性が既知の 2 つの配列yよりも常に大きいですか?r

一般的に、Needleman-Wunsch アルゴリズムを使用して配列アラインメントを大幅に高速化することは理解していますが (力ずくのアプローチと比較して)、それに伴う精度のコスト (もしあれば) については理解していません。元の論文 (Needleman & Wunsch, 1970) を読んでみましたが、まだこの疑問が残っています。

4

2 に答える 2

5

Needlman-Wunsch は、常に最適な答えを生成します。これは、総当たりよりもはるかに高速であり、プロセスの精度を犠牲にしません。それが使用する重要な洞察は、考えられるすべてのアラインメントを実際に生成する必要はないということです。それらのほとんどには不適切なサブアラインメントが含まれており、おそらく最適ではないからです。代わりに、Needleman-Wunsch アルゴリズムは、元の鎖のフラグメントの最適なアラインメントをゆっくりと構築し、最適なアラインメントにはわずかに小さいケースの最適なアラインメントが含まれている必要があるという保証を使用して、これらの小さなアラインメントを大きなアラインメントにゆっくりと成長させることによって機能します。

于 2016-11-15T16:57:59.037 に答える
2

あなたの質問は、動的計画法が最適な解決策を見つけるかどうか、つまりy >= x. これについての議論のために、私はおそらく私より頭が良い人たちに言及します:

https://cs.stackexchange.com/questions/23599/how-is-dynamic-programming-different-from-brute-force

基本的に、動的計画法は最適な結果を生成する可能性が高い、つまりブルートフォースと同じですが、ベルマンの最適性の原則を満たす特定の問題に対してのみ、と述べています。

Needleman-Wunsch のウィキペディアのページによると、この問題はBellman の最適性の原則を満たしています。

https://en.wikipedia.org/wiki/Needleman%E2%80%93Wunsch_algorithm

具体的には：

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

同じウィキペディアのページの他の場所にも最適性についての言及があります。

于 2016-11-15T17:09:41.430 に答える