Una versione più complessa di "Come posso sapere se una stringa si ripete in Python?"

Question

Stavo leggendo this post e mi chiedo se qualcuno possa trovare il modo di catturare motivi ripetitivi in ​​una stringa più complessa.

Per esempio, trovare tutti i motivi ripetitivi in ​​

string = 'AAACACGTACGTAATTCCGTGTGTCCCCTATACGTATACGTTT' 

Ecco i motivi ripetitivi: 'AAAC ACGTACGT AATTCC GTGTGT CCCC TATACGTATACG TTT'

Così, l'uscita dovrebbe essere qualcosa del genere:

output = {'ACGT': {'repeat': 2, 
        'region': (5,13)}, 
      'GT': {'repeat': 3, 
       'region': (19,24)}, 
      'TATACG': {'repeat': 2, 
        'region': (29,40)}} 

Questo esempio deriva da un tipico fenomeno biologico chiamato microsatellite che è presente nel DNA.

UPDATE 1: Gli asterischi sono stati rimossi dalla variabile stringa. È stato un errore.

UPDATE 2: il motivo a carattere singolo non viene conteggiato. Ad esempio: in ACGUG AAA GUC, il motivo "A" non viene preso in considerazione.

Answer 1

è possibile utilizzare una funzione di ricorsione come segue:

Nota: L'argomento risultato sarà trattata come una variabile globale (perché passando oggetto mutabile alla funzione influisce il chiamante)

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) 

risultato:

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

risposta alla precedente domanda per la seguente stringa:

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

È possibile utilizzare entrambe le risposte da mentioned question e alcune ricette in più:

In primo luogo è possibile dividere la stringa con ** quindi creare un nuovo elenco contiene le corde ripetuti con r'(.+)\1+' regex:

Così il risultato sarà:

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

Nota su 'ACGTACGT' che mancato il A alla fine!

Quindi è possibile utilizzare la funzione 's principal_period per ottenere le stringhe ripetute sub:

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

in modo da avere le stringhe ripetute in l e principali stringhe in sub:

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

Poi si è necessario il region che si può fare con il metodo span:

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

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

E alla fine si può comprimere il 3 lista regon, sub, l e utilizzare una comprensione dict per creare il risultato atteso:

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

Il codice principale:

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

Answer 2

Questa semplice, mentre loop rileva tutti i pattern ripetuti:

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

A questo punto, motifs contiene tutti gli schemi ripetuti ... Diamo loro filtro con alcuni criteri:

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

''' 
ATACGT 
ACGT 
TATACG 
CGTA 
''' 

Answer 3

È possibile utilizzare il fatto che in regex, lookaheads non avanzare l'iteratore primario. Così, è possibile nidificare un gruppo di acquisizione all'interno di un lookahead per trovare le (potenzialmente sovrapposti) i modelli che si ripetono e hanno una lunghezza minima specificata:

>>> 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'] 

Nota i risultati leggermente diversi tra l'utilizzo di un avido e un quantificatore non avido . Il quantificatore avido cerca la sottostringa ripetuta più lunga che inizia da ogni indice nella stringa originale, se ne esiste uno. Il quantificatore non avido cerca il più breve degli stessi. La limitazione è che puoi ottenere un massimo di un modello per indice di partenza nella stringa. Se hai qualche idea per risolvere questo problema, fammi sapere! Potenzialmente, possiamo usare la regex del quantificatore avido per impostare una soluzione ricorsiva che trovi ogni schema di ripetizione a partire da ciascun indice, ma per ora evitiamo "calcoli prematuri".

Ora se prendiamo la regex (?=(.{2,})\1+) e la modifichiamo, possiamo anche catturare l'intera sottostringa che contiene motivi ripetuti. In questo modo, siamo in grado di utilizzare il span delle partite per calcolare il numero di ripetizioni:

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

Nella regex sopra, abbiamo un gruppo di acquisizione all'interno di un gruppo di acquisizione all'interno di un lookahead. Ora abbiamo tutto quello che serve per risolvere il problema:

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

Poiché il comportamento desiderato nella situazione in cui non è stato specificato un motivo si ripete in diverse "regioni" della stringa, ho fatto l'ipotesi che OP vorrebbe un dizionario di string->list in cui ogni lista contiene il proprio insieme di dizionari.

Answer 4

Se è possibile limitare la query, è possibile utilizzare un singolo passaggio della stringa.Il numero di confronti sarà length of string * (max_length - min_length) quindi verrà scalato linearmente.

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) 

uscita:

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 

Si noti che questa cattura una fiera pochi modelli più sovrapposizione rispetto alle risposte regexp, ma senza sapere di più su ciò che si considera un buon partita è difficile per ridurlo inoltre, ad esempio, perché TATACG è migliore di ATACGT?

Extra: usare un comando per restituire le corrispondenze è una cattiva idea in quanto i pattern non saranno unici.