Найти повторы с определенной длиной в строку, используя Python

Question

Я пытаюсь использовать regex модуль для поиска неперекрывающиеся повторы (дублированные подстроки) в пределах заданной строки (30 символов), с учетом следующих требований:

1. Меня интересуют только неперекрывающиеся повторы длиной 6-15 символов.
2. позволяет 1 неправильно матч
3. возвратных позиции для каждого матча

Один из способов я подумал о том, что для каждой возможной длины повтора, пусть цикл питона через вход 30char строки. Например,

string = "ATAGATATATGGCCCGGCCCATAGATATAT" #input 

#for 6char repeats, first one in loop would be for the following event: 

text = "ATAGAT" 
text2 ="(" + text + ")"+ "{e<=1}" #this is to allow 1 mismatch later in regex 

string2="ATATGGCCCGGCCCATAGATATAT" #string after excluding text 

for x in regex.finditer(text2,string2,overlapped=True): 
    print x.span() 

#then still for 6char repeats, I will move on to text = "TAGATA"... 
#after 6char, loop again for 7char... 

Там должно быть два выхода для этой конкретной строки = "ATAGATATAT GGCCCGGCCC ATAGATATAT". 1. Смелое два несоответствия «ATAGATATAT» + 1: «ATAGATATATG» & «CATAGATATAT» с индексом положения, возвращенным как (0,10) & (19, 29); 2. «TGGCCC» & «GGCCCA» (необходимо добавить одно несоответствие не менее 6 символов), с индексом (9,14) & (15,20). Числа могут быть в списке или таблице.

Извините, что я не включил реальный цикл, но я надеюсь, что идея понятна ... Как вы можете видеть, это очень менее эффективный метод, не говоря уже о том, что он создаст избыточность - - например Повторы 10char будут засчитываться более одного раза, поскольку они подходят для 9,8,7 и 6 циклов повторений символов. Более того, у меня есть много таких 30 символов, с которыми нужно работать, поэтому я буду благодарен за ваши советы по поводу более чистых методов.

Большое спасибо :)

Answer 1

Я хотел бы попробовать простой алгоритм вместо регулярных выражений (которые довольно запутанным в данном случае);

s = "ATAGATATATGGCCCGGCCCATAGATATAT" 

def fuzzy_compare(s1, s2): 
    # sanity check 
    if len(s1) != len(s2): 
     return False 

    diffs = 0 
    for a, b in zip(s1, s2): 
     if a != b: 
      diffs += 1 

     if diffs > 1: 
      return False   

    return True 

slen = len(s) # 30 
for l in range(6, 16): 
    i = 0 
    while (i + l * 2) <= slen: 
    sub1 = s[i:i+l] 
    for j in range(i+l, slen - l): 
     sub2 = s[j:j+l] 
     if fuzzy_compare(sub1, sub2): 
      # checking if this could be partial 
      partial = False 
      if i + l < j and j + l < slen: 
       extsub1 = s[i:i+l+1] 
       extsub2 = s[j:j+l+1] 
       # if it is partial, we'll get it later in the main loop 
       if fuzzy_compare(extsub1, extsub2): 
        partial = True 

      if not partial: 
       print (i, i+l), (j, j+l) 

    i += 1 

Это первый проект, поэтому не стесняйтесь экспериментировать с ним. Это также кажется неуклюжим и не оптимальным, но сначала попробуйте запустить его - этого может быть достаточно.