Genomátrendeződések Miklós István Rényi Intézet, összintézeti szeminárium, 2006. március 13.
A mai előadás • Genomátrendeződések biológiai jelentősége Filogenetikai elemzések Genomátrendeződés rákos sejtekben • Matematikai modellek Előjeles permutációk és rajtuk ható mutációk Valóság és kívánalom gráfja, graph of desire and reality • Parszimónia módszerek Hannenhalli-Pevzner elmélet inverziókra (reverzálokra) Approximációk más esetekre Összes optimális reverziós útvonal megkeresése • Statisztikus módszerek MCMC, Sztochasztikus optimalizálás Bayes statisztika Központi kérdés: Markov láncok konvergenciája • Analitikus megoldások
Humán – egér összehasonlítás
Humán – egér összehasonlítás
Probléma: az két vonalon az mutációk akkumlálásának a sebessége nem biztos, hogy azonos volt!
Többszörös genomátrendeződések Humán, egér és patkány genomok összehasonlítása
Folytatás
Egér, patkány: 3.2 – 3.5 átrendeződés / millió év Humán ágon 1.6 átrendeződés / millió év
Sok genom bevonásával még pontosabb képet kapunk
Genomátrendeződés az immunrendszerben JH
JH 1
JH 2
JH 2 DH
JH
4
nonamer
12 bp heptamer
C C A A A C A C A G T G A C A C
C A C T G T G
DH
3
9-77-9
RAG
23 bp D-J
kapcsolódás
D D H H D D D H 1 H2 H 3
JH
4
kivágás
G G T T T T T G T
1
J J J H H5 H 6 4
1
D --J J J H H H H 2
3
4
5
6
3
Génátrendeződés tumor genomokban mFISH • Minden szín egy kromoszóma egészséges genomban • Többszínű kromoszóma az ábrán: átrendezett • Alacsony felbontás, pontos térkép nem állapítható meg
Szekvenálással a kép pontosítható (ESP technológia)
Geneológia ESP a tumor számos fázisában és áttételében
Mi az ősi genom, amely a rákosodási folyamatot kiváltotta? • Gyógyszer • Prevenció
A mai előadás • Genomátrendeződések biológiai jelentősége Filogenetikai elemzések Genomátrendeződés rákos sejtekben • Matematikai modellek Előjeles permutációk és rajtuk ható mutációk Valóság és kívánalom gráfja, graph of desire and reality • Parszimónia módszerek Hannenhalli-Pevzner elmélet inverziókra (reverzálokra) Approximációk más esetekre Összes optimális reverziós útvonal megkeresése • Statisztikus módszerek MCMC, Sztochasztikus optimalizálás Bayes statisztika Központi kérdés: Markov láncok konvergenciája • Analitikus megoldások
Genomátrendező mutációk Inversions
...π iπ i +1 ...π jπ j +1 ...
π i − π j ... − π i +1π j +1
→
Transpositions ...π iπ i +1...π jπ j +1 ...π kπ k +1 ... → ...π iπ k ...π j +1π i +1 ...π jπ k +1 ...
Inverted Transpositions ...π iπ i +1...π jπ j +1 ...π kπ k +1 ... → ...π i − π k ... − π j +1π i +1 ...π jπ k +1 ...
Translocations
...π iπ i +1...π jπ j +1 ...
→
ρ kπ i +1...π j ρ k +1
Valóság és kívánalom gráfja Reality L
3
2
1
4 3
2
2
3
4
R
5
Desire edges 0
Reality edges
Desire L
5
1
6
1
7 8
10 9
4
5
11
R
Based on basic group theory, transforming π 1 to π 2 is equivalent with −1 transforming π 2 π 1 to the identical permutation. The graph of desire and reality of the identical permutation is n+1 cycle, all other permutations have less cycles:
0
1
2
3 4
5
6
7
8
9 10
11
Cirkuláris és lineáris permutációk Egy n hosszú cirkuláris permutáció modellezhető egy n-1 hosszú lineáris permutációval +6
+7
-4
+8 +1
+5
+2
+4
+6
-5
+5
-7 +5
+2
+4 +3
+2
-6
+8 +1
+8 +1
+3 +7
-3
+8 +1
+4
+2
+3 +7
+6
A mai előadás • Genomátrendeződések biológiai jelentősége Filogenetikai elemzések Genomátrendeződés rákos sejtekben • Matematikai modellek Előjeles permutációk és rajtuk ható mutációk Valóság és kívánalom gráfja, graph of desire and reality • Parszimónia módszerek Hannenhalli-Pevzner elmélet inverziókra (reverzálokra) Approximációk más esetekre Összes optimális reverziós útvonal megkeresése • Statisztikus módszerek MCMC, Sztochasztikus optimalizálás Bayes statisztika Központi kérdés: Markov láncok konvergenciája • Analitikus megoldások
Hannenhalli-Pevzner elmélet Megadja a minimálisan szükséges inverziók (reverzálok) számát, amely egy előjeles permutáció rendezéséhez kell. • Hannenhalli-Pevzner (1995): O(n4) algoritmus • Kaplan, Shamir, Tarjan, (1997) O(n2) algoritmus • Bader, Moret, Yan (2001) O(n) algoritmus, csak a távolságot adja meg, útvonalat nem ad. • Carpara (1997) Ha a permutáció nem előjeles, a probléma NP-teljes!
Alsó becslés az inverziós távolságra A körök számát a valóság és kívánalom gráfjában egy iverzió maximum eggyel növeli, így
d (π ) ≥ n + 1 − c(π ) a
b
c
d
a
c
b
d
a
b
c
d
a
c
b
d
”Problémás” permutációk Az alábbi permutációban nem lehet a körök számát növelni egy lépésben:
0
9
10 5 +5
6 +3
3
4 +2
1
2 +1
7
8 11 +4
Szükséges definíciók Egy kivánalom él irányított, ha a körön tett sétán a két szomszédos valóság élen ellenkező irányba megyünk Két kívánalom él metszi egymást, ha a végpontjaik által megadott intervallumok metszik egymást. A metszési gráf pontjai a valóság és kivánalom gráf nem triviáslis körein található kívánalom élek, két pont a metszési gráfon akkor van összekötve, ha a két kívánalom él metszi egymást. A metszési gráf egy komponense irányított komponens, ha van irányított kívánalom éle, egyébként a komponens irányítatlan. Egy irányítatlan komponens védett nem-gát, ha van két irányítatlan komponens, amelyeket elválaszt, azaz az egyik komponens „alatta”, a másik pedig „felette”, vagy rajta kívül van a valóság és kívánalom gráfban.
Szükséges definíciók, folytatás Egy irányítatlan komponens gát, ha nem védett nem-gát Egy gát szupergát, ha van olyan védett nem-gát, amely ezen gát nélkül maga is gát lenne (azaz a védett nem-gát egyik felén a szupergát az egyetlen irányítatlan komponens)
Egy permutáció erőd, ha minden gátja szupergát, és ezek száma páratlan
Példa: egy legkisebb erőd Egy erőd legalább három szupergátat tartalmaz
A legkisebb irányítatlan komponens három valóságélt tartalmaz
A Hannenhalli-Pevzner tétel d (π ) = n + 1 − c(π ) + h(π ) + f (π ) ahol • d(π) a π előjeles permutáció reverziós távolsága (az identikus permutációtól) • n a π előjeles permutáció hossza • c(π) a körök száma a valóság és kívánalom gráfban • h(π) a gátak (hurdle) száma • f(π) pedig 1, ha π erőd (fortress), egyébként 0.
Biztonságos (safe) körnövelő reverzálok Egy körök számát növelő reverzál biztonságos, ha nem hoz létre új irányítatlan komponenst. Nem minden körnövelő reversal biztonságos 0
8
7
4
3
12 11
6
5
2 1
9 10
13
0
1
2
5
6
11 12
3
4
7 8
9 10
13
Lemma: Minden irányított komponensre létezik körnövelő biztonságos reversal
A lemma folyománya Gátmentes permutációkra
d (π ) = n + 1 − c(π ) hiszen biztonságos körnövelő reverzálokkal rendezhető
Gátkötés Egy inverzió két gátat összeköt, ha a két gát két végén levő valóságéleken hat Állítás: A gátkötés egy irányított komponenst hoz létre Állítás: Ha két nem szomszédos gátat kötünk össze (az első és az utolsó gátat is szomszédosnak tekintjük), akkor a gátak számát kettővel csökkentjük, míg a körök számát eggyel, ha a gátak száma páros, akkor nem hozunk létre erődöt
Gátvágás A gátvágás egy inverzió, amely egy gát egy körének két végén levő valóságéleken hat Állítás: a gátvágás a gátból egy irányított komponenst csinál A bizonyítás a következő állításokon keresztül: Állítás: Egy kör minden kívánaloméle egy komponensben van Állítás: A gátvágás hatására a két szélső kívánalomél irányítottá válik, egy körben lesznek, és minden más kívánalomél átfedése változatlan marad.
a b
c
d
c b
a
Az algoritmus
Ha van irányított komponens csinálj egy biztonságos körnövel reverzált Különben{ Ha a gátak száma páros{ Ha a gátak száma több, mint kett Köss össze két nem konszekutív gátat Különben Kössd össze a két gátat } Különben{ // gátak száma páratlan Ha van egyszer gát Vágd el Különben{ // er dünk van Ha a gátak száma több, mint három Köss össze két nem konszekutív gátat Egyébként köss össze két gátat } } }
Transzpozíciók Rendezés transzpozíciókkal: Ismeretlen komplexitású probléma már 10 éve!!! Bafna & Pevzner (1995) 1.5-approximáció Alapja: Egy transzpozíció a körök számát max. 2-vel növeli. Minden permutációban vagy van egy 2-transzpozíció, vagy egy 0-2-2 sorozat
1.375-approximáció: Több, mint 10000 eset számítógépes vizsgálata
Reverziós medián probléma Adottak π1, π2, π3 előjeles permutációk, keressük azon πM-et, amelyre
d (π M−1π 1 ) + d (π M−1π 2 ) + d (π M−1π 3 )
Visszavezethető a Travelling Salesman problémára
π
π
π
NP-teljes probléma!!!
π
minimális
Összes optimális inverziós útvonal Miért fontos? • Heurisztikus algoritmusok reverziós mediánra • Mutációs „forró pontok” keresése Siepel, A.C. (2002) RECOMB proceedings: Semi-brute-force algoritmus Gyakorlatilag pontosan leírja az irányítatlan komponenseken ható rendező reverzálokat, de semmit nem mond a biztonságos körnövelő reverzálokról. Fő probléma: nem csak a lehetséges útvonalak száma, de az ezt reprezentáló hálózat mérete is lehet exponenciális függvénye a permutáció hosszának
A mai előadás • Genomátrendeződések biológiai jelentősége Filogenetikai elemzések Genomátrendeződés rákos sejtekben • Matematikai modellek Előjeles permutációk és rajtuk ható mutációk Valóság és kívánalom gráfja, graph of desire and reality • Parszimónia módszerek Hannenhalli-Pevzner elmélet inverziókra (reverzálokra) Approximációk más esetekre Összes optimális reverziós útvonal megkeresése • Statisztikus módszerek MCMC, Sztochasztikus optimalizálás Bayes statisztika Központi kérdés: Markov láncok konvergenciája • Analitikus megoldások
Markov lánc Monte Carlo (MCMC) Metropolis, Rosenbluth, Rosenbluth, Teller, Teller (1953) J. Chem. Phys. 21:1087-1091.
T(Y|X) aperiodikus, irreducibilis Markov lánc, T(Y|X) ≠ 0 → T(X|Y) ≠ 0 ∀X-re π(X)>0 eloszlás, akkor a következő algoritmussal definiált Markov lánc konvergál π(X)-hez:
T ( X | Y )π (Y ) min 1, T (Y | X )π ( X )
• 1. (proposal) Végy egy random Y-t T(⋅|X)-ből. • 2. (acceptance) A Markov lánc következő eleme Y
valószínűséggel, és X ennek komplementerével Első alkalmazások: mintavételezés Boltzmann eloszlásból Bayes statisztikában szeretik: nem kell a normalizációs konstanst ismerni! P (Θ | D ) =
P ( D | Θ) P ( Θ)
∫ P ( D | Θ' ) P ( Θ' )
Θ'
Mintavételezés
P (Θ | D) ∝ P( D | Θ) P (Θ) -ból
Összes optimális inverziós útvonalból mintavételezés
Proposal p1 p2 p3 p4 p5 p6 p7 p8 p9
Random ablak
}
p7−1 p6−1 p5−1 p’ p’’
p7−1 p6−1 p5−1
p’’’ id
Új rész-útvonal
p1 p2 p3 p4 p’ p’’ p’’’ p8 p9
Simulated Annealing Definiálunk egy hipotetikus ’energiát’ a Markov lánc minden X állapotára. Minnél ’jobb’ egy állapot, annál kisebb az energiája. Az MCMC céleloszlása a Boltzmann eloszlás
PT ( X ) ∝ e
−E( X ) T
A T hőmérsékletet fokozatosan csökkentjük. Ha a hőmérsékletet elég lassan csökkentjük, akkor bizonyítottan 1 valószínűséggel a globális minimumhoz fog konvergálni a Markov lánc. (Persze az ’elég lassan’ miatt nem tudunk egy NP-teljes problémát polinom időben megoldani...)
Sztochasztikus heurisztikus algoritmussal próbálunk meg egyre jobb útvonalakat találni
Bayesiánus MCMC Egy Θ (evolúciós) paraméterhalmaz valószínűségének a feltételes eloszlása érdekel, adottak a D biológiai adatok
P ( Θ | D ) ∝ P ( D | Θ) P ( Θ) poszterior α likelihood × prior A közvetlen likelihood számolás nehéz. Ha egy statisztikus nem tud egy problémát megoldani, akkor csinál belőle egy komplikáltabbat...
P ( D | Θ) =
∑ P(traj | Θ)
traj D
MCMC konvergenciája A konvergencia sebességét nem a lépésszámban, hanem a számolási időben szeretnénk optimalizálni. Sokszor nem világos, hogy mi legyen a proposal eloszlás, melyek a ’jó’ mutációk Sejtések: • Töréspontot csökkentő mutációk • Körök számát növelő permutációk • Egyéb (???) Pl. Körök számát növelő transzpozíciók: O(n3) memória és idő (Miklós, 2003), töréspontok számát csökkentő transzpozíciók: O(n) memória és idő (Miklós & Paige, 2006)
Irreducibilitás Ha az optimális reverziók útvonalain akarunk bolyongani, mekkora részt kell kivágni az útvonalból, hogy irreducibilis legyen a láncunk?
Válasz: az egészet!!!
1
0
Metropolizált független mintavételezés (MIS) MIS: Olyan MCMC, amelyben T(Y|X) = T(Y), bármely X-re. MIS-re a spektrális rés
1 λ1 − λ2 = max (w)
ahol w a fontossági súly, π(X)/T(X) (Liu, 1995)
A MIS bizonyítottan lassan keveredik optimális reverziós útvonalakra, azaz meg lehet adni olyan permutációsorozatot, amelyre max(w) exponenciálisan növekszik a permutáció hosszának függvényében (Mélykúti, készülő szakdolgozat).
Részleges IS (ParIS) Egy random hosszúságú ablakot vágunk ki, ezen teszünk egy MIS lépést Az alábbi példában a MIS bizonyítottan lassan keveredik, a ParIS bizonyítottan gyorsan, és ha csak kis ablakokat vágunk ki, a Markov lánc nem lesz irreducibilis
Ugyanakkor van példa olyan hálózatra, ahol a ParIS is lassan keveredik. Nyílt kérdés: gyorsan vagy lassan keveredik a ParIS az optimális reverziós útvonalakon?
A mai előadás • Genomátrendeződések biológiai jelentősége Filogenetikai elemzések Genomátrendeződés rákos sejtekben • Matematikai modellek Előjeles permutációk és rajtuk ható mutációk Valóság és kívánalom gráfja, graph of desire and reality • Parszimónia módszerek Hannenhalli-Pevzner elmélet inverziókra (reverzálokra) Approximációk más esetekre Összes optimális reverziós útvonal megkeresése • Statisztikus módszerek MCMC, Sztochasztikus optimalizálás Bayes statisztika Központi kérdés: Markov láncok konvergenciája • Analitikus megoldások
Sztochasztikus modell reverzálokra A modellben az előjeles permutációk véletlenszerűen változnak meg, minden reverzál exponenciális várakozási idő után következik be. Azaz a reverzálok által generált Cayley-gráfon van egy időfolytonos Markov modellünk. Az exponenciális eloszlás valamely paraméterére keressük a
Pt (G 2 | G1 ) valószínűséget. Van-e algoritmus, ja? ’Hagyományos’ algoritmus
ami
(2 n!) n
idő alatt!
3
ezt
gyorsan
kiszámol-
Összeejtett dinamikai rendszer Vegyük a Cayley gráf szimmetriacsoportjában a Cayley gráf valamely G0 pontjának a stabilizátorát. Ekkor ha G1 és G2 a stabilizátor egy orbitjában van, akkor
Pt (G1 | G0 ) = Pt (G2 | G0 ) bármely t időpontra. Kérdés: legyen a Cayley gráf a reverzálok által meghatározott gráf. Mivel izomorf egy pont stabilizátora? Hány orbitja van?
Egy probléma Cayley-gráfokról Legyen Γ1 azon Cayley gráfok halmazrendszere, amelyre a minimális hosszúságú generálószavak számára van gyors algoritmus. Legyen Γ2 azon Cayley gráfok halmazrendszere, amelyre az időfolytonos dinamika gyorsan számolható (Bármely G1, G2, t-re Pt(G1|G2)). Mi Γ1 és Γ2 viszonya? (Tipp: Γ1 = Γ2)
Nyitott problémák • O(n) idejű algoritmus optimális reverziós útvonalra • Gyors algoritmus az optimális reverziós útvonalak egyenletes eloszlásából való mintavételezésére • Az optimális reverziós útvonalak számát megadó algoritmus komplexitása • Egy optimális transzpozíciós útvonalat megadó algoritmus komplexitása • Mutációs útvonalakon bolyongó Markov lánc Monte Carlo metódusok konvergenciájának sebessége • Mutációs Cayley-gráfok szimmetriacsoportjában egy stabilizátor részcsoport oritjai • Mutációs Cayley gráfokon történő időfolytonos bolyongás időbeli leírása
Köszönetnyílvánítás Mélykúti Bence, Timothy Brooks Paige
Falus András, Erdős Péter, Miklós Dezső, Lovász László, Tusnády Gábor
