Wie findet man ein Muster in einer Sequenz?
Ein Motiv ist ein kurzes Muster, das in einer Sequenz vorkommt, zum Beispiel ACA. Um Motive zu finden, schneidet man die Sequenz in alle Stücke einer festen Länge und zählt sie. Diese Stücke heißen k-Mere.
Mit k-Meren lässt sich zeigen, welches Stück besonders oft vorkommt. Das ist die Grundlage vieler Suchverfahren.
Am Ende dieser Lektion
Notiz
Ich kann ein Muster in einer Sequenz suchen und k-Mere zählen.
Schlüsselwörter
| Begriff | Was er bedeutet | Beispiel |
|---|---|---|
| Motiv | ein kurzes Muster, das gesucht wird | ACA |
| k-Mer | ein Stück der Länge k aus der Sequenz | ACG |
| Fenster | das Stück, das Schritt für Schritt weiterrückt | |
| Überlappung | zwei Vorkommen, die sich Basen teilen | |
| Häufigkeit | wie oft ein k-Mer vorkommt |
Die Zellen, die Lernende ausfüllen, bleiben in dieser Vorschau leer.
Ein Fenster schneidet alle k-Mere aus
Ein k-Mer ist ein Stück der Länge k. Um alle k-Mere einer Sequenz zu bekommen, schieben Sie ein Fenster der Länge k Base für Base weiter und schneiden jedes Stück aus.
Eine Sequenz der Länge n hat n minus k plus 1 Fenster. Bei ACGTACGT und k gleich 3 sind das 8 minus 3 plus 1, also 6.
Beispiel: k-Mere von ACGTACGT, k gleich 3
| Start | Stück | Schon gesehen? |
|---|---|---|
| 0 | ACG | Nein |
| 1 | CGT | Nein |
| 2 | GTA | Nein |
| 3 | TAC | Nein |
| 4 | ACG | Ja, zum zweiten Mal |
| 5 | CGT | Ja, zum zweiten Mal |
Die Zellen, die Lernende ausfüllen, bleiben in dieser Vorschau leer.
Alle 3-Mere auflisten
docker exec jupyter python3 -c "s='ACGTACGT'; k=3; print([s[i:i+k] for i in range(len(s)-k+1)])"Hier angezeigt, nicht ausgeführt. Erstellen Sie ein kostenloses Konto, um „Ausführen“ zu drücken und ihn im Terminal Ihres eigenen Labs einzugeben.
Die häufigsten 3-Mere zählen
docker exec jupyter python3 -c "from collections import Counter; s='ACGTACGT'; print(Counter(s[i:i+3] for i in range(len(s)-2)).most_common(2))"Hier angezeigt, nicht ausgeführt. Erstellen Sie ein kostenloses Konto, um „Ausführen“ zu drücken und ihn im Terminal Ihres eigenen Labs einzugeben.
Ein Motiv kann sich selbst überlappen
Um ein Motiv zu suchen, vergleichen Sie an jeder Stelle das Fenster mit dem Muster. Jede Übereinstimmung merken Sie sich mit ihrer Startstelle.
Dabei kann sich ein Motiv überlappen: In ACACACA beginnt ACA an den Stellen 0, 2 und 4. Die Vorkommen teilen sich Basen. Die Methode .count zählt solche Fälle nicht mit.
Alle Stellen eines Motivs finden
# Alle Stellen suchen, auch wenn sich Vorkommen überlappen.
sequenz = "ACACACA"
muster = "ACA"
stellen = []
for i in range(len(sequenz) - len(muster) + 1):
if sequenz[i:i + len(muster)] == muster:
stellen.append(i)
print(stellen)
print("count findet:", sequenz.count(muster))
# Suchen Sie das Muster "CAC". Was liefern beide Zeilen?
Was count bei Überlappung zählt
docker exec jupyter python3 -c "print('ACACACA'.count('ACA'))"Hier angezeigt, nicht ausgeführt. Erstellen Sie ein kostenloses Konto, um „Ausführen“ zu drücken und ihn im Terminal Ihres eigenen Labs einzugeben.
Ein häufiger Fehler
Warnung
Viele nehmen count für die Zahl aller Vorkommen. Die Methode zählt nur Vorkommen, die sich nicht überlappen, und liefert in ACACACA die 2 statt der 3. Wenn Überlappungen zählen, schieben Sie das Fenster selbst Base für Base.