正则表达式 - 计算最大数量的短串联重复

Question

我正在遍历短串联重复序列的列表，并试图找到它们在 DNA 序列中连续出现的最大次数。

序列：

AAGGTAAGTTTAGAATATAAAAGGTGAGTTAAATAGAATAGGTTAAAATTAAAGGAGATCAGATCAGATCAGATCTATCTATCTATCTATCTATCAGAAAAGAGAGATCAGATCAGTTAAAGAGTAAGATATTGAATTAATGGAAAATATTGTTGGGGAAAGGAGGGATAGAGATCAGATC

STRs = ['AGATC', 'AATG', 'TATC']

for STR in STRs:
    max_repeats = len(re.findall(f'(?<={STR}){STR}', sequence))
    print(max_repeats)

序列中最大连续重复次数为4

我当前的正则表达式仅返回 3 个匹配项，因为正向后视，我也不太确定如何修改我的代码以捕获最大数量的重复 (4)，而不包括其他重复组，是可以检索匹配项的嵌套列表，我可以对其进行迭代以找到最大数量，如下所示。

[[AGATC, AGATC, AGATC, AGATC], [AGATAC,AGATC], [AGATC, AGATC]]

Answer 1

要查找 AGATC 的所有序列，只要它不在序列的末尾，您可以使用：

>>> re.findall(r'AGATC\B', sequence)
['AGATC', 'AGATC', 'AGATC', 'AGATC']

来自 the python documentation on \B:

Matches the empty string, but only when it is not at the beginning or end of a word. This means that r'py\B' matches 'python', 'py3', 'py2', but not 'py', 'py.', or 'py!'. \B is just the opposite of \b, so word characters in Unicode patterns are Unicode alphanumerics or the underscore, although this can be changed by using the ASCII flag. Word boundaries are determined by the current locale if the LOCALE flag is used.

Answer 2

这是解决问题的一种方法：

>>> STRs = ['AGATC', 'AATG', 'TATC']
>>> pattern = '|'.join(f'({tgt})+' for tgt in STRs)
>>> for mo in re.finditer(pattern, seq):
         print(mo.group(0))

AGATCAGATCAGATCAGATC
TATCTATCTATCTATCTATC
AGATCAGATC
AATG
AGATCAGATC

主要观点：

1) 核心模式 + 用于一个组以允许连续重复：

(AGATC)+

2) 模式与 | 组合以允许任何 STR 匹配：

>>> pattern
'(AGATC)+|(AATG)+|(TATC)+'

3) re.finditer() 调用一次给出一个匹配对象。

4) 如果需要，匹配对象可以提供其他信息，例如用于计算长度的起点和终点或用于显示匹配的 STR 的元组：

>>> mo.group(0)
'AGATCAGATC'
>>> mo.span()
(171, 181)
>>> mo.groups()
('AGATC', None, None)

如何计算最大重复次数：

>>> tracker = dict.fromkeys(STRs, 0)
>>> for mo in re.finditer(pattern, seq):
        start, end = mo.span()
        STR = next(filter(None, mo.groups()))
        reps = (end - start) // len(STR)
        tracker[STR] = max(tracker[STR], reps)

>>> tracker
{'AGATC': 4, 'AATG': 1, 'TATC': 5}

Answer 3

这是一种函数式编程方法。在每个递归步骤中，找到连续重复的第一次出现，然后从搜索字符串中删除。您记录到目前为止发现的最大重复次数，并将其传递给每个递归调用，直到再也找不到连续的重复次数。

def find_repeats (pattern, seq, max_r=0):
    g = re.search(f'{pattern}({pattern})+', seq)
    if g:
        max_repeats = len ( g.group() ) / len(pattern)
        return find_repeats (pattern, seq.replace (g.group(), '', 1), max (max_r, max_repeats) )
    else:
        return max_r

print (find_repeats ('AGATC', sequence))

Answer 4

当您要搜索的字符串中没有任何动态内容时，并且尤其是当您要搜索的字符串很大时，我会尝试找到解决方案这避免了正则表达式，因为基本的字符串方法通常比正则表达式快得多。

以下可能在多个方面都不是 Pythonic（欢迎提出改进建议），但潜在的假设是 str.split() 大大优于正则表达式，并且计算字符串位置的算法所花费的时间可以忽略不计。

def find_tandem_repeats(sequence, search):
    """ searches through an DNA sequence and returns (position, repeats) tuples """
    if sequence == '' or search == '':
        return

    lengths = list(map(len, sequence.split(search)))
    pos = lengths[0]
    repeats = 0
    pending = False

    for l in lengths[1:]:
        if l == 0:
            pending = True
            repeats += 1
            continue
        repeats += 1
        yield (pos, repeats)
        pos += l + len(search) * repeats
        repeats = 0
        pending = False

    if pending:
        yield (pos, repeats)

用法：

data = "AAGGTAAGTTTAGAATATAAAAGGTGAGTTAAATAGAATAGGTTAAAATTAAAGGAGATCAGATCAGATCAGATCTATCTATCTATCTATCTATCAGAAAAGAGAGATCAGATCAGTTAAAGAGTAAGATATTGAATTAATGGAAAATATTGTTGGGGAAAGGAGGGATAGAGATCAGATC"
positions = list(find_tandem_repeats(data, 'AGATC'))

for position in positions:
    print("at index %s, repeats %s times" % position)

max_position = max(positions, key=lambda x: x[1])
print("maximum at index %s, repeats %s times" % max_position)

输出

at index 55, repeats 4 times
at index 104, repeats 2 times
at index 171, repeats 2 times
maximum at index 55, repeats 4 times

正则表达式 - 计算最大数量的短串联重复

Regex - Counting greatest number of short tandem repeats

python

regex

bioinformatics