Was ist das Ziel der Assemblierung? (Slide 2)
- Rekonstruktion des ursprünglichen Genoms aus ungeordneten Reads / - Zusammensetzen von Sequenzen zu möglichst vollständigem Genom / - Wird als „Puzzlespiel“ beschrieben
Welche zwei Methoden der Assemblierung gibt es? (Slide 2)
- De Novo Assembly (ohne Referenz) / - Assembly mit Referenz (Referenz-basiert)
Was versteht man unter Contigs und Scaffolds? (Slide 3)
- Contigs: aneinandergereihte Reads zu größeren Sequenzen / - Scaffolds: mehrere Contigs, die als Gerüst das Genom abbilden / - Lassen Lücken, bilden nicht das gesamte Chromosom ab
Wie läuft eine Genom-Assemblierung ab? (Slide 4)
- 1️⃣ Qualitätskontrolle der Reads / - 2️⃣ Suche nach Überlappungen zwischen Reads / - 3️⃣ Bildung von Contigs / - 4️⃣ Scaffolding zur Erzeugung längerer Sequenzen
Was bedeutet „Read Quality Control“? (Slide 5)
- Bewertung der Lesegenauigkeit jedes Nukleotids / - Bestimmung der Fehlerwahrscheinlichkeit P / - Phred-Score Q = −10 × log₁₀(P) bedeutet: je kleiner die Fehlerwahrscheinlichkeit, desto größer der Qualitätswert
Wie interpretiert man die Formel Q = −10 × log₁₀(P)? (Slide 5)
- Q ist der Phred-Score / - P ist die Wahrscheinlichkeit, dass eine Base falsch ist / - Wenn P = 0.01 → Q = 20 (Fehlerwahrscheinlichkeit 1 %) / - Wenn P = 0.001 → Q = 30 (Fehlerwahrscheinlichkeit 0.1 %) / - Ein um 10 höherer Score bedeutet 10× geringere Fehlerwahrscheinlichkeit
Was ist eine FASTQ-Datei? (Slide 6)
- Textdatei mit allen Reads / - Jeder Eintrag besteht aus Sequence-Identifier (@), Sequenz und Phred-Score / - Enthält Qualitätsbewertung pro Base
Wie sind FASTQ-Dateien strukturiert? (Slide 6)
- Zeile 1: @Identifier / - Zeile 2: DNA-Sequenz / - Zeile 3: + (optionale Zusatzinfos) / - Zeile 4: Phred-Score-Zeichenfolge (eine Position = eine Base)
Wie werden Phred-Scores in ASCII kodiert? (Slide 7)
- ASCII-Zeichen 33–126 entsprechen Werten 0–93 / - z. B. Zeichen „!“ steht für 0, „A“ für 32, „~“ für 93 / - Seltener > 60 (P ≈ 1 : 1 Million)
Was sind typische Read-Datenbeispiele? (Slide 8)
- Bakterium *Aliivibrio wodanis*: 4.972.754 bp, 200× Illumina Reads (760 MB) / - *Caenorhabditis elegans*: 100.272.607 bp, 80× PacBio Reads (7,6 GB)
Was ist der Assembly-Bottleneck? (Slide 9)
- Bestimmung aller Präfix-Suffix-Überlappungen zwischen Reads / - Jeder Vergleich erfordert ggf. ein Alignment (Fehlererkennung) / - Extrem rechenintensiv bei großen Datenmengen
Warum benötigt man Indizierung und Kompression bei der Assemblierung? (Slide 10)
- Um Überlappungen schneller zu finden / - Um den Speicherverbrauch zu reduzieren / - Damit Millionen Reads effizient verarbeitet werden können
Was ist der FM-Index? (Slide 11)
- Komprimierter Index für Textsuche / - Kombination aus Burrows-Wheeler-Transformation (BWT) und Zusatzstrukturen / - Ermöglicht schnelle Suffix- und Pattern-Suchen bei minimalem Speicherbedarf
Welche Vorteile bietet der FM-Index für Genomdaten? (Slide 11)
- Schnelle Suchen nach Teilsequenzen / - Kompakt, speichereffizient / - Besonders nützlich für DNA mit nur vier Symbolen (A,C,G,T)
Was ist ein Suffix Array? (Slide 12)
- Enthält alle Suffixe eines Strings T[1..u], alphabetisch sortiert / - Speichert Startpositionen statt ganzer Suffixe / - Speicherbedarf ≈ u × log₂(u) Bits
Was leistet die Burrows-Wheeler-Transformation (BWT)? (Slide 13)
- Nimmt Eingabestring T und hängt ein Endsymbol # an / - Bildet alle Permutationen von T# und sortiert sie lexikographisch / - Die letzte Spalte L ist die BWT von T / - So werden gleiche Zeichen gruppiert → bessere Kompression
Was ist die Komplexität der BWT? (Slide 13)
- Zeitkomplexität O(u), wobei u die Länge des Textes ist / - Bedeutet: Aufwand wächst linear mit der Textlänge / - Daher effizient auch für große Genome
Wie wird die originale Sequenz aus der BWT rekonstruiert? (Slide 14)
- Durch „Last-to-First“-Mapping (LF-Mapping) / - Beginne mit T[u] = L[1] (weil die erste Zeile #T enthält) / - Danach rekonstruiert man rückwärts jedes Zeichen bis T[1] / - C(c) zählt, wie viele Buchstaben kleiner als c sind / - Occ(c,i) zählt, wie oft c bis Position i in L vorkommt
Wie funktioniert LF-Mapping? (Slide 14)
- Formel: LF(i) = C(c) + Occ(c,i) / - C(c): Anzahl aller Buchstaben im Text, die im Alphabet vor c stehen / - Occ(c,i): Häufigkeit von c in der letzten Spalte L bis Position i / - Ergebnis: Position des vorherigen Zeichens im Originaltext / - So „springt“ man durch das BWT-Array zurück zur Originalreihenfolge
Warum funktioniert die Rücktransformation der BWT? (Slide 16)
- Jede Zeile ist eine Permutation des Texts T / - Letzter Buchstabe einer Zeile steht im Original direkt vor dem ersten / - LF-Mapping rekonstruiert dadurch Buchstabe für Buchstabe rückwärts / - So kann T ohne Verlust vollständig wiederhergestellt werden
Was ist Move-to-Front-Kompression (MTF)? (Slide 17)
- Kodiert Zeichen durch ihre Position in einer dynamischen Liste l / - Nach jedem Zeichen wird l so umgeordnet, dass das Zeichen vorne steht / - Häufige Zeichen bekommen dadurch niedrige Zahlenwerte
Wie funktioniert Move-to-Front im Prinzip? (Slide 17)
- Beispiel: s = "bananaaa" und l = "abcdef...z" / - Jedes Zeichen c → gib seine aktuelle Position in l aus und verschiebe c nach vorne / - Ergebnis ist eine Zahlenfolge (Positionen) statt Buchstaben / - Erleichtert anschließende Kompression
Wie wird durch Move-to-Front Kompression erzielt? (Slide 18)
- Wiederholte Zeichen ergeben kleine Zahlen (meist 1 oder 0) / - Kleine Zahlen brauchen weniger Speicher / - BWT gruppiert gleiche Zeichen → MTF erzeugt viele kleine Zahlen / - Grundlage für Run-Length-Encoding
Wie funktioniert die Dekompression von Move-to-Front-Daten? (Slide 19)
- Gegeben ist die Positionsliste o und eine alphabetische Startliste l / - Für jede Position p: nimm l[p] und füge sie zu s hinzu / - Dann verschiebe l[p] an den Anfang / - Das rekonstruiert die ursprüngliche Zeichenfolge schrittweise
Wie wird die BWT komprimiert? (Slide 20)
- 1️⃣ MTF-Encoding wandelt Buchstaben in Positionen / - 2️⃣ Run-Length-Encoding ersetzt Folgen gleicher Werte (z. B. Nullen) durch Zählpaare / - 3️⃣ Optionale Huffman- oder arithmetische Kodierung, um Bitlängen weiter zu minimieren
Was sind Suffix Array-Eigenschaften bei BWT-Lookups? (Slide 21)
- Alle Suffixe, die mit einem Suchmuster P beginnen, liegen im Array nebeneinander / - Diese Positionen liegen zwischen sp (Start) und ep (Ende) / - Dadurch kann man alle Treffer effizient aufspüren
Wie wird ein Pattern P in der BWT gesucht? (Slide 22)
- Man sucht rückwärts von P[p] bis P[1] / - sp und ep werden über C(c) und Occ(c, i) aktualisiert: sp = C(c) + Occ(c, sp−1) + 1 und ep = C(c) + Occ(c, ep) / - Ergebnis: Bereich [sp, ep] enthält alle Vorkommen von P
Wie interpretiert man die Formel sp = C(c) + Occ(c, sp−1) + 1 ? (Slide 22)
- C(c) = lexikographische Position des Zeichens c im sortierten Alphabet / - Occ(c, sp−1) = wie oft c bis sp−1 in L vorkommt / - Die Summe zeigt, ab wo das neue Präfix cP im Array zu finden ist
Warum werden sp und ep über C[c] + Occ[…] berechnet? (Slide 23)
- C(c) liefert die Basisposition für das Zeichen c / - Occ(c,i) verschiebt diesen Bereich entsprechend der bisherigen Treffer / - Damit wird das Suchintervall bei jedem Präfix präzise eingegrenzt
Wie findet man die Positionen von Pattern-Vorkommen in T? (Slide 24)
- Markiere einige Zeilen der BWT-Matrix mit ihren Originalpositionen / - Für s ∈ [sp, ep]: Wenn Zeile markiert → Position direkt ausgeben / - Sonst: LF-Mapping rückwärts ausführen, bis markierte Zeile erreicht ist / - Ergebnis: Startposition des Musters im Originaltext
Wer entwickelte den FM-Index? (Slide 25)
- Paolo Ferragina und Giovanni Manzini (2000) / - Veröffentlichung: „Opportunistic Data Structures with Applications“ / - Grundlage aller modernen FM-Index-Implementierungen / - Wichtige Basis für Bioinformatik-Tools wie Bowtie oder BWA
Zuletzt geändertvor 2 Monaten