MCMC genome rearrangement SE Aktuelle Themen der BioInformatik André Brück (2579542)

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


3/80

EinführungWorum geht es?

Abschätzung evolutionärer Abstände

mittels Zählen der benötigten Mutationen

•„reversals“

•„signed permutations“


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


5/80

Gliederung





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


7/80

Grundlagen

Was ist ein „reversal“?

„Eine Inversion der Abfolge der Nukleotide einer DNA-Sequenz“

ACGATA -> ATAGCA

+1 -> -1


8/80

Grundlagen

76315824 16847325

76315824

13675824

13675284

13674825

16374825

5 reversals


9/80

Grundlagen 7


10/80

Grundlagen 26


11/80

Grundlagen„Reality – Desire – Diagram“ (+3,-2,-1,+4,-5)

Definieren wir als:


12/80

Grundlagen„Reality-Diagram“ =

tatsächliches Vorkommen

„Desire-Diagram“ = „so soll´s sein“ bzw. „so war es einmal“


13/80

Grundlagen

Koventionen:– „Reality“ wird auf den Kreis gezeichnet

(Lit.: „black edges“)

– „Desire“ als Kanten im Kreis(Lit.: „gray edges“)

– Pfeilrichtung immer - +


14/80

Grundlagen

„Reality – Desire – Diagram“ für Beispiel R=(+3,-2,-1,+4,-5) und D=(+1,+2,+3,+4,+5)


15/80

Grundlagen

„Reality – Desire - Diagram“


16/80

Grundlagen„breakpoint – graph“

eine Abschätzung, wie viele „reversals“ mindestens benötigt werden

Grobe untere Schranke


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“


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 β


19/80

Grundlagen

Beispiel: (3, 5, 8, 6, 4, 7, 9, 2, 1, 10, 11)


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


21/80

Grundlagen

Kurze Zwischenzusammenfassung:

• „signed permutations“• „Reality-Desire-Diagrams“• „breakpoint-graph“


22/80

Grundlagen

Was passiert, wenn ein „reversal“ im RD-

Diagramm vorkommt?


23/80

Grundlagen

„Hürden“ und „Festungen“ (Hannenhalli & Pevzner 95)


24/80

Grundlagen


25/80

Grundlagen„Interleaving graph“ „RD-diagram“


26/80

Grundlagen

Komponenten• Interleaving-Graph

gibt Komponenten zurück

• F ist „good“• A/E ist „bad“• B/C/D ist „good“


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


28/80

Grundlagen

Definitionen(2)

FortressWenn das Diagramm

aus einer ungeraden Anzahl von Super-Hürden besteht.(hier 3 SH)


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


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)


31/80

GrundlagenL

-3

+3

+4

-6

-5

+5

R

-4

+2

+6

-2+1

-1

Ziel


32/80

Grundlagen

-3

+3

+5

+6

-6

+2

-5

-2+1

-1

+4

-4

L R


33/80

Grundlagen

-3

+3

+5

+6

-6

+4

-5

-4-1

+1

+2

-2

L R


34/80

Grundlagen

+1

-1+6

+4

-5

-4+3

-3

-2

+2

RL

-6

+5

3 Reversals


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.


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


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 α = β.


38/80

Grundlagen

Laufzeit-Verhalten

Erstellen von RD O(n)Interleaving graph O(n2)Komponenten O(n)

--------------RDβ(α)(dynamisch) O(n2)


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


40/80

Grundlagen

Kurze Zwischenzusammenfassung:

• Interleaving Graph• Hürden & Festungen• Algorithmus mit O(n5)


41/80

Gliederung





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.


43/80


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


44/80



45/80


Zur Erinnerung:– 1 (inverted) Transposition kann mehrere

inversions ersetzen

– Beispiel vom Anfang

76315824 16847325

Inverted transposition 31567824


46/80


• 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


47/80


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.


48/80


Es gibt maximal...

2

1n

verschiedene Inversionen und

3

1n

verschiedene Transpositionen.

Inv. Transpositionen werden definiert als:n : Länge der Permutation

3

12n


49/80


• 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.


50/80


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


51/80


Permutationen sind nicht kommutativ

Daraus ergibt sich die Wahrscheinlichkeit für einen Pfad

[(8) durch (9) geteilt]


52/80


• 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.


53/80


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


54/80


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.


55/80


Zurück zu MCMC:Per Definition ist die „posterior distribution“ eines

MCMC Netzwerkes:


56/80


Dies wird mit den Formeln (10)-(12) eingesetzt zu:


57/80


wobei....

P(α) und P(β) sind die Eingangs-wahrscheinlichkeiten der Parameter α und β.

(Dichtefunktion über zwei Parameter)


58/80


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.


59/80


Wir betrachten nur die folgende Näherung:


60/80


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“


61/80


Grundidee für die „proposal distribution“:

1. Eine Mutation, die die Anzahl der Kreise erhöht, bekommt eine hohe Wahrscheinlichkeit

=> „Der Weg zum Ziel“


62/80


2. Eine Mutation, die die Anzahl der Kreise nicht verändert, bekommt eine niedrigere Wahrscheinlichkeit

=> „Die Natur nimmt „normalerweise“ den kürzesten Weg“


63/80


Folge daraus...

3. Eine Mutation, die die Anzahl der Kreise vermindert, bekommt die niedrigste Wahrscheinlichkeit.


64/80


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


65/80


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


66/80


Was wissen wir jetzt?

• Maximale Anzahl der Inversionen• Alle möglichen Transpositionen• Anzahl der Kreise / Komponenten


67/80


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


68/80


Die „proposal-distribution“ wurde von Miklós empirisch bestimmt.


69/80


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.


70/80


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.


71/80


Auffällig ist, dass wenn keine Inversionen / Transpositionen vorhanden waren, trotzdem welche gefunden wurden

(„Problem mit Wahrscheinlichkeiten“)


72/80


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)


73/80


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


74/80


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.


75/80


• 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“


76/80

Gliederung





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


78/80

Gliederung





79/80

Fragen / Diskussion

Danke für Eure Aufmerksamkeit !!!

Documents

MCMC genome rearrangement SE Aktuelle Themen der BioInformatik André Brück (2579542)