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

Question

我正在使用 PyPy regex module具有重叠匹配支持。

我有以下代码，其中有一个字符串 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 中并且与正则表达式模式匹配。这里有什么问题吗？我应该进行哪些更改才能获得所有可能的匹配(包括重叠的匹配)？

Answer 1

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

---

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

如果你检查你的正则表达式:

([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' 起始/结束序列的)。

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

首先找到每个可能的'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找到候选结束 anchor 的结束位置，该位置与开始 anchor 相同。 bisect 模块允许我们构建一个形成子字符串的切片，a) 以 'GGG' 开头(来自 indicies 列表)，b) 以 ' 结尾GGG' 和 c) 的起始 anchor 和结束 anchor 之间的长度为 9 到 84 个字符。然后我们使用 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

---

注意:

正如评论中所述，regex module 确实支持可变宽度lookbehinds。

因此，您可能会想做:

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 个唯一匹配项。索引 1 处的字符串 GGGAGAAGGGGGGCCTTCCTGGGTCCCCGAGAGTGCAGACATGCCTGGG 丢失。