如何捕获一组中最长的连续序列

Question

任务是找到一组中最长的序列。

例如，给定DNA序列："AGATCAGATCTTTTTTCTAATGTCTAGGATATATCAGATCAGATCAGATCAGATCAGATC"， 其中有7个AGATC出现。 (AGATC) 匹配所有出现。 是否可能编写一个正则表达式，只捕获给定文本中最长的序列，即 AGATCAGATCAGATCAGATCAGATC ？

如果仅使用正则表达式无法实现，则如何在 Python 中迭代每个序列（即第1个序列为 AGATCAGATC ，第2个序列为 AGATCAGATCAGATCAGATCAGATC 等）？

- hamvee

Answer 1

使用：

import re

sequence = "AGATCAGATCTTTTTTCTAATGTCTAGGATATATCAGATCAGATCAGATCAGATCAGATC"
matches = re.findall(r'(?:AGATC)+', sequence)

# To find the longest subsequence
longest = max(matches, key=len)

解释：

非捕获型分组 (?:AGATC)+

• + 量词符号 — 匹配一次或多次，尽可能多的匹配。
• AGATC 匹配含有字母 AGATC 的字符（区分大小写）

结果：

# print(matches)
['AGATCAGATC', 'AGATCAGATCAGATCAGATCAGATC']

# print(longest)
'AGATCAGATCAGATCAGATCAGATC'

你可以在这里测试正则表达式。

- Shubham Sharma

---

如此简短而优雅的解决方案！非常感谢您。 - hamvee

这是一个好的解决方案，可能是我会使用的，但它并没有回答问题：“是否可能编写一个正则表达式只捕获最长序列？” - Cary Swoveland

@CarySwoveland 嗯，对于这个问题，我采取了一种替代方法，即使它不能仅使用正则表达式找到最长的单个子序列，但它确实可以找到所有最长可能长度的连续子序列，因此我们可以轻松地使用max函数选择最长的子序列。 - Shubham Sharma

Answer 2

中心问题是：“是否能编写一个正则表达式，只捕获最长的序列？”答案是“是”：

import re

s = 'AGATC_AGATCAGATC_AGATCAGATCAGATC_AGATC_AGATCAGATC'

m = re.search(r'((?:AGATC)+)(?!.*\1)', s)
print m.group() if m else ''
  #=> "AGATCAGATCAGATC"

Python的正则表达式引擎执行以下操作。

正则表达式演示_{^<¯\(ツ)/¯^>}Python演示

(            begin capture group 1
  (?:AGATC)  match 'AGATC' in a non-capture group
  +          execute the non-capture group 1+ times
)            end capture group 1
(?!          begin a negative lookahead
  .*         match 0+ characters
  \1         match the content of capture group 1
)            end the negative lookahead

对于上面的字符串s，首先会匹配AGATC，但是负向先行断言会将AGATC视为AGATCAGATC的第一部分，因此暂定的匹配将被拒绝。接下来，AGATCAGATC会被匹配，但是负向先行断言会将AGATCAGATC视为AGATCAGATCAGATC的第一部分，所以该暂定匹配也将被拒绝。然后，AGATCAGATCAGATC将被匹配并接受，因为负向先行断言在字符串中找不到那个匹配。（与re.search不同，re.findall还会在字符串末尾匹配AGATCAGATC）。

如果使用re.findall，则可能在最长匹配后有多个匹配（请参见正则表达式演示链接中的最后一个测试字符串），但是匹配的长度从第一个到最后一个是非递减的。因此，使用re.search获得的第一个匹配是最长的匹配。

- Cary Swoveland

---

@caryswoveland 回答得很好，点赞 +1。 - Shubham Sharma

Answer 3

使用re.finditer()遍历所有匹配项。然后使用带有键函数的max()找到最长的匹配项。将其制作成一个函数，以便您可以使用不同的组。

import re

def find_longest(sequence, group):
    # build pattern
    pattern = fr"(?:{group})+"

    # iterate over all matches
    matches = (match[0] for match in re.finditer(pattern, sequence))

    # find the longest
    return max(matches, key=len)

seq = "AGATCAGATCTTTTTTCTAATGTCTAGGATATATCAGATCAGATCAGATCAGATCAGATC"

find_longest(seq, "AGATC")

- RootTwo