0

同じ長さの部分文字列のリストがあり、そのすべてについて大きな文字列内の位置を見つけたいと考えています。ただし、トリッキーな部分は、不一致の数が限られている部分文字列も見つける必要があることです (不一致の数も指定されています)。正規表現でこれができると思ったのですが、方法がわかりません。UPD: Python 2.7 を使用しています。

例: 入力文字列: s = 'ATGTCGATCGATGCTAGCTATAGATAAAA'、入力部分文字列はs0 = 'ATG'、許容される不一致の数は n = 1 です。私が望むのは、[0,7,19,23,6]「ATG」(2 回)、「ATA」の位置に対応する位置の反復可能なリスト、たとえばリストを返すことです。 ' (2 回)、'ATC' は、一致しない他の 3-mer が文字列に発生しないためです。

4

3 に答える 3

5

新しいregexモジュールはあいまい一致をサポートしています。例えば

(?:foo){s<=2}

"foo" に一致し、2 つの置換を許可します。

ドキュメントからのこの発言にも注意してください。

デフォルトでは、あいまい一致は、指定された制約を満たす最初の一致を検索します。ENHANCEMATCH フラグを指定すると、見つかった一致の適合性を改善 (つまり、エラーの数を減らす) しようとします。

BESTMATCH フラグを指定すると、代わりに最適な一致が検索されます。

例：

>>> regex.findall(r'(?:foo){s<=2}', 'xxfoo')
['xfo']
>>> regex.findall(r'(?:foo){s<=2}', 'xxfoo', regex.BESTMATCH)
['foo']
于 2013-03-20T14:50:50.290 に答える
0

レーベンシュタイン距離アルゴリズムの使用を検討したことがありますか? 2 つの文字列が互いにどの程度似ているかを判断するために使用されます。

単純な実装を次に示します。

  1. i = 0 の場合、len(haystack_str) - len(needle_str)
  2. potential_match = haystack_str[i,i+len] とする
  3. potential_match と needle_str の間のレーベンシュタイン距離を確認してください
  4. 距離が 0 の場合、完全に一致しています
  5. 距離がしきい値未満の場合、不完全ではあるが十分に近い一致があります
  6. それ以外の場合は、次の i に進みます
于 2013-03-20T13:27:35.587 に答える
0

あなたの質問について私が理解したことを考えると：

タイプ1

def diff_count(s1, s2):
    count = 0
    for i in range(len(s1)):
        if s1[i] != s2[i]:
            count += 1
    return count

def diff_filter1(s1, s2, max_count):
    return diff_count(s1, s2) < max_count

タイプ 2 (より効率的)

def diff_filter2(s1, s2, max_count):
    count = 0
    i = 0
    while i < len(s1) and count < max_count:
        if s1[i] != s2[i]:
            count += 1
        i += 1
    return count < max_count

レーベンシュタイン距離の Python コード

def LevenshteinDistance(s, t):
    len_s = len(s)- 1
    len_t = len(t)- 1
    if(len_s == 0): return len_t
    if(len_t == 0): return len_s
    if(s[len_s-1] == t[len_t-1]): cost = 0
    else:                         cost = 1
    return min(LevenshteinDistance(s[0:len_s-1], t) + 1,
               LevenshteinDistance(s, t[0:len_t-1]) + 1,
               LevenshteinDistance(s[0:len_s-1], t[0:len_t-1]) + cost)
于 2013-03-20T13:43:36.210 に答える