Python 正则表达式模块即使重叠 = True 也找不到所有匹配项

我正在使用 PyPy正则表达式模块 https://pypi.org/project/regex/具有重叠匹配支持。

我有以下代码，其中有一个字符串 A，我正在使用正则表达式查找在正则表达式中定义的 DNA 模式。我想找到与我的 RE 的所有匹配项，包括重叠的匹配项。正则表达式缺少其中一场比赛，我不知道如何修复它。

import regex as re
A = "GGGGAGAAGGGGGGCCTTCCTGGGTCCCCGAGAGTGCAGACATGCCTGGGTCCACAGCCACGGTTTGGG"
GQ_list = re.findall(r"[G]{3,6}[ACTG]{1,33}[G]{3,6}[ACTG]{1,33}[G]{3,6}[ACTG]{1,33}[G]{3,6}", A, overlapped=True)

GQ_list 返回：

['GGGGAGAAGGGGGGCCTTCCTGGGTCCCCGAGAGTGCAGACATGCCTGGGTCCACAGCCACGGTTTGGG',
 'GGGAGAAGGGGGGCCTTCCTGGGTCCCCGAGAGTGCAGACATGCCTGGGTCCACAGCCACGGTTTGGG',
 'GGGGGGCCTTCCTGGGTCCCCGAGAGTGCAGACATGCCTGGGTCCACAGCCACGGTTTGGG',
 'GGGGGCCTTCCTGGGTCCCCGAGAGTGCAGACATGCCTGGGTCCACAGCCACGGTTTGGG',
 'GGGGCCTTCCTGGGTCCCCGAGAGTGCAGACATGCCTGGGTCCACAGCCACGGTTTGGG',
 'GGGCCTTCCTGGGTCCCCGAGAGTGCAGACATGCCTGGGTCCACAGCCACGGTTTGGG']

缺少这个"GGGGAGAAGGGGGGCCTTCCTGGGTCCCCGAGAGTGCAGACATGCCTGGG" 这是我的字符串中的A并匹配正则表达式模式。这里有什么问题吗？我应该做出哪些更改才能获得所有可能的匹配（包括重叠的匹配）？

tdlr：在同一起始字符串索引处可能存在多个正则表达式匹配，re.findall或其他正则表达式方法只会为每个起始索引找到 1 个匹配项。你必须分解搜索才能找到全部......

您遇到的问题是正则表达式 findall 确实not找到每个索引的所有组合；它只找到one依次从每个索引进行匹配——通常是最长的匹配。查找重叠匹配的技术仍然会错过单个字符串索引中可能的多个匹配。你需要修改你的方法。

如果您检查您的正则表达式：

([G]{3,6}[ACTG]{1,33}[G]{3,6}[ACTG]{1,33}[G]{3,6}[ACTG]{1,33}[G]{3,6})

您会注意到匹配的序列必须以至少 3 个开头G并以相同的顺序结束。之间的顺序GGG[in_between_part]GGG短至 9 个字符，长至 84 个字符（并且可能包含相同的开始/结束序列'GGG''s).

我们可以使用该信息来查找符合该描述的所有可能的字符串序列。然后我们使用您的正则表达式来过滤所识别的序列确实是我们想要的序列。

首先找到每个可能的字符串索引'GGG'这是子字符串开始或结束的位置（根据定义）：

s = "GGGGAGAAGGGGGGCCTTCCTGGGTCCCCGAGAGTGCAGACATGCCTGGGTCCACAGCCACGGTTTGGG"

offset=0
indicies=[]
while (s_idx:=s[offset:].find('GGG'))>-1:
    indicies.append(s_idx+offset)
    offset+=s_idx+1

>>> indicies
[0, 1, 8, 9, 10, 11, 21, 47, 66]
# these are the indicies of 'GGG' that might be that start or end
# of a sub string of interest.

现在我们有了每个的起始索引'GGG'在你的字符串中。我们现在可以使用正则表达式和 bisect 模块来过滤正则表达式字符串中所有可能的匹配项。

我们正在使用bisect https://docs.python.org/3/library/bisect.html找到候选结束锚点的结束位置，该位置与开始锚点相同。 bisect 模块允许我们构造一个切片，该切片形成子字符串，a) 开头'GGG'（来自indicies列表）和 b）以'GGG'c) 起始锚点和结束锚点之间的长度在 9 到 84 个字符之间。然后我们使用重新完全匹配 https://docs.python.org/3/library/re.html#re.fullmatch确保候选子字符串完全匹配您的模式：

import re 
import bisect 

matches=[]  
min_len=3+9
max_len=3+84
pat=re.compile(r'([G]{3,6}[ACTG]{1,33}[G]{3,6}[ACTG]{1,33}[G]{3,6}[ACTG]{1,33}[G]{3,6})')
for x in indicies:
    min_offest=bisect.bisect(indicies,x+min_len)
    max_offset=bisect.bisect(indicies,x+max_len)
    for idx in indicies[min_offest:]+indicies[max_offset:]:
        candidate=s[x:idx+3]
        if pat.fullmatch(candidate):
            matches.append(candidate)

现在我们可以打印找到的所有匹配项，其索引位于s和长度：

>>> for ss in matches: print((s.index(ss), len(ss)),ss)
# This is only a primitive shortcut. If you want the actual
# index, save it when 'candidate' matches the regex

打印所有八个唯一匹配项，包括来自相同起始索引的匹配项：

(0, 50) GGGGAGAAGGGGGGCCTTCCTGGGTCCCCGAGAGTGCAGACATGCCTGGG
(0, 69) GGGGAGAAGGGGGGCCTTCCTGGGTCCCCGAGAGTGCAGACATGCCTGGGTCCACAGCCACGGTTTGGG
(1, 49) GGGAGAAGGGGGGCCTTCCTGGGTCCCCGAGAGTGCAGACATGCCTGGG
(1, 68) GGGAGAAGGGGGGCCTTCCTGGGTCCCCGAGAGTGCAGACATGCCTGGGTCCACAGCCACGGTTTGGG
(8, 61) GGGGGGCCTTCCTGGGTCCCCGAGAGTGCAGACATGCCTGGGTCCACAGCCACGGTTTGGG
(9, 60) GGGGGCCTTCCTGGGTCCCCGAGAGTGCAGACATGCCTGGGTCCACAGCCACGGTTTGGG
(10, 59) GGGGCCTTCCTGGGTCCCCGAGAGTGCAGACATGCCTGGGTCCACAGCCACGGTTTGGG
(11, 58) GGGCCTTCCTGGGTCCCCGAGAGTGCAGACATGCCTGGGTCCACAGCCACGGTTTGGG

Note:

正如评论中所述，正则表达式模块 https://pypi.org/project/regex/ does支持可变宽度lookbehind。

因此，您可能会想做：

m1=regex.findall(r'([G]{3,6}[ACTG]{1,33}[G]{3,6}[ACTG]{1,33}[G]{3,6}[ACTG]{1,33}[G]{3,6})', s, overlapped=True)     
# produces 6 unique matches 
m2=regex.findall(r'(?<=([G]{3,6}[ACTG]{1,33}[G]{3,6}[ACTG]{1,33}[G]{3,6}[ACTG]{1,33}[G]{3,6}))', s, overlapped=True)
# produces 2 matches, but one is a duplicate from m1

虽然此组合找到了 1 个额外的字符串，即您要查找的字符串，但它没有找到所有 8 个唯一匹配项。字符串GGGAGAAGGGGGGCCTTCCTGGGTCCCCGAGAGTGCAGACATGCCTGGG索引 1 处被遗漏。