Übungen (Fragen) Flashcards
Erweitern Sie den Algorithmus zur Bestimmung der optimalen Edit-Distanz, so dass zusätzlich auch die Anzahl der co-optimalen Alignments zweier Sequenzen bestimmt wird.
Die Idee ist einer zusätzlichen Matrix. Die Anzahl der co-optimalen Alignments kann parallel zur Edit-Distanz-Berechnung mitgeführt werden, indem man für jeden Eintrag die Summe der möglichen Pfade speichert. Die Zeitkomplexität bleibt O(mn), da die Berechnungen unverändert sind. Der Speicherverbrauch verdoppelt sich, bleibt aber asymptotisch O(mn), da nur eine zusätzliche Matrix gespeichert wird.
Sequenzvergleiche – warum?
Erkennen von Mutationen und deren Auswirkungen. Ähnliche Sequenzen deuten auf gemeinsamen Ursprung hin. Identifikation unbekannter Genfunktionen.
Sequenzdistanzen - Eigenschaften
d ist eine Metrik wenn:
1. d(x,y) = 0 nur wenn x = y
2. d(x,y) = d(y,x) für alle x,y
3. d(x,y) ≤ 𝑑 (𝑥, 𝑧) + 𝑑 (𝑧, 𝑦) für alle x,y,z
Rekursive Berechnung der Edit-Distanz Formel
Needleman-Wunsch Komplexität
Wir berechnen jedes Feld einer zwei
-dimensionalen (quadratischen) Matrix einmal
* Für jedes Feld ‚überprüfen‘ wir eine konstante Anzahl an Vorgängern (genau 3)
* Zeitkomplexität: O(nm) (oder
O(n^2))
* Platzkomplexität: O(nm) (2
-D Matrix!)
Needleman-Wunsch-Algorithmus Ablauf
- Initialisierung
- Matrix-Füllung (match, mismatch, gap)
- Backtracking
Rekursive Formel für alle Alignments
A(i,j)=A(i−1,j−1)+A(i−1,j)+A(i,j−1)
mit A(i,0) = 1 und A(0,j) = 1 als Basisfälle. Diese Formel zählt alle möglichen Alignments, auch nicht optimale.
Implementierung edit_recursive und edit_dynamic
Rekursiv: Zerlegt Problem in kleinere Instanzen und ruft sich selbst auf (ineffizient ohne Memoization).if len(x)=0 return len(y), if len (y) = 0 return len(x) ifx[-1] =y[-1] return edit_rec(x[:-1],y[:-1]) #berechnungen insert = edit_rec(x, y[:-1]) del = edit_rec(x[:-1], y) substr=edit_rec(x[:-1], y[:-1]) return 1+ min(insert, del, substr)
Dynamisch: Erstellt eine Matrix, füllt erste Zeile und Spalte mit Längen, dann füllt sie iterativ die restlichen Werte.
Warum verwendet man einen eigenen Algorithmus zur Berechnung von lokalen Alignments, anstatt die globalen Alignments aller Paare von Substrings zu berechnen und sich das beste Alignment auszusuchen? Nennen Sie auch die Laufzeitkomplexität beider Strategien!
Globales Alignment für alle Substrings wäre O(n⁶), da O(n⁴) Vergleiche mit O(n²) Aufwand nötig sind. Lokales Alignment erkennt konservierte Regionen, ohne unähnliche Bereiche zu beeinflussen.
Affine Gap-Kosten & Needleman-Wunsch
α: Kosten für Lückenöffnung, β: Kosten für Lückenerweiterung.
Needleman-Wunsch funktioniert nicht direkt, da affine Gap-Kosten drei Matrizen erfordern.
Erläutern Sie, warum das Divide-and-Conquer Verfahren für paarweises Sequenzalignment nur linearen Speicherbedarf hat.
Speicherbedarf sinkt auf O(n), da nur zwei Zeilen der Matrix gespeichert werden. Vorwärts- und Rückwärtspass reduzieren Speicher, aber Zeit bleibt O(mn).
Erläutern Sie, wie sich die Zeitkomplexität im Vergleich zum Needleman-Wunsch Algorithmus (O(nm) verändert.
Zeit bleibt O(mn), da die Berechnungen gleich bleiben. Speicher sinkt auf O(n + m), weil nur zwei Zeilen gleichzeitig benötigt werden.
Erläutern Sie, mit eigenen Worten, warum eine Erweiterung des Needleman-Wunsch Algorithmus (dynamische Programmierung) zur Berechnung multipler Sequenzalignments nicht effizient ist.
Needleman-Wunsch skaliert mit O(n^k) für k Sequenzen, was exponentiell ist. Speicherkosten steigen drastisch, da eine k-dimensionale Matrix benötigt wird.
Erläutern Sie die Laufzeit- und Speicherplatzkomplexität der Center-Star Approximation. Unterscheiden Sie dabei zuerst die einzelnen Phasen und erklären dann das Gesamtergebnis
Laufzeit: O(k²n²), da alle k Sequenzen paarweise verglichen werden. Speicher: O(n²), da pro Paar nur eine Matrix gespeichert wird.
Optimalität von multiplen Alignments
Center-Star ist nur eine Approximation, keine optimale Lösung. Paarweise Alignments sind nicht immer optimal, da sie nicht im Kontext aller Sequenzen optimiert werden.
Progressives Alignment & Problem
Sequenzen werden schrittweise ausgerichtet, basierend auf Ähnlichkeit. Fehler in frühen Schritten sind nicht korrigierbar und beeinflussen spätere Alignments.
E-Wert Bedeutung
Niedriger E-Wert = hohe Signifikanz des Treffers. Hohe E-Werte normal bei kurzen Sequenzen, da zufällige Matches wahrscheinlicher sind.
k-profil(x, k) und 18. k-distance(x, y, k)
Nutze Dictionary/Hashmap, um K-mers und ihre Häufigkeiten effizient zu speichern. K-Distanz: Vergleiche Häufigkeitsvektoren der Sequenzen.
Maximale Anzahl Kanten im Suffixbaum
Ein Suffix Baum hat:
- Blätter: Genau n, da jedes Suffix ein Blatt darstellt.
- Innere Knoten: Jeder innere Knoten repräsentiert ein gemeinsames Präfix von mindestens zwei Suffixen. Die maximale Anzahl innerer Knoten beträgt n−1, da jeder innere Knoten mindestens zwei Kinder haben muss.
-Baumeigenschaft: Ein Baum mit mmm Knoten hat immer m – 1 Kanten. Der Suffix Baum hat n Blätter und höchstens n−1 innere Knoten, also maximal 2n – 1 Knoten insgesamt.
3. Die maximale Anzahl an Kanten ergibt sich aus:
Kanten = (Anzahl Blätter) + (Anzahl innerer Knoten) −1
= 𝒏 + (𝒏 − 𝟏) − 𝟏 = 𝟐𝒏 – 𝟐
Begründung der n - 1 inneren Knoten: Jeder innere Knoten ist der Startpunkt eines neuen Teilbaums. Da jedes Suffix mit einem anderen Suffix nur an einer bestimmten Position übereinstimmen kann, gibt es höchstens n−1n−1 solcher inneren Knoten.
Fazit: Die Anzahl der Kanten in einem Suffix Baum ist also durch 2n – 2 beschränkt.
Anwendungen von Suffixbäumen
Wiederholungssuche: Identifikation von Tandem-Repeats, z. B. Huntington-Krankheit.
Genomische Duplikationen: Analyse evolutionärer Konservierung.
Laufzeit der Suffixbaum-Konstruktion
Mit Ukkonen-Algorithmus O(n), naiver Ansatz O(n²).
Algorithmus: Längstes häufigstes Teilwort im Suffixbaum
1.Konstruiere Suffixbaum (O(n)).
2.Zähle Häufigkeiten durch DFS (O(n)).
3.Finde längstes häufigstes Teilwort (O(n)). Gesamt: O(n).
Suffix-Array vs. Suffixbaum
Direkte Konstruktion: O(n log n) (z. B. mit SA-IS).
Suffixbaum → Suffix-Array: O(n).
Problem: Längstes gemeinsames Substring ist mit Suffixbaum effizienter.
Burrows-Wheeler-Transformation
BWT ist bijektiv, da sie mit LF-Mapping umkehrbar ist.
