Eine komplexere Version von "Wie kann ich feststellen, ob sich eine Zeichenfolge in Python wiederholt?"

Question

Ich las this post und ich frage mich, ob jemand den Weg finden kann, sich wiederholende Motive in eine komplexere Zeichenfolge einzufangen.

Zum Beispiel finden Sie alle sich wiederholende Motive in

string = 'AAACACGTACGTAATTCCGTGTGTCCCCTATACGTATACGTTT' 

Hier die sich wiederholende Motive: 'AAAC ACGTACGT AATTCC gtgtgt CCCC TATACGTATACG TTT'

So sollte die Ausgabe sei etwas wie dieses:

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

Dieses Beispiel stammt von einem typischen biologischen Phänomen namens Mikrosatelliten, das in der DNA vorhanden ist.

UPDATE 1: Sternchen wurden aus der String-Variablen entfernt. Es war ein Fehler.

UPDATE 2: Ein einzelnes Zeichenmotiv zählt nicht. Zum Beispiel: in ACGUG AAA GUC, das A-Motiv wird nicht berücksichtigt.

Answer 1

können Sie eine Rekursion Funktion wie folgt verwendet werden:

Hinweis: Das Ergebnis Argument wird als globale Variable behandelt werden (da vorbei veränderbares Objekt an die Funktion wirkt sich auf den Anrufer)

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) 

Ergebnis:

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

Antwort zur vorherigen Frage für folgende Zeichenfolge:

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

können Sie beide Antworten verwenden, um von mentioned question und einige zusätzliche Rezepte:

Zuerst Sie die Zeichenfolge mit ** aufspalten kann dann eine neue Liste erstellen enthalten die wiederholten Strings mit r'(.+)\1+' regex:

So das Ergebnis sein wird:

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

Hinweis über 'ACGTACGT' dass verpasst die A am Ende!

Dann können Sie principal_period ‚s Funktion zu erhalten, die wiederholten Teilzeichenfolgen verwenden:

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

So werden Sie die wiederholten Saiten in l und Saiten in sub:

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

Sie dann brauche eine region, dass Sie es mit span Methode tun können:

Und endlich können Sie zip die 3 Liste regon, sub, l und ein dict Verständnis verwenden das erwartete Ergebnis zu erstellen:

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

Der Hauptcode:

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

Diese einfache, während Schleife erkennt alle sich wiederholenden Muster:

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

An diesem Punkt, motifs enthält alle wiederholten Mustern ... Lassen Sie uns filtern sie mit einigen Kriterien:

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

Sie die Tatsache nutzen, dass Lookaheads in regex, nicht die primäre Iterator vorzurücken. So können Sie nisten eine Capture-Gruppe innerhalb einer Look-Ahead, die (potentiell überlappende) Muster zu finden, und haben eine festgelegte Mindestlänge wiederholen:

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

Beachten Sie die leicht unterschiedlichen Ergebnissen zwischen einer gierigen und einen nicht-gierigen Quantor mit . Der gierige Quantifizierer sucht nach der längsten Wiederholungs-Teilzeichenkette, die von jedem Index in der ursprünglichen Zeichenkette ausgeht, falls eine existiert. Der nicht-gierige Quantifizierer sucht nach dem kürzesten Gleichen. Die Einschränkung besteht darin, dass Sie nur maximal ein Muster pro Startindex in der Zeichenfolge erhalten können. Wenn Sie Ideen haben, um dieses Problem zu lösen, lassen Sie es mich wissen! Potentiell können wir den greedy quantifier regex verwenden, um eine rekursive Lösung zu erstellen, die alle sich wiederholenden Muster von jedem Index ausgehend findet, aber wir vermeiden "vorzeitige Berechnung" für jetzt.

Wenn wir jetzt die Regex (?=(.{2,})\1+) nehmen und sie modifizieren, können wir auch die gesamte Teilkette erfassen, die wiederholte Motive enthält. Auf diese Weise können wir die span der Spiele verwenden, um die Anzahl der Wiederholungen zu berechnen:

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

In dem obigen regex, haben wir eine Capture-Gruppe in einer Capture-Gruppe in einem Look-Ahead. Jetzt haben wir alles, was wir brauchen, um das Problem zu lösen:

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

Da das gewünschte Verhalten in der Situation, wo ein Motiv wiederholt sich in mehreren „Regionen“ der Zeichenfolge nicht angegeben wurde, habe ich die Vermutung haben, dass OP möchten ein Wörterbuch von string->list, in dem jede Liste ihre eigenen Wörterbücher enthält.

Answer 4

Wenn Sie Ihre Abfrage anbinden können, können Sie einen einzelnen Durchlauf der Zeichenfolge verwenden.Die Anzahl der Vergleiche wird length of string * (max_length - min_length) sein, also linear skalieren.

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) 

Ausgang:

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 

Beachten Sie, dass dies ein faires paar überlappende Muster als die regexp Antworten fängt, aber ohne mehr zu wissen, was man ein gut Spiel betrachtet es schwierig ist, sie zu reduzieren weiter, zum Beispiel warum ist TATACG besser als ATACGT?

Extra: Das Verwenden eines Diktats zum Zurückgeben von Übereinstimmungen ist eine schlechte Idee, da die Muster nicht eindeutig sind.