translation - Unicode 文字列の高速シーケンス アラインメント

Question

BLAST アルゴリズムのようなものを実行して、Unicode 文字列の大規模なデータベースを照会したいと考えています。BLAST のようなアラインメント ソフトウェアのほとんどは、入力としてヌクレオチドまたはタンパク質の文字列を想定しています。しかし、私の入力には任意の Unicode 文字が含まれている可能性があります。これを可能にするソフトウェアを知っている人はいますか? スコアリング マトリックスは、単なる単位マトリックスである可能性があります (部分的な一致はありません)。

Needleman-Wunsch と Smith Waterman を試しましたが、私の目的には遅すぎます。BLAST のように、大規模なデータベースにクエリを実行する必要があります。

ありがとうございました！

Answer 1

BLASTを使用して、任意のアルファベットの文字シーケンスを整列させることができます。公開されている実装のほとんどはタンパク質に合わせて調整されているため、おそらく自分で実装する必要がありますが、アルゴリズムはタンパク質やヌクレオチド配列に固有のものではありません。

Answer 2

STELLAR を試してみることもできます。これは、検証ステップを備えたクエーサーのようなフィルター アルゴリズムです。（この論文を参照）

編集距離が 5% 未満の場合は、非常に高速です。

Answer 3

vmatch は一般的なサフィックス ツリー ベースのアラインメント プログラムです。