View
218
Download
0
Category
Preview:
Citation preview
MCMC genome rearrangement
SE Aktuelle Themen der BioInformatikAndré Brück (2579542)
04/26/23 André Brück - MCMC genome rearrangement
2/80
Gliederung
• Einführung• Grundlagen
• Miklós – „MCMC genome rearrangement“• Ausblick
• Fragen / Diskussion
04/26/23 André Brück - MCMC genome rearrangement
3/80
EinführungWorum geht es?
Abschätzung evolutionärer Abstände
mittels Zählen der benötigten Mutationen
•„reversals“
•„signed permutations“
04/26/23 André Brück - MCMC genome rearrangement
4/80
Einführung
• Wie viele Mutationen benötigt man, um aus einem Grünkohl eine Mohrrübe zu machen ???
• ...und wie viele um von der Mitochondrien – DNA eines Wurmes zu der humanen zu kommen ???
04/26/23 André Brück - MCMC genome rearrangement
5/80
Gliederung
• Einführung• Grundlagen
• Miklós – „MCMC genome rearrangement“• Ausblick
• Fragen / Diskussion
04/26/23 André Brück - MCMC genome rearrangement
6/80
Grundlagen• Permutation
1,5,3,4,2
• vorzeichen-behaftete Permutation
+1,-5,+3,+4,-2
Jede Zahl steht für eine bei beiden Individuen gleiche Abfolge der DNA-
Moleküle
04/26/23 André Brück - MCMC genome rearrangement
7/80
Grundlagen
Was ist ein „reversal“?
„Eine Inversion der Abfolge der Nukleotide einer DNA-Sequenz“
ACGATA -> ATAGCA
+1 -> -1
04/26/23 André Brück - MCMC genome rearrangement
8/80
Grundlagen
76315824 16847325
76315824
13675824
13675284
13674825
16374825
5 reversals
04/26/23 André Brück - MCMC genome rearrangement
9/80
Grundlagen 7
04/26/23 André Brück - MCMC genome rearrangement
10/80
Grundlagen 26
04/26/23 André Brück - MCMC genome rearrangement
11/80
Grundlagen„Reality – Desire – Diagram“ (+3,-2,-1,+4,-5)
Definieren wir als:
04/26/23 André Brück - MCMC genome rearrangement
12/80
Grundlagen„Reality-Diagram“ =
tatsächliches Vorkommen
„Desire-Diagram“ = „so soll´s sein“ bzw. „so war es einmal“
04/26/23 André Brück - MCMC genome rearrangement
13/80
Grundlagen
Koventionen:– „Reality“ wird auf den Kreis gezeichnet
(Lit.: „black edges“)
– „Desire“ als Kanten im Kreis(Lit.: „gray edges“)
– Pfeilrichtung immer - +
04/26/23 André Brück - MCMC genome rearrangement
14/80
Grundlagen
„Reality – Desire – Diagram“ für Beispiel R=(+3,-2,-1,+4,-5) und D=(+1,+2,+3,+4,+5)
04/26/23 André Brück - MCMC genome rearrangement
15/80
Grundlagen
„Reality – Desire - Diagram“
04/26/23 André Brück - MCMC genome rearrangement
16/80
Grundlagen„breakpoint – graph“
eine Abschätzung, wie viele „reversals“ mindestens benötigt werden
Grobe untere Schranke
04/26/23 André Brück - MCMC genome rearrangement
17/80
Grundlagen
Was ist ein „breakpoint“ ?Definition:
Wenn (x,y) in einem Graphen α vorliegt, in einem Graphen β aber weder (x,y) noch (-y,-x) vorkommen, so bezeichnet man (x,y) als „breakpoint“ von α in Bezug auf β.
Beispiel:(+3,-2,-1,+4,-5) (+1,+2,+3,+4,+5)(+3,-2) (-1,+4) sind „breakpoints“, (-2,-1) ist KEIN „breakpoint“
04/26/23 André Brück - MCMC genome rearrangement
18/80
Grundlagen
Warum sind „breakpoints“ wichtig, bzw. als Abschätzung geeignet?
Intuitiv: Wenn (x,y) ein „breakpoint“ ist, dann muss es eine Veränderung von α gegeben haben, um zu β zu kommen.
Anzahl der „breakpoints“ ≈ Anzahl der „reversals“
bβ(α) := # “breakpoints” von α in Bezug auf β
04/26/23 André Brück - MCMC genome rearrangement
19/80
Grundlagen
Beispiel: (3, 5, 8, 6, 4, 7, 9, 2, 1, 10, 11)
04/26/23 André Brück - MCMC genome rearrangement
20/80
Grundlagen
Genauere untere Schranke:(0,2,3,1,4,6,5,7,8) (0,1,2,3,4,5,6,7,8)
Ein „reversal“ kann maximal 2 „breakpoints“ löschen
(0,2,3,1,4,6,5,7,8) (0,2,3,1,4,5,6,7,8)
bβ(α) = 5 bβ(α) = 3dβ(α) ≥ bβ(α)/2
04/26/23 André Brück - MCMC genome rearrangement
21/80
Grundlagen
Kurze Zwischenzusammenfassung:
• „signed permutations“• „Reality-Desire-Diagrams“• „breakpoint-graph“
04/26/23 André Brück - MCMC genome rearrangement
22/80
Grundlagen
Was passiert, wenn ein „reversal“ im RD-
Diagramm vorkommt?
04/26/23 André Brück - MCMC genome rearrangement
23/80
Grundlagen
„Hürden“ und „Festungen“ (Hannenhalli & Pevzner 95)
04/26/23 André Brück - MCMC genome rearrangement
24/80
Grundlagen
04/26/23 André Brück - MCMC genome rearrangement
25/80
Grundlagen„Interleaving graph“ „RD-diagram“
04/26/23 André Brück - MCMC genome rearrangement
26/80
Grundlagen
Komponenten• Interleaving-Graph
gibt Komponenten zurück
• F ist „good“• A/E ist „bad“• B/C/D ist „good“
04/26/23 André Brück - MCMC genome rearrangement
27/80
Grundlagen
Definitionen nach Hannenhalli & Pevzner
Hurdle– Simple Hurdle:
» Wenn durch diese Hürde nicht zwei „schlechte“ Komponenten getrennt werden
– Super Hurdle:» Wenn bei einem reversal aus einer „guten“
Komponente eine Hürde wird
– Non-Hurdle:» Wenn bei einem reversal nur „gute“ Kreise entstehen
04/26/23 André Brück - MCMC genome rearrangement
28/80
Grundlagen
Definitionen(2)
FortressWenn das Diagramm
aus einer ungeraden Anzahl von Super-Hürden besteht.(hier 3 SH)
04/26/23 André Brück - MCMC genome rearrangement
29/80
Grundlagen
• A,C,D,F sind Hürden• A,C,D „simple H.“• F „super H.“
Methode:Man nimmt „formal“
einen Nachbarn raus.Definitionen ergeben
Klassifizierung
04/26/23 André Brück - MCMC genome rearrangement
30/80
Grundlagen
L +3 -3 +4 -4 -1 +1 -2 2 6 -6 5 -5 R
L -1 +1 -2 +2 -3 +3 -4 +4 -5 +5 -6 +6 R
(-3,-4,+1,+2,-6,-5)
04/26/23 André Brück - MCMC genome rearrangement
31/80
GrundlagenL
-3
+3
+4
-6
-5
+5
R
-4
+2
+6
-2+1
-1
Ziel
04/26/23 André Brück - MCMC genome rearrangement
32/80
Grundlagen
-3
+3
+5
+6
-6
+2
-5
-2+1
-1
+4
-4
L R
04/26/23 André Brück - MCMC genome rearrangement
33/80
Grundlagen
-3
+3
+5
+6
-6
+4
-5
-4-1
+1
+2
-2
L R
04/26/23 André Brück - MCMC genome rearrangement
34/80
Grundlagen
+1
-1+6
+4
-5
-4+3
-3
-2
+2
RL
-6
+5
3 Reversals
04/26/23 André Brück - MCMC genome rearrangement
35/80
Grundlagen
Reversal-TypenKind I: („safe reversal“)Divergente „reality edges“
werden invertiert.
Kind II: („Hurdle Merging“)
Zwei gegenüberliegende Hürden , falls die Anzahl der Hürden geradegerade ist.
04/26/23 André Brück - MCMC genome rearrangement
36/80
GrundlagenKind III: („Hurdle Cutting“)Zwei gegenüberliegende
Hürden, falls die Anzahl der Hürden ungeradeungerade ist.
Diese 3 Möglichkeiten decken alles ab:
- Gute Komponente- Schlechte Komponente
- Gerade Anzahl- Ungerade Anzahl
04/26/23 André Brück - MCMC genome rearrangement
37/80
GrundlagenAlgorithmus-SkizzeAlgorithmus-Skizzerepeat
if es gibt eine gute Komponente in RDβ(α)führe Kind I reversal durchelse if gerade Anzahl Hürdenführe Kind II reversal durchelse if ungerade Anzahl Hürden und min 1 Simple H.führe Kind III reversal durch else [fortress]Kind II reversal mit beliebigen Hürden
until α = β.
04/26/23 André Brück - MCMC genome rearrangement
38/80
Grundlagen
Laufzeit-Verhalten
Erstellen von RD O(n)Interleaving graph O(n2)Komponenten O(n)
--------------RDβ(α)(dynamisch) O(n2)
04/26/23 André Brück - MCMC genome rearrangement
39/80
Grundlagen
Laufzeit-Verhalten
Für einen reversal (2 edges) O(n2)Prüfen ob schlechte Komp.(RD) O(n2)Maximal n-mal O(n)
GesamtlaufzeitGesamtlaufzeit O(nO(n55))
04/26/23 André Brück - MCMC genome rearrangement
40/80
Grundlagen
Kurze Zwischenzusammenfassung:
• Interleaving Graph• Hürden & Festungen• Algorithmus mit O(n5)
04/26/23 André Brück - MCMC genome rearrangement
41/80
Gliederung
• Einführung• Grundlagen
• Miklós – „MCMC genome rearrangement“• Ausblick
• Fragen / Diskussion
04/26/23 André Brück - MCMC genome rearrangement
42/80
Miklós – „MCMC genome rearrangement“
• University of Oxford, 2003.• Greift mehrere Essays auf, die er
einfließen lässt:– Hannenhalli & Pevzner, 1999.– Blanchette et al., 1996.– Eriksen et al., 2001.– Geman & Geman, 1984.
04/26/23 André Brück - MCMC genome rearrangement
43/80
Miklós – „MCMC genome rearrangement“
Miklós teilt Mutationen in 3 Kategorien ein:– Inversions:
• Ein Teilabschnitt wird nur umgedreht– Transposition
• Ein Teilabschnitt wird an einer anderen Stelle lokalisiert
– Inverted Transposition• Inversion+Transposition
04/26/23 André Brück - MCMC genome rearrangement
44/80
Miklós – „MCMC genome rearrangement“
04/26/23 André Brück - MCMC genome rearrangement
45/80
Miklós – „MCMC genome rearrangement“
Zur Erinnerung:– 1 (inverted) Transposition kann mehrere
inversions ersetzen
– Beispiel vom Anfang
76315824 16847325
Inverted transposition 31567824
04/26/23 André Brück - MCMC genome rearrangement
46/80
Miklós – „MCMC genome rearrangement“
• Wie werden die Mutationen gewichtet?– In den meisten existierenden Algorithmen
werden alle Mutationen gleichgewichtet.(Gu et al, Kececioglu & Sankoff, etc)
– (fast) alle bisherigen Veröffentlichungen / Untersuchungen beruhen nur auf einem Typ.
(inversions: Larget et al, Sankoff & Blanchette)– Miklós führt stochastische Methode zur
Gewichtung ein
04/26/23 André Brück - MCMC genome rearrangement
47/80
Miklós – „MCMC genome rearrangement“
Stochastisches ModellMiklós nimmt eine
Gleichverteilung der Mutationstypen an (Poisson-Verteilung)
Hierbei wird λ als Rate α·t für inversions und β·t für inv. Transpos.
dargestellt.
04/26/23 André Brück - MCMC genome rearrangement
48/80
Miklós – „MCMC genome rearrangement“
Es gibt maximal...
2
1n
verschiedene Inversionen und
3
1n
verschiedene Transpositionen.
Inv. Transpositionen werden definiert als:n : Länge der Permutation
3
12n
04/26/23 André Brück - MCMC genome rearrangement
49/80
Miklós – „MCMC genome rearrangement“
• l ist die Summe aller Positionen an denen i Inversionen stattgefunden haben.
• m ist die Summe aller Positionen an denen j Transpositionen oder invertierte Transpositionen stattgefunden haben.
• li und mj sind die Summen aller Positionen, an denen Inversionen oder Transpositionen stattgefunden haben.
04/26/23 André Brück - MCMC genome rearrangement
50/80
Miklós – „MCMC genome rearrangement“
Da die Ereignisse als unabhängig angenommen werden, kann die Wahrscheinlichkeit der Ereignisse für einen Datensatz so dargestellt werden.
(multiplizieren der Einzelwahrscheinl.)
t t
04/26/23 André Brück - MCMC genome rearrangement
51/80
Miklós – „MCMC genome rearrangement“
Permutationen sind nicht kommutativ
Daraus ergibt sich die Wahrscheinlichkeit für einen Pfad
[(8) durch (9) geteilt]
04/26/23 André Brück - MCMC genome rearrangement
52/80
Miklós – „MCMC genome rearrangement“
• MCs likelihood wird mit dem Satz von Bayes bestimmt, wobei G1 und G2 zwei Genome sind, α und β die Parameter.
• Das t kann weggelassen werden, da Zeit und Rate nicht getrennt werden können.
04/26/23 André Brück - MCMC genome rearrangement
53/80
Miklós – „MCMC genome rearrangement“
ist die Wahrscheinlichkeit, dass G2 aus G1 entstanden ist, mit den Parametern α und β, wobei Traj(G1, G2) die Menge aller möglichen Pfade von G1 zu G2 angibt.
Dies kann so nicht berechnet werden!!!
,,| 12 GGP
04/26/23 André Brück - MCMC genome rearrangement
54/80
Miklós – „MCMC genome rearrangement“
Aber: interessiert uns auch nicht ;-)
Was wir wollen: Abschätzung α und βWir wollen nur die Rate der Mutationen,
bzw. die Anzahlen der verschiedenen Mutationen in Bezug auf einen Datensatz.
04/26/23 André Brück - MCMC genome rearrangement
55/80
Miklós – „MCMC genome rearrangement“
Zurück zu MCMC:Per Definition ist die „posterior distribution“ eines
MCMC Netzwerkes:
04/26/23 André Brück - MCMC genome rearrangement
56/80
Miklós – „MCMC genome rearrangement“
Dies wird mit den Formeln (10)-(12) eingesetzt zu:
04/26/23 André Brück - MCMC genome rearrangement
57/80
Miklós – „MCMC genome rearrangement“
wobei....
P(α) und P(β) sind die Eingangs-wahrscheinlichkeiten der Parameter α und β.
(Dichtefunktion über zwei Parameter)
04/26/23 André Brück - MCMC genome rearrangement
58/80
Miklós – „MCMC genome rearrangement“
Nun kann P(α, β |G1,G2) aus P( t, α, β) gesampelt werden.
Mittels einer niedrigen Eingangs-wahrscheinlichkeit für α und β und einem sehr hohem cut-off wird der Einfluss der a priori Verteilung minimiert.
04/26/23 André Brück - MCMC genome rearrangement
59/80
Miklós – „MCMC genome rearrangement“
Wir betrachten nur die folgende Näherung:
04/26/23 André Brück - MCMC genome rearrangement
60/80
Miklós – „MCMC genome rearrangement“
Wie bei Markoff-Ketten üblich wird eine Funktion erstellt, die uns angibt, ob wir den Pfad annehmen oder verwerfen:
Diese Berechnung heißt „Metropolis-Hastings ratio“
04/26/23 André Brück - MCMC genome rearrangement
61/80
Miklós – „MCMC genome rearrangement“
Grundidee für die „proposal distribution“:
1. Eine Mutation, die die Anzahl der Kreise erhöht, bekommt eine hohe Wahrscheinlichkeit
=> „Der Weg zum Ziel“
04/26/23 André Brück - MCMC genome rearrangement
62/80
Miklós – „MCMC genome rearrangement“
2. Eine Mutation, die die Anzahl der Kreise nicht verändert, bekommt eine niedrigere Wahrscheinlichkeit
=> „Die Natur nimmt „normalerweise“ den kürzesten Weg“
04/26/23 André Brück - MCMC genome rearrangement
63/80
Miklós – „MCMC genome rearrangement“
Folge daraus...
3. Eine Mutation, die die Anzahl der Kreise vermindert, bekommt die niedrigste Wahrscheinlichkeit.
04/26/23 André Brück - MCMC genome rearrangement
64/80
Miklós – „MCMC genome rearrangement“
Versuchen wir den Bogen zu den Grundlagen zu schlagen :
• Inversions / Transpositions verändern die „black edges“ => Reality-Linien (RD) (und ziehen die D-Edges mit)
• „Gut ist, was Kreise schafft...“• Hannenhalli & Pevzner:
– Ein reversal kann maximal 2 breakpoints löschen– Ein reversal kann maximal 1 Kreis neu erzeugen
04/26/23 André Brück - MCMC genome rearrangement
65/80
Miklós – „MCMC genome rearrangement“
Wie wird mit diesen Vorgaben ein neuer Pfad vorhergesagt?
1. Fange am Start an (Komponentenweise)2. Laufe den Weg auf den Desire-Edges durch den
Graphen und markiere die Kanten entsprechend ihrer Orientierung mit +1 oder -1
3. Wenn man mindestens 3 R-Edges überspannt, prüfe ob eine Transposition vorkommen kann und notiere alle Möglichkeiten.
4. Berechne Anzahl der Inversionen
04/26/23 André Brück - MCMC genome rearrangement
66/80
Miklós – „MCMC genome rearrangement“
Was wissen wir jetzt?
• Maximale Anzahl der Inversionen• Alle möglichen Transpositionen• Anzahl der Kreise / Komponenten
04/26/23 André Brück - MCMC genome rearrangement
67/80
Miklós – „MCMC genome rearrangement“
Jetzt kommt die „proposal distribution“ ins Spiel:
• Gibt es einen safe-Reversal: hohe Wahrscheinlichkeit
• Gibt es nicht: Gibt es eine Möglichkeit, safe-Reversals zu erzeugen?
• (Ist es schon die Ziel-Permutation?)• Alles andere: niedrige Wahrscheinlichkeiten
04/26/23 André Brück - MCMC genome rearrangement
68/80
Miklós – „MCMC genome rearrangement“
Die „proposal-distribution“ wurde von Miklós empirisch bestimmt.
04/26/23 André Brück - MCMC genome rearrangement
69/80
Miklós – „MCMC genome rearrangement“
Kurze Wiederholung:• Miklós nutzt die MCMC Methode um die Raten α
und β zu berechnen• Dazu hat er eine Verteilung empirisch bestimmt
(proposal distribution)• Sein Algorithmus läuft über alle Reality-Kanten
des RD-Diagrammes und berechnet in jedem Zyklus alle möglichen Mutationen und gewichtet sie mittels seiner Wahrscheinlichkeitswerte.
04/26/23 André Brück - MCMC genome rearrangement
70/80
Miklós – „MCMC genome rearrangement“
Ergebnis auf simulierten Daten:
• 5 inversions / 5 Transpositions / n = 50• Ein run (Sample / MIS) benötigte ca. 3
Stunden auf 1.5 GHz Rechner.• In allen Fällen wurden mehr Mutationen
vorhergesagt, wie simuliert.
04/26/23 André Brück - MCMC genome rearrangement
71/80
Miklós – „MCMC genome rearrangement“
Auffällig ist, dass wenn keine Inversionen / Transpositionen vorhanden waren, trotzdem welche gefunden wurden
(„Problem mit Wahrscheinlichkeiten“)
04/26/23 André Brück - MCMC genome rearrangement
72/80
Miklós – „MCMC genome rearrangement“
Test auf reelen Daten gegen DERANGE2Humane / Drosophila mitochondrialer DNADERANGE2
– unterteilt nur in gute / schlechte Mutation -> manche Pfade können nie begangen werden
– Blanchette et al. (1996)
04/26/23 André Brück - MCMC genome rearrangement
73/80
Miklós – „MCMC genome rearrangement“
Miklós• 6.76 ± 3.32
Inversionen• 6.80 ± 1.12
TranspositionenMit angepassten Gewichten:
2 Inversions + 9 Transpositions = 11 Mutationen
DERANGE2• Findet minimal 12
Mutationen, davon 3 Transpositionen
• Bei leichter Veränderung der Gewichte 16 / 3
04/26/23 André Brück - MCMC genome rearrangement
74/80
Miklós – „MCMC genome rearrangement“
Bewertung von Miklós MCMC Ansatz:Sein Algorithmus kann bessere Werte
erzielen, wenn die proposal distribution sinnvoll gewählt ist.
Er findet mehr Transpositionen und weniger Inversionen als vorhanden sind.
04/26/23 André Brück - MCMC genome rearrangement
75/80
Miklós – „MCMC genome rearrangement“
• Zwei Zitate:
– „a better implementation of the approach might improve both the theoretical time complexity and the running time in practice“
– „The proposed auxiliary distribution in the MIS step is far from the optimal“
04/26/23 André Brück - MCMC genome rearrangement
76/80
Gliederung
• Einführung• Grundlagen
• Miklós – „MCMC genome rearrangement“• Ausblick
• Fragen / Diskussion
04/26/23 André Brück - MCMC genome rearrangement
77/80
Ausblick
Weiterentwicklung von Algorithmus mit besserer Laufzeit
Bessere „proposal distribution“, die nicht empirisch bestimmt ist, sondern die den Daten (allen Daten) mehr entspricht
=> Bessere & schnellere Ergebnisse
04/26/23 André Brück - MCMC genome rearrangement
78/80
Gliederung
• Einführung• Grundlagen
• Miklós – „MCMC genome rearrangement“• Ausblick
• Fragen / Diskussion
04/26/23 André Brück - MCMC genome rearrangement
79/80
Fragen / Diskussion
Danke für Eure Aufmerksamkeit !!!
Recommended