0

我有一个相等长度的子字符串列表，我想在一个大字符串中找到一个位置。然而棘手的部分是我还应该找到不匹配数量有限的子字符串（也给出了不匹配的数量）。我以为我可以用正则表达式来做到这一点，但我找不到怎么做。UPD：我使用的是 Python 2.7。

示例：输入字符串：s = 'ATGTCGATCGATGCTAGCTATAGATAAAA'，输入子字符串是s0 = 'ATG'，允许的不匹配数是 n = 1。我想要的是返回一个可迭代的，比如说一个位置列表：[0,7,19,23,6]，它对应于 'ATG' 的位置（两次），'ATA ' (两次), 'ATC' 相应地，因为没有其他 3-mers 不匹配不会出现在字符串中。

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

您是否考虑过使用 Levenshtein 距离算法寻求帮助？它用于确定两个字符串彼此之间的相似程度。

这是一个幼稚的实现：

  1. 对于 i = 0 到 len(haystack_str) - len(needle_str)
  2. 让potential_match = haystack_str[i,i+len]
  3. 查看 potential_match 和 needle_str 之间的 Levenshtein 距离是多少
  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

以及Levenshtein 距离的 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 回答