Как поймать самую длинную последовательность в группе

Question

Задача состоит в том, чтобы найти самую длинную последовательность из группы

, например, для данной последовательности ДНК: "AGATCAGATCTTTTTTCTAATGTCTAGGATATATCAGATCAGATCAGATCAGATCAGATC" и в ней есть 7 вхождений AGAT C. (AGATC) соответствует всем вхождениям. Можно ли написать регулярное выражение, которое улавливает только самую длинную последовательность, т.е. AGATCAGATCAGATCAGATCAGATC в заданном тексте? Если это невозможно только с регулярным выражением, как я могу перебрать каждую последовательность (т.е. 1-я последовательность - AGATCAGATC, 2-я - AGATCAGATCAGATCAGATCAGATC и так далее) в python?

Answer 1

Центральный вопрос: «Можно ли написать регулярное выражение, которое улавливает только самую длинную последовательность?» Ответ - «да»:

import re

s = 'AGATC_AGATCAGATC_AGATCAGATCAGATC_AGATC_AGATCAGATC'

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

Regex demo _{^< ¯ \ (ツ) / ¯ ></sup>} Python demo

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.findall, в отличие от re.search, также будет соответствовать AGATCAGATC в конце строки.)

Если использовалось re.findall, может быть несколько совпадений после самого длинного (см. Последний тест строка в ссылке на демонстрацию регулярного выражения), но длины совпадений не уменьшаются от первого до последнего. Следовательно, первое совпадение, полученное с использованием re.search, является самым длинным совпадением.

Answer 2

Используйте:

import re

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

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

Объяснение:

Группа без захвата (?:AGATC)+

• + Квантификатор - Соответствует от одного до неограниченного времени, столько раз, сколько возможно.
• AGATC соответствует символам AGAT C буквально (с учетом регистра)

Результат:

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

# print(longest)
'AGATCAGATCAGATCAGATCAGATC'

Вы можете проверить регулярное выражение here.

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