Ответ 1

вы можете использовать функцию рекурсии следующим образом:

Примечание. Аргумент результата будет рассматриваться как глобальная переменная (поскольку передача изменяемого объекта в функцию влияет на вызывающего)

import re
def finder(st,past_ind=0,result=[]):
   m=re.search(r'(.+)\1+',st)
   if m:
      i,j=m.span()
      sub=st[i:j]
      ind = (sub+sub).find(sub, 1)
      sub=sub[:ind]
      if len(sub)>1:
        result.append([sub,(i+past_ind+1,j+past_ind+1)])
      past_ind+=j
      return finder(st[j:],past_ind)
   else:
      return result



s='AAACACGTACGTAATTCCGTGTGTCCCCTATACGTATACGTTT'
print finder(s)

результат:

[['ACGT', (5, 13)], ['GT', (19, 25)], ['TATACG', (29, 41)]]

ответьте на предыдущий вопрос для следующей строки:

s = 'AAAC**ACGTACGTA**ATTCC**GTGTGT**CCCC**TATACGTATACG**TTT'

Вы можете использовать оба ответа из упомянутого вопроса и некоторые дополнительные рецепты:

Сначала вы можете разделить строку на **, а затем создать новый список, содержащий повторяющиеся строки с r'(.+)\1+' regex:

Таким образом, результат будет:

>>> new=[re.search(r'(.+)\1+',i).group(0) for i in s.split('**')]
>>> new
['AAA', 'ACGTACGT', 'TT', 'GTGTGT', 'CCCC', 'TATACGTATACG', 'TTT']

Примечание о 'ACGTACGT', который пропустил A в конце!

Затем вы можете использовать функцию principal_period для получения повторяющихся подстрок:

def principal_period(s):
    i = (s+s).find(s, 1, -1)
    return None if i == -1 else s[:i]

>>> for i in new:
...    p=principal_period(i)
...    if p is not None and len(p)>1:
...        l.append(p)
...        sub.append(i)
... 

Итак, у вас будут повторяющиеся строки в l и основные строки в sub:

>>> l
['ACGT', 'GT', 'TATACG']
>>> sub
['ACGTACGT', 'GTGTGT', 'TATACGTATACG']

Затем вам понадобится region, который вы можете сделать с помощью метода span:

>>> for t in sub:
...    regons.append(re.search(t,s).span())

>>> regons
[(6, 14), (24, 30), (38, 50)]

И, наконец, вы можете закрепить 3 списка regon, sub, l и использовать понимание dict для создания ожидаемого результата:

>>> z=zip(sub,l,regons)
>>> out={i :{'repeat':i.count(j),'region':reg} for i,j,reg in z}
>>> out
{'TATACGTATACG': {'region': (38, 50), 'repeat': 2}, 'ACGTACGT': {'region': (6, 14), 'repeat': 2}, 'GTGTGT': {'region': (24, 30), 'repeat': 3}}

Основной код:

>>> s = 'AAAC**ACGTACGTA**ATTCC**GTGTGT**CCCC**TATACGTATACG**TTT'
>>> sub=[]
>>> l=[]
>>> regon=[]
>>> new=[re.search(r'(.+)\1+',i).group(0) for i in s.split('**')]
>>> for i in new:
...    p=principal_period(i)
...    if p is not None and len(p)>1:
...        l.append(p)
...        sub.append(i)
... 

>>> for t in sub:
...    regons.append(re.search(t,s).span())
... 
>>> z=zip(sub,l,regons)
>>> out={i :{'repeat':i.count(j),'region':reg} for i,j,reg in z}
>>> out
{'TATACGTATACG': {'region': (38, 50), 'repeat': 2}, 'ACGTACGT': {'region': (6, 14), 'repeat': 2}, 'GTGTGT': {'region': (24, 30), 'repeat': 3}}

Ответ 2

Если вы можете связать свой запрос, вы можете использовать один проход строки. Число сравнений будет length of string * (max_length - min_length), поэтому масштабируется линейно.

s = 'AAACACGTACGTAATTCCGTGTGTCCCCTATACGTATACGTTT'

def find_repeats(s, max_length, min_length=2):

    for i in xrange(len(s)):
        for j in xrange(min_length, max_length+1):
            count = 1
            while s[i:i+j] == s[i+j*count:i+j*count+j]: count += 1
            if count > 1:
                yield s[i:i+j], i, count

for pattern, position, count in find_repeats(s, 6, 2):
    print "%6s at region (%d, %d), %d repeats" % (pattern, position, position + count*len(pattern), count)

Вывод:

    AC at region (2, 6), 2 repeats
  ACGT at region (4, 12), 2 repeats
  CGTA at region (5, 13), 2 repeats
    GT at region (18, 24), 3 repeats
    TG at region (19, 23), 2 repeats
    GT at region (20, 24), 2 repeats
    CC at region (24, 28), 2 repeats
    TA at region (28, 32), 2 repeats
TATACG at region (28, 40), 2 repeats
ATACGT at region (29, 41), 2 repeats
    TA at region (34, 38), 2 repeats

Обратите внимание, что это наследует несколько более наложенных шаблонов, чем ответы регулярного выражения, но, не зная больше о том, что вы считаете совпадением хорошего, его трудно уменьшить, например, почему это значение TATACG лучше, чем ATACGT?

Дополнительно: использование диктата для возврата матчей - плохая идея, поскольку шаблоны не будут уникальными.

Ответ 3

Этот простой цикл while обнаруживает все повторяющиеся шаблоны:

def expand():
    global hi
    hi += 1

def shrink():
    global lo
    lo += 1

s = 'AAACACGTACGTAATTCCGTGTGTCCCCTATACGTATACGTTT'

motifs = set()

lo = 0
hi = 0

f = expand

while hi <= len(s):
    sub = s[lo : hi+1]
    if s.count(sub) > 1:
        motifs.add(sub)
        if lo==hi: f = expand
        f()
    else:
        f = shrink if lo<=hi else expand
        f()

В этот момент motifs содержит все повторяющиеся шаблоны... Пусть фильтрует их с некоторыми критериями:

minlen = 3
for m in filter(lambda m: len(m)>=minlen and s.count(2*m)>=1, motifs):
    print(m)

'''
ATACGT
ACGT
TATACG
CGTA
'''

Ответ 4

Вы можете использовать тот факт, что в regex, lookaheads не продвигают первичный итератор. Таким образом, вы можете вложить группу захвата в lookahead, чтобы найти (потенциально перекрывающиеся) шаблоны, которые повторяются и имеют заданную минимальную длину:

>>> import re
>>> s = 'AAACACGTACGTAATTCCGTGTGTCCCCTATACGTATACGTTT'
>>> re.findall(r'(?=(.{2,})\1+)', s)
['AC', 'ACGT', 'CGTA', 'GT', 'TG', 'GT', 'CC', 'TATACG', 'ATACGT', 'TA']
>>> re.findall(r'(?=(.{2,}?)\1+)', s)
['AC', 'ACGT', 'CGTA', 'GT', 'TG', 'GT', 'CC', 'TA', 'ATACGT', 'TA']

Обратите внимание на несколько разные результаты между использованием жадного и неживого квантификатора. Жадный квантификатор ищет самую длинную повторяющуюся подстроку, начиная с каждого индекса исходной строки, если таковой существует. Нежелательный квантификатор ищет самый короткий из них. Ограничение состоит в том, что вы можете получить максимум один шаблон для каждого начального индекса в строке. Если у вас есть идеи решить эту проблему, дайте мне знать! Потенциально, мы можем использовать жадное квантификатор regex, чтобы настроить рекурсивное решение, которое находит каждый повторяющийся шаблон, начиная с каждого индекса, но пока не допускайте "преждевременных вычислений".

Теперь, если мы возьмем регулярное выражение (?=(.{2,})\1+) и изменим его, мы также можем захватить всю подстроку, содержащую повторяющиеся мотивы. Посредством этого мы можем использовать span совпадений для вычисления числа повторений:

(?=((.{2,})\2+))

В приведенном выше регулярном выражении у нас есть группа захвата внутри группы захвата внутри lookahead. Теперь у нас есть все необходимое для решения проблемы:

def repeated_motifs(s):
    import re
    from collections import defaultdict
    rmdict = defaultdict(list)
    for match in re.finditer(r'(?=((.{2,})\2+))', s):
        motif = match.group(2)
        span1, span2 = match.span(1), match.span(2)
        startindex = span1[0]
        repetitions = (span1[1] - startindex) // (span2[1] - startindex)
        others = rmdict[motif]
        if not others or startindex > others[-1]['region'][1]:
            others.append({'repeat': repetitions, 'region': span1})
    return rmdict


s = 'AAACACGTACGTAATTCCGTGTGTCCCCTATACGTATACGTTT'
d = repeated_motifs(s)
print(d)
# list of the repeating motifs we have found sorted by first region
print(sorted(list(d.keys()), key=lambda k: d[k][0]['region']))

Поскольку желаемое поведение в ситуации, когда мотив повторяется в нескольких "областях" строки, не указывается, я сделал предположение, что OP хотел бы использовать словарь string->list, где каждый список содержит свой собственный набор словарей.