OK、Needleman-Wunsch(NW) は、バイオインフォマティクスの文献からの古典的なエンドツーエンド (「グローバル」) アライナーです。かなり前に、FASTA パッケージで「align」および「align0」として利用可能でした。違いは、「0」バージョンは、エンド ギャップを回避することについてそれほどバイアスがかかっていなかったことです。これにより、多くの場合、高品質の内部一致をより簡単に優先することができました。ご存知かと思いますが、Smith-Waterman は地元のアライナーであり、BLAST の最初の基礎となっています。FASTA には独自のローカル アライナーもありましたが、これは少し異なりました。これらはすべて、基本的に、個々の文字ペアのスコアリング メトリックに関連するレーベンシュタイン距離を推定するヒューリスティックな方法です (バイオインフォマティクスでは、Dayhoff/"PAM"、Henikoff&Henikoff、
ラベルについては気にしないでください: レーベンシュタイン距離は、少なくとも実際に参照されているように、基本的には編集距離であり、一般的に計算するのは現実的ではなく、興味深い特殊なケースでさえ正確に計算するには費用がかかるため、推定する必要があります: 水そこではすぐに深くなるので、長くて評判の良いヒューリスティックな方法があります。
さて、あなた自身の問題についてですが、数年前、私は短い DNA 読み取りの正確性を、正しいことがわかっている参照配列に対してチェックしなければならず、「固定アラインメント」と呼ばれるものを思いつきました。
アイデアは、指定された N 文字の部分文字列が発生するすべての場所を見つけることによって、参照文字列セットを取得し、それを「ダイジェスト」することです。作成するテーブルが大きすぎず、長さ N の部分文字列が一般的になりすぎないように、N を選択します。DNA 塩基のような小さなアルファベットの場合、N 文字の文字列に対して完全なハッシュを作成し、テーブルを作成して、各ビンからのリンクされたリストで一致を連鎖させることができます。リスト エントリは、それらが出現するリスト内のビンにマップされる部分文字列のシーケンスと開始位置を識別する必要があります。これらは、NW アラインメントが役立つ可能性が高い、検索対象の文字列のリスト内の「アンカー」です。
クエリ文字列を処理するとき、クエリ文字列のオフセット K から始まる N 文字を取得し、それらをハッシュし、それらのビンを検索します。そのビンのリストが空でない場合は、すべてのリスト レコードを調べて間のアライメントを実行します。レコードで参照されているクエリ文字列と検索文字列。これらのアラインメントを行うときは、クエリ文字列と検索文字列をアンカーで並べ、クエリ文字列と同じ長さで、同じオフセット K でそのアンカーを含む検索文字列の部分文字列を抽出します。
十分に長いアンカー長 N とオフセット K の妥当な値のセット (クエリ文字列全体に分散するか、低いオフセットに制限することができます) を選択すると、可能なアラインメントのサブセットが得られ、多くの場合、より明確な勝者が得られます。通常、エンド バイアスの少ない align0 のような NW アライナーを使用することをお勧めします。
このメソッドは、入力を制限することで NW を少しブーストしようとします。アラインメントが少なくなり、同様のシーケンス間で行われることが多いため、パフォーマンスが向上します。NWアライナーで行うもう1つの良いことは、特に中程度の品質の試合を見たり興味を持ったりしないことがわかっている場合は、コストを削減するために、ある程度または長さのギャップが発生した後にあきらめることです.
最後に、この方法は、小さなアルファベットのシステムで使用され、K はクエリ文字列の最初の 100 程度の位置に制限され、検索文字列はクエリよりもはるかに大きくなります (DNA 読み取りは約 1000 塩基で、検索文字列はオンでした)。 10000のオーダーなので、具体的には編集距離の推定によって正当化されるおおよその部分文字列の一致を探していました)。この方法論を自然言語に適応させるには、慎重に検討する必要があります。アルファベットのサイズでは負けますが、クエリ文字列と検索文字列の長さが同じであればメリットがあります。
いずれにせよ、クエリ文字列の異なる端から複数のアンカーを同時に使用できるようにすることは、NW に供給されるデータをさらにフィルタリングするのに役立つ場合があります。これを行う場合は、それぞれが 2 つのアンカーの 1 つを含むオーバーラップする文字列をアライナーに送信し、アラインメントを調整する準備をしてください。または、NW をさらに変更して、アラインメント中にアンカーをほとんどそのまま維持することを強調するために、アルゴリズムの実行。
これが役立つか、少なくとも興味深いことを願っています。