5

difflib を使用して、長いシーケンス内の短い文字列のすべての一致を識別しています。ただし、複数の一致がある場合、difflib は 1 つだけを返すようです。

> sm = difflib.SequenceMatcher(None, a='ACT', b='ACTGACT')
> sm.get_matching_blocks()
[Match(a=0, b=0, size=3), Match(a=3, b=7, size=0)]

私が期待した出力は次のとおりです。

[Match(a=0, b=0, size=3), Match(a=0, b=4, size=3), Match(a=3, b=7, size=0)]

実際、文字列 ACTGACT には、位置 0 と 4 に 2 つの一致する ACT が含まれており、両方ともサイズ 3 です (さらに、文字列の末尾にサイズ 0 の別の一致があります)。

複数のマッチを取得するにはどうすればよいですか? difflib が両方の位置を返すことを期待していました。

4

2 に答える 2

2

なぜあなたはそれを使うdifflibのですか？標準の正規表現を使用できるはずです。

import re
pattern = "ACT"
text = "ACTGACT"
matches = [m.span() for m in re.finditer(pattern, text)]

それはあなたに与えるでしょう：

[(0, 3), (4, 7)]

それとも、何らかの理由で、関心のある情報が含まれていませんか? もちろん、difflib が返す最後の空の一致は返されませんが、簡単に作成できます。

于 2015-02-27T13:02:04.560 に答える
2

Jerry が指摘し、k-nut が正しく答えたように、問題に対して間違ったアルゴリズムを使用しています。正直なところ、k-nut の答えはそれほど悪くはありませんが、このクラスの問題を解決する最も効率的な方法とは言えません。私は生物情報学者であり、あなたの質問とその例を考えると、あなたは「私たちの」古典的な DNA 配列アラインメント/検索の問題を解決しようとしているように見えます ( Altschul や "Gene" Myers などの科学界のスーパースターによる科学文献を参照してください)。核心的な詳細に興味があり、これまでで最も引用された論文の 1 つを読みたい場合は、この問題について）。

長いセグメントのデータベースで短いセグメントを効率的に見つけることは、Altschul の現在有名なBLASTアルゴリズムがヒューリスティックに解決するものであり、正確なルックアップのためにSmith-Watermanを使用して実行できます。Python でこれを行う最も効率的な方法は、おそらくBioPythonを使用することです。特に、ローカル NCBI BLAST+ インスタンスをセットアップする方法を説明しているセクションを参照することをお勧めします。Python と "結婚" していない場合、今日ではFSA-BLASTのようなさらに高速な BLAST の実装があります。

一方、正確な一致が必要な場合 (BLAST によって作成されたヒューリスティックとは対照的に)、長いクエリ時間を気にせず、参照シーケンスが小さい場合 (B例では)、行くことができます。公式の Smith-Waterman (SW) アライメントを使用。そうでなく、完全一致が必要な場合は、最初に BLAST で一致をフィルター処理し、次に候補の SW アラインメントでセットを減らします。

SW を純粋な Python で実装することもできます。既存の純粋な Python 実装をそのまま使用することもできますが、純粋に教育目的でのみそのパスをお勧めします (たとえば、GitHub のswalignを参照してください)。それにもかかわらず、かなり強力な Python ベースの実装が必要な場合は、scikit-bio はまだアルファ版の状態ですが、SW アラインメントについてはscikit-bioをチェックしてください。ただし、最初に上記で既にリンクされているSW WikiPedia ページを読んでください。使用しているハードウェアによっては、 CUDAまたはC++で GPU または少なくとも SIMD 最適化された実装を代わりに使用する場合があります。Python ラッパーを使用した適切なバージョンが必要な場合は、SSWlibを確認してください。

于 2015-03-06T10:08:39.283 に答える