02-Genome Assembly

- Rekonstruktion des ursprünglichen Genoms aus ungeordneten Reads / - Zusammensetzen von Sequenzen zu möglichst vollständigem Genom / - Wird als „Puzzlespiel“ beschrieben

- De Novo Assembly (ohne Referenz) / - Assembly mit Referenz (Referenz-basiert)

- 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

- 1️⃣ Qualitätskontrolle der Reads / - 2️⃣ Suche nach Überlappungen zwischen Reads / - 3️⃣ Bildung von Contigs / - 4️⃣ Scaffolding zur Erzeugung längerer Sequenzen

- 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

- 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

- Textdatei mit allen Reads / - Jeder Eintrag besteht aus Sequence-Identifier (@), Sequenz und Phred-Score / - Enthält Qualitätsbewertung pro Base

- Zeile 1: @Identifier / - Zeile 2: DNA-Sequenz / - Zeile 3: + (optionale Zusatzinfos) / - Zeile 4: Phred-Score-Zeichenfolge (eine Position = eine Base)

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

- Bakterium *Aliivibrio wodanis*: 4.972.754 bp, 200× Illumina Reads (760 MB) / - *Caenorhabditis elegans*: 100.272.607 bp, 80× PacBio Reads (7,6 GB)

- Bestimmung aller Präfix-Suffix-Überlappungen zwischen Reads / - Jeder Vergleich erfordert ggf. ein Alignment (Fehlererkennung) / - Extrem rechenintensiv bei großen Datenmengen

- Um Überlappungen schneller zu finden / - Um den Speicherverbrauch zu reduzieren / - Damit Millionen Reads effizient verarbeitet werden können

- Komprimierter Index für Textsuche / - Kombination aus Burrows-Wheeler-Transformation (BWT) und Zusatzstrukturen / - Ermöglicht schnelle Suffix- und Pattern-Suchen bei minimalem Speicherbedarf

- Schnelle Suchen nach Teilsequenzen / - Kompakt, speichereffizient / - Besonders nützlich für DNA mit nur vier Symbolen (A,C,G,T)

- Enthält alle Suffixe eines Strings T[1..u], alphabetisch sortiert / - Speichert Startpositionen statt ganzer Suffixe / - Speicherbedarf ≈ u × log₂(u) Bits

- 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

- 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

- 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

- 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

- 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

- 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

- 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

- 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

- 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

- 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

- 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

- 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

- 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

- 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

- 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

- 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