問題タブ [needleman-wunsch]
For questions regarding programming in ECMAScript (JavaScript/JS) and its various dialects/implementations (excluding ActionScript). Note JavaScript is NOT the same as Java! Please include all relevant tags on your question; e.g., [node.js], [jquery], [json], [reactjs], [angular], [ember.js], [vue.js], [typescript], [svelte], etc.
string - Needleman Wunsch アルゴリズムはブルート フォースと比べてどうですか?
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) を読んでみましたが、まだこの疑問が残っています。