4

できればPythonで、N文字の長さのターゲット文字列に最も近い既存の文字列のN文字の長さの部分文字列を見つけるのに役立つアルゴリズムを探しています。

ターゲット文字列、つまり 4 文字の長さを次のように考えます。

targetString -> '1111'

これが私が利用できる文字列であると仮定します（「最適な配置」マッチングのために、この部分文字列を生成します）：

nonEmptySubStrings -> ['110101']

上記の 4 文字の部分文字列:

nGramsSubStrings -> ['0101', '1010', '1101']

targetString に最も近い文字列を選択する「マジック関数」を作成/使用したい:

someMagicFunction -> ['1101']

いくつかの例:

nonEmptySubStrings -> ['101011']
nGramsSubStrings -> ['0101', '1010', '1011']

someMagicFunction -> ['1011']

nonEmptySubStrings -> ['10101']
nGramsSubStrings -> ['0101', '1010']

someMagicFunction -> ['0101', '1010']

この「マジック関数」はよく知られている部分文字列の問題ですか?

私は本当に分を見つけたいです。部分文字列として targetString を持つようにするための nonEmptySubStrings の変更の数。

4

3 に答える 3

3

Edit Distanceが必要だと思います。Peter Norvig のスペル修正プログラムは、Python での実装例です。これはレーベンシュタイン距離の実装です。この質問も参照してください。

編集: これは、バイオインフォマティクスではかなり頻繁に行われます。例えば、 FASTAおよびBLASTを参照してください。バイオインフォマティクスには、このアルゴリズムのさまざまな特徴があります。メソッドの概要については、配列アラインメントを参照してください。

于 2010-11-17T09:55:00.553 に答える
2

少し前の遺伝子マッチングに関する議論の一環として、私はこの pyparsing exampleを書き、pyparsing クラスを実装しましたCloseMatch。通常、pyparse 式は、一致した文字列と名前付きの結果を含む構造をCloseMatch返しますが、一致した文字列と一致した文字列内の不一致の場所のリストを含む 2 タプルを返します。CloseMatch使用方法は次のとおりです。

searchseq = CloseMatch("TTAAATCTAGAAGAT", 3)
for g in genedata: 
    print "%s (%d)" % (g.id, g.genelen) 
    print "-"*24 
    for t,startLoc,endLoc in searchseq.scanString(g.gene): 
        matched, mismatches = t[0] 
        print "MATCH:", searchseq.sequence 
        print "FOUND:", matched 
        if mismatches: 
            print "      ", ''.join(' ' if i not in mismatches else '*'  
                            for i,c in enumerate(searchseq.sequence)) 
        else: 
            print "<exact match>" 
        print "at location", startLoc

部分一致の出力例を次に示します。

organism=Toxoplasma_gondii_RH (258)
------------------------
MATCH: TTAAATCTAGAAGAT
FOUND: TTAAATTTAGGAGCT
             *   *  * 
at location 195

このクラスは重複一致を検出しないことに注意してください。それはまだ達成できますが、scanString (次の pyparsing リリースに含める予定) を使用した少し異なるアプローチを使用します。

于 2010-11-17T13:47:58.247 に答える
1

質問へのOPのコメントに基づいて、これが望ましいものです

import functools

def edit_distance(str1, str2): 
    #implement it here

f = functools.operator(edit_distance, target_string)
return min(f(s) for s in slices(string_))   # use slices from below

これにより、部分文字列からターゲット文字列までの最小編集距離が返されます。それがどの文字列であるか、またはそのインデックスが何であるかは示しません。ただし、そうするように簡単に変更できます。

最良の方法である可能性のある素朴な方法は、

import functools

def diff(str1, str2):
    # However you test the distance gets defined here. e.g. Hamming distance, 
    # Levenshtein distance, etc.


def slices(string_, L):
    for i in xrange(len(string_) - L + 1)):
        yield string_[i:i+L]

best_match = min(slices(string_), key=functools.partial(diff, target_string))

ただし、これは部分文字列が発生するインデックスを返しません。もちろん、質問でそれが必要であることを指定していませんでした;）

これよりも良くしたい場合は、距離をどのように測定しているかに依存し、基本的には、すでにより良い一致を得るには少なくとも x 文字を変更する必要があると推測することで、一部の部分文字列のチェックを回避することになります。持ってる。その時点で、x 文字先にジャンプして x 文字を変更することもできます。

于 2010-11-17T09:57:14.943 に答える