在 Python 中使用正则表达式查找重叠匹配项和子匹配项

Question

我有一串字符（一个 DNA 序列），我设计了一个正则表达式来过滤掉可能的匹配项，(?:ATA|ATT)[ATCGN]{144,16563}(?:AGA|AGG|TAA|TAG)。稍后我应用两个过滤条件：

序列必须能被 3、len(match) % 3 == 0 和
字符串结尾前不能有终止密码子(['AGA', 'AGG', 'TAA', 'TAG'])，not any(substring in list(sliced(match[:-3], 3)) for substring in [x.replace("U", "T") for x in stop_codons]).

但是，当我应用这些过滤器时，我根本没有得到任何匹配项（在过滤器之前我得到大约 200 个匹配项。我在完整序列中搜索子字符串的方式是运行 re.findall(regex, genome_fasta, overlapped=True)，因为匹配项可能是其他匹配项的子匹配项。

我对正则表达式有什么误解吗？据我所知，在过滤器之后我应该仍然有匹配项。

如果还有什么需要补充的，请告诉我！（我使用的是 Python 3.4 的 regex 包，而不是标准的 re 包，因为它不支持重叠。

编辑 1：

根据评论：我正在寻找线粒体基因组中的 ORF，但只考虑长度至少为 150 个核苷酸（字符）的那些。考虑重叠很重要，因为匹配可能包括字符串中的第一个起始密码子和字符串中的最后一个终止密码子，但中间可能有另一个起始密码子。例如：

给定 "ATAAAGCCATTTACCGTACATAGCACATTATAACCAACAAACCTACCCACCCTTAACTAG"，匹配应该是 "ATAAAGCCATTTACCGTACATAGCACATTATAACCAACAAACCTACCCACCCTTAACTAG"，但也应该是 "ATAAAGCCATTTACCGTACATAGCACATTATAA"，因为 "TAG" 和 "TAA" 都是终止密码子。

编辑 2：

完全是错误的评论，方法的完整代码是：

typical_regex = r"%s[ATCGN]{%s,%s}%s" % (proc_start_codons, str(minimum_orf_length - 6), str(maximum_orf_length - 6), proc_stop_codons)

typical_fwd_matches = []
    if re.search(typical_regex, genome_fasta, overlapped=True):
        for match in re.findall(typical_regex, genome_fasta, overlapped=True):
            if len(match) % 3 == 0:
                if not any(substring in list(sliced(match[:-3], 3)) for substring in [x.replace("U", "T") for x in stop_codons]):
                    typical_fwd_matches.append(match)

print(typical_fwd_matches)

typical_fwd_matches 数组为空，正则表达式在打印到 console/file 时呈现为 (?:ATA|ATT)[ATCGN]{144,16563}(?:AGA|AGG|TAA|TAG)。

Answer 1

我认为你可以这样做。
子集将由不断减小的先前匹配项组成。
这就是您要做的所有事情。
因此，设计正则表达式相当简单。

正则表达式将只匹配 3 个字符的倍数。
开头和中间在第1组中捕获。
这用于新的 text 值，它只是最后一个匹配项
减去最后 3 个字符。

正则表达式解释：

 (                             # (1 start), Whole match minus last 3 chars
      (?: ATA | ATT )               # Starts with one of these 3 char sequence
      (?:                           # Cluster group
           [ATCGN]{3}                    # Any 3 char sequence consisting of these chars
      )+                            # End cluster, do 1 to many times
 )                             # (1 end)
 (?: AGA | AGG | TAA | TAG )   # Last 3 char sequence, one of these

Python 代码示例：

Demo

import re

r = re.compile(r"((?:ATA|ATT)(?:[ATCGN]{3})+)(?:AGA|AGG|TAA|TAG)")
text = "ATAAAGCCATTTACCGTACATAGCACATTATAACCAACAAACCTACCCACCCTTAACTAG"

m = r.search(text)
while m:
    print("Found:  " + m.group(0))
    text = m.group(1)
    m = r.search(text)

输出：

Found:  ATAAAGCCATTTACCGTACATAGCACATTATAACCAACAAACCTACCCACCCTTAACTAG
Found:  ATAAAGCCATTTACCGTACATAGCACATTATAA
Found:  ATTTACCGTACATAG

使用这种方法，被测试的子集是这些：

ATAAAGCCATTTACCGTACATAGCACATTACAACCAACAACCTACCCACCCTTAACTAG
ATAAAGCCATTTACCGTACATAGCACATTAACCAACAAACCTACCACCCTTAAC
ATAAAGCCATTTACCGTACATAGCACATTA
ATTTACCGTACA

我们可以对正则表达式匹配这些的时间进行基准测试。

Regex1:   ((?:ATA|ATT)(?:[ATCGN]{3})+)(?:AGA|AGG|TAA|TAG)
Completed iterations:   50  /  50     ( x 1000 )
Matches found per iteration:   3
Elapsed Time:    1.63 s,   1627.59 ms,   1627594 µs
Matches per sec:   92,160

在 Python 中使用正则表达式查找重叠匹配项和子匹配项

Find overlapping matches and submatches using regular expressions in Python

regex

string-matching

dna-sequence

python-3.4