Python正则表达式：如何重复模式的重复？

Question

我正在寻找一长串的DNA核苷酸，并寻找以起始代码“AAA”开始，以终止代码“CCC”结束的序列。由于核苷酸是三胞胎，所以我发现的每个序列的开始和结束之间的核苷酸数量必须是三的倍数。

例如，“aaaggccc”是有效序列，但“AAAGCCC”不是。

此外，在每一个停止代码之前，我想找到一个特定阅读框的最长链。

例如，如果DNA是“AAAGGGAAACCC”，那么“AAAGGGAAACCC”和“AAACCC”在技术上都是有效的，但是因为它们共享相同的停止代码实例，所以我只想要最长的DNA链“AAAGGGAAACCC”。此外，如果我的链是“aaaaggcccc”，则必须返回“aaaaggcccc”和“aaaggccccc”，因为它们位于不同的读取帧中（一个读取帧是mod 3，另一个是mod 1）

虽然我认为我有代码来搜索满足3倍要求且不重叠的字符串，但我不确定如何实现保持相同阅读框架的第二个条件。下面的代码只返回不重叠但不区分读取帧的最长字符串，因此在上面的示例中，它将捕获“AAAAGGCCC”而不是“aaaggccc”：

match = re.finditer(r"AAA\w{3}{%d}BBB$"% (minNucleotide-6, math.ceil((minNucleotide-6)/3))

很抱歉，你说得太多了，谢谢你看了一眼！

Answer 1

使用positive lookahead assertion。这允许您在字符串中的每个字符处重新应用regex，从而可以找到所有重叠的匹配项，因为lookahead断言不会像正常匹配那样使用任何字符。因为您仍然需要匹配一些实际的文本，所以可以使用capturing group进行匹配。

由于re.findall()返回捕获组的内容，而不是完整的regex匹配（它们都是''），因此可以使用：

>>> import re
>>> re.findall(r"(?=(AAA(?:\w{3})*?CCC))", "AAAAGGCCCC")
['AAAAGGCCC', 'AAAGGCCCC']

作为注释的Python函数：

def find_overlapping(sequence):
    return re.findall(
    """(?=        # Assert that the following regex could be matched here:
     (            # Start of capturing group number 1.
      AAA         # Match AAA.
      (?:         # Start of non-capturing group, matching...
       [AGCT]{3}  # a DNA triplet
      )*?         # repeated any number of times, as few as possible.
      CCC         # Match CCC.
     )            # End of capturing group number 1. 
    )             # End of lookahead assertion.""", 
    sequence, re.VERBOSE)

Answer 2

想到的最简单的模式是：

'AAA(\w{3})*CCC'
            ^^^ stop code
           ^ zero or more of…
    ^     ^ a group of…
     ^^^^^ three characters
 ^^^ start code

如果您对三个字符组的数量有额外的要求，比如“至少有两个这样的组”，那么现在可以很容易地用所需的内容替换正则表达式中的星型字符。

至于最长的匹配和不同的帧，我不确定。从技术上讲，星型字符已经是贪婪的，也就是说将匹配尽可能长的字符串，所以这应该满足您的要求。但是我担心这个特性和在一个帧中不共享子串的要求会产生不好的交互。

我认为最清楚的方法是让regex引擎为您提供所有匹配项，而不考虑长度和帧（只要内部部分的长度可以被3整除），然后在正则表达式之外解决问题。

如果您真的想使用regex引擎来实现这一点，有一种方法我可以考虑运行一个特定的regex三次，每帧一次。这些正则表达式将是：

^(?:\w{3})*AAA(\w{3})*CCC
^(?:\w{3})*\wAAA(\w{3})*CCC
^(?:\w{3})*\w\wAAA(\w{3})*CCC

如您所见，它们中的每一个首先匹配3k、3k+1或3k+2个字符，这样AAA开始代码将在不同的帧开始。要获得匹配的部分，您需要检查返回的match对象。我真的不知道重叠的序列会发生什么。