Regex - подсчет наибольшего количества коротких тандемных повторов

Question

Я перебираю список коротких тандемных повторов и пытаюсь найти наибольшее количество раз, когда они встречаются последовательно в последовательности ДНК.

Последовательность:

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

Когда в строке, которую вы ищете, нет ничего динамического c и особенно , когда строка, которую вы ищете, велика, я бы попытался найти решение, которое избегает регулярных выражений потому что базовые c строковые методы обычно значительно быстрее, чем регулярное выражение * значительно превосходит регулярное выражение, а арифметика c для вычисления позиций строки занимает незначительное время.

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

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

Чтобы найти все последовательности AGAT C, пока они не находятся в конце последовательности, вы можете использовать:

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

С the python документация по \B:

Соответствует пустой строке, но только когда она не в начале или конце слова. Это означает, что r'py\B' соответствует 'python', 'py3', 'py2', но не 'py', 'py.' или 'py!'. \B является полной противоположностью \b, поэтому символами слова в шаблонах Unicode являются буквенно-цифровые символы Unicode или подчеркивание, хотя это можно изменить с помощью флага ASCII. Границы слова определяются текущей локалью, если используется флаг LOCALE.

Answer 4

Вот подход функционального программирования. На каждом шаге рекурсии обнаруживаются первые вхождения последовательного повтора, а после этого они исключаются из строки поиска. Вы ведете запись максимального числа найденных повторов и передаете его каждому рекурсивному вызову, пока последовательных повторов больше не будет найдено.

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))