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

Question

我正在使用具有重叠匹配支持的PyPyregex module

我有下面的代码，其中有一个字符串a，我正在寻找使用正则表达式在正则表达式中定义的DNA模式。我想用我的RE查找所有匹配项，包括重叠项。regex错过了一场比赛，我不知道如何修复它

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_列表返回：

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

这缺少我的字符串A中的"GGGGAGAAGGGGGGCCTTCCTGGGTCCCCGAGAGTGCAGACATGCCTGGG" ，它与正则表达式模式匹配。这里怎么了？我应该做哪些更改以获得所有可能的匹配，包括重叠的匹配

Answer 1

编辑：改进答案

这个问题的原因在于“正则表达式正向查找后面”的执行方式

在正常情况下，从位置1匹配字符串后：

patern = r"[G]{3,6}[ACTG]{1,33}[G]{3,6}[ACTG]{1,33}[G]{3,6}[ACTG]{1,33}[G]{3,6}"

GGGGAGAAGGGGGGCCTTCCTGGGTCCCCGAGAGTGCAGACATGCCTGGGTCCACAGCCACGGTTTGGG
^

regex提前一个职位：

GGGGAGAAGGGGGGCCTTCCTGGGTCCCCGAGAGTGCAGACATGCCTGGGTCCACAGCCACGGTTTGGG
 ^

然后从那里开始匹配。
那么，这将不匹配 GGGGAGGGGGGGCCTTCCTGGGTCCCGAGGAGTGCAGCAGAGAGACATGCTGGG（因为它与第一场比赛在同一位置开始）

而且它不会匹配 GGGAGAGGGGGGCCTTCCTGGGTCCCGAGAGTGCAGCAGACACACACATGCCTGGG 因为它与第二场比赛在同一位置开始）

使用正面向后看，也可以从同一起始位置（重新）匹配。
正则表达式：

(?<=([paterntomatch]))

//  ?<=  indicates positive look behind

警告：下面的示例可能会产生双重结果（两次查找一个事件）

因此，我在python中尝试使用递归函数来重新匹配match.substring（0，match.Length-1）

import re

def regexRecursive(patern,subject):
    master_results = []
    results = re.findall(patern, subject)
    for result in results:
        master_results.append(result)
        length = (len(result)-1)
        subresults = regexRecursive(patern,result[0:length])
        for subresult in subresults:
            master_results.append(subresult)
    return master_results

patern = r"(?=([G]{3,6}[ACTG]{1,33}[G]{3,6}[ACTG]{1,33}[G]{3,6}[ACTG]{1,33}[G]{3,6}))"

given = "GGGGAGAAGGGGGGCCTTCCTGGGTCCCCGAGAGTGCAGACATGCCTGGGTCCACAGCCACGGTTTGGG"

expected_yield = ['GGGGAGAAGGGGGGCCTTCCTGGGTCCCCGAGAGTGCAGACATGCCTGGGTCCACAGCCACGGTTTGGG',
 'GGGAGAAGGGGGGCCTTCCTGGGTCCCCGAGAGTGCAGACATGCCTGGGTCCACAGCCACGGTTTGGG',
 'GGGGGGCCTTCCTGGGTCCCCGAGAGTGCAGACATGCCTGGGTCCACAGCCACGGTTTGGG',
 'GGGGGCCTTCCTGGGTCCCCGAGAGTGCAGACATGCCTGGGTCCACAGCCACGGTTTGGG',
 'GGGGCCTTCCTGGGTCCCCGAGAGTGCAGACATGCCTGGGTCCACAGCCACGGTTTGGG',
 'GGGCCTTCCTGGGTCCCCGAGAGTGCAGACATGCCTGGGTCCACAGCCACGGTTTGGG',
 'GGGGAGAAGGGGGGCCTTCCTGGGTCCCCGAGAGTGCAGACATGCCTGGG',
 'GGGAGAAGGGGGGCCTTCCTGGGTCCCCGAGAGTGCAGACATGCCTGGG']

results = regexRecursive(patern, given)

for result in results:
    if result not in expected_yield:
        print ("\033[91m","Found Unexpected: ",result,"\033[0m")

for expected in expected_yield:
    if expected not in results:
        print ("\033[91m","Missing Expected: ",expected,"\033[0m")
    else:
        print ("\033[92m","Found Expected: ",expected,"\033[0m")

它产生了8个子串的完整补码

Answer 2

tdlr：由于在同一起始字符串索引中可能存在多个正则表达式匹配项，re.findall或其他正则表达式方法在每个起始索引中只能找到一个匹配项。你必须中断搜索才能找到所有的

---

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

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

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

您将注意到，匹配的序列必须以至少3G开始，并以相同的序列结束。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查找候选结束锚的结束位置，该位置与开始锚相同。对分模块允许我们构造一个切片，该切片形成以下子字符串：a）以'GGG'（来自indicies列表）开头，b）以'GGG'结尾，c）在起始和结束锚定之间的长度在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确实支持可变宽度的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

虽然这个组合找到了一个额外的字符串，即您正在寻找的字符串，但它没有找到所有8个唯一的匹配项。缺少索引1处的字符串GGGAGAAGGGGGGCCTTCCTGGGTCCCCGAGAGTGCAGACATGCCTGGG