Problémák és megoldások a bioinformatikában
Válogatott fejezetek a bioinformatikából
Gyimesi Gergely, 2008. február 25.
• Mik a fontos, megoldatlan biológiai problémák? • Milyen módszereket, megoldási lehetıségeket ad a bioinformatika ezekre? • Mik ezeknek a korlátai?
Mik a felismerési kódok fehérje-{DNS,RNS,fehérje} kölcsönhatások esetén
Pontos ab initio fehérjeszerkezet jóslás
Molekula
Sejt
Evolúció
Racionális inhibitortervezés
Mikor és hol fog transzkripció történni?
Splicing mintázatok jóslása
Új fehérjefunkciók kialakulásának mechanisztikus megértése
Jelátviteli hálózatok modellje: hogyan reagál egy sejt a külsı stimulusra?
A speciáció molekuláris részleteinek mechanisztikus megértése
Hatékony gén ontológiák továbbfejlesztése gének és fehérjék funkciójának szisztematikus leírására
Szekvenciaillesztés – többszörös illesztés Fragmens összeállítás (fragment assembly) Fragmensek fizikai vetítése (physical mapping) Filogenetikus fák építése Genomátrendezıdések modellje Genomösszehasonlítás Génpredikció – génkeresés Fehérjeszerkezet predikció Microarray kísérletek kiértékelése Fehérjeklasszifikáció (osztályozás) Vizualizációs programok, felületek
Páronkénti szekvenciaillesztés (pairwise sequence alignment) • Mik az egymásnak (funkcionálisan vagy szerkezetileg) megfelelı egységek? • Mekkora az evolúciós távolság közöttük? Dotplot • a legegyszerőbb „vizuális illesztés” 1, ai = b j M ij = δ ai ,b j = 0, ai ≠ b j
• rövid, egzakt illeszkedések könnyen felfedezhetıek ...gcctaGGCATGCGAtgcgt... ...cgggaGCCGTGTAGTTGACGgcctg... ||||||||| ||||||||||||||| ...catggGGCATGCGAgtgac... ...cctagGCCGTGTAGTTGACGtgcgt...
• ismétlıdı elemek megtalálása • közös domének megtalálása • hosszú szekvenciák (> 1000 bp) összehasonlításánál hatékony
Páronkénti szekvenciaillesztés (pairwise sequence alignment) Optimális illesztés keresése hézagok (gap) beszúrásával Biológiai események: • beszúrás gap, indel • törlıdés • szubsztitúció (csere) • két szekvenciának sokféle lehetséges illesztése van, de az „optimálisat” keressük • pontozás:
Sa ,b = ∑ M ai ,bi
K-LYE—CN---E-SK -Y---EC-NQC-G-K KLYECNESK YE-CNQCGK KLYECNE-SK --YECNQRGK
i
M a ,b : (aminosav/nukleotid) szubsztitúciós mátrix Egzakt megoldások dinamikus programozással: • Lokális illesztés: csak a legjobban illeszkedı részszekvenciák felhasználása Smith & Waterman, 1981. • Globális illesztés: az összes karakter felhasználása Needleman & Wunsch, 1970.
futási idı:
Ο(nm)
Páronkénti szekvenciaillesztés (pairwise sequence alignment) Szubsztitúciós mátrixok PAM (Point Accepted Mutation, Percent Accepted Mutation) • Margaret Dayhoff, 1970-es évek • kézzel összerendezett közeli rokon szekvenciák alapján statisztika • log-odds:
• 1 PAM evolúciós egység: 1 csere / 100 aminosav • hatványozással PAM30, PAM70, PAM250 mátrixok BLOSUM (Block Substitution Matrix) • Henikoff and Henikoff, 1992 • távoli homológokat is felhasználtak • nagyobb adatkészlet • BLOSUM62 – legfeljebb 62%-ban azonos szekvenciák alapján
Páronkénti szekvenciaillesztés (pairwise sequence alignment) Szubsztitúciós mátrixok
PAM250
BLOSUM62
Páronkénti szekvenciaillesztés (pairwise sequence alignment) Homológia: hasonlóság, ami közös ıstıl való származásból ered szekvenciák esetén gyakran közelítik a magas százalékos egyezéssel (pl. >50%) Homológ szekvenciák keresése: gyors, heurisztikus módszerek FASTA • egzakt (BLAST) vagy majdnem-egzakt (FASTA) gap nélküli rövid illeszkedéseket keres • ezeket kiterjeszti lokálisan mindkét irányba, gapekkel • az eredmények szignifikanciáját becsli
p A = pG = pT = pC = 0.25
keresı szekvencia (Q) hossza: LQ adatbázis (D) hossza: LD
L hosszú egzakt egyezés esélye: p = 0.25L = 2 −2 L ez elıfordulhat Q-ban m = LQ − L + 1 különbözı helyen (effective length of query), D-ben n = LD − L + 1 különbözı helyen (effective length of database). véletlenszerő egyezés esélye (E-value): E = mn 2 −2 L = mne − λ R
Többszörös szekvenciaillesztés (multiple sequence alignment, MSA) KLYECNE-SK --YECNQRGK KLYECNQRGK KVYECNEKGDinamikus programozás alkalmazható:
Ο(l n )
• kevés számú szekvencia (~5-10) esetén használható • nagy adatkészletekre (~10, ~100 db) nem túl praktikus Heurisztikus módszerek Progresszív illesztés (progressive alignment) • hierarchikus vagy fa-módszer (tree method) • illesztések sorozatát végezzük el egy irányító fa mentén (guiding tree) • elıször a két (evolúciósan) legközelebbi szekvenciát illesztjük • utána ehhez az illesztéshez illesztjük a következı legközelebbit • automatikusan egy filogenetikus fát is létrehoznak
Többszörös szekvenciaillesztés (multiple sequence alignment, MSA) ClustalW 1. páronkénti távolságok megállapítása (teljes dinamikus programozás vagy valamilyen gyors heurisztika) 2. klaszterezés (pl. neighbor-joining) 3. progresszív illesztés Korlátok: • erıs függés a kezdeti rokonságkereséstıl és a kezdeti illesztés minıségétıl • romlik a teljesítmény, ha • távoli klaszterek • mind távoliak • súlyozással csökkenteni lehet a kezdeti illesztés hatását
Többszörös szekvenciaillesztés (multiple sequence alignment, MSA) T-Coffee • más információt (pl. szerkezeti illesztésbıl származót) is fel tud használni PSAlign • részlegesen progresszív (semi-progressive) módszer, nem használ heurisztikát és polinomiális idejő T : fa i, j : szekvenciák Pi,j : illesztés
Megadható olyan többszörös illesztés, amely mindegyik Pi,j páronkénti illesztést megtartja
T i
Pi , j
• adott szekvenciákból készítsünk egy teljes gráfot, élhosszak az evolúciós távolság • keressük meg a minimális feszítıfát
j
Többszörös szekvenciaillesztés (multiple sequence alignment, MSA) Iteratív módszerek Progresszív módszerek legnagyobb hiányossága: egyszer összeillesztett szekvenciák már úgy maradnak
PRRN/PRRP
CHAOS/DIALIGN MUSCLE Rejtett Markov modellek (HMM)
POA, SAM
Genetikus algoritmusok, szimulált hıkezelés
SAGA, MSASA
Filogenetikus fák (phylogenetic trees) Cél: létrehozni egy olyan fát, amely leginkább jellemzi az adott gének, fajok, stb. leszármazását.
gyökértelen
gyökeres
ultrametrikus
Filogenetikus fák (phylogenetic trees) Távolság alapú módszerek (distance based methods) • távolságmátrixot hoznak létre a szekvenciákból (gyakran egy Dij = w( e) többszörös illesztés alapján) e∈Pi , j • egzakt megoldás csak akkor van, ha a távolságmátrix additív: • létrehoznak egy fát, ami a leginkább illeszkedik a távolság Pi , j az út i-bıl j-be adatokhoz UPGMA (Unweighted Pair Group Method with Arithmetic mean) módszer • a legegyszerőbb faépítési módszer, mindig a legközelebbi szomszédot összevonjuk • új távolságok: d A , C + d B ,C
∑
d AB ,C =
2
• feltételezi, hogy az evolúció sebessége minden ágon egyforma volt (molekuláris óra hipotézis) Neighbor-joining (NJ) módszer • az új klaszter távolságát másképp számolja • megenged különbözı evolúciós sebességeket (ez a reális) Gyors, polinomiális idejő módszerek (ClustalW, PHYLIP)
Filogenetikus fák (phylogenetic trees) Fitch-Margoliash módszer • egy adott fatopológiához az élhosszakat legkisebb négyzetek értelemben illeszti a távolságmátrixhoz • a fa-térben való keresés miatt NP-nehéz Távolság alapú módszerek: • gyorsak, hatékonyak • nagy mennyiségő adat esetén is általában reális fákat adnak • bármilyen távolság adat felhasználható (pl. DNS-DNS hibridizációs kísérletek) • node density effect: a fa rosszul mintavételezett részein (kevés faj) inkább alulbecsültek lesznek a távolságok • a távolságok nem függetlenek, ezért a hibák az egész fát érintik
Filogenetikus fák (phylogenetic trees) Karakter alapú módszerek karakter = diszkrét állapotokat felvevı tulajdonság Maximum parszimónia módszerek (maximum parsimony) • olyan fát keres, amivel a legkevesebb mutációval leírható a filogenetika Kis parszimónia probléma (small parsimony problem) • adott fának mennyi a parszimónia-pontszáma? (minimális változások) • polinomiális idıben megoldható Nagy parszimónia probléma (large parsimony problem) • melyik fatopológia az optimális? • NP-nehéz
Filogenetikus fák (phylogenetic trees) alkalmazott módszerek: branch and bound • egzakt megoldás • teljes enumerációhoz hasonló, de a keresıfa bizonyos részeit levágja
Filogenetikus fák (phylogenetic trees) heurisztikus módszerek nearest neighbor interchange (NNI) C
A
A
D
C
B
e B
D
• egy él négy al-fára osztja a fát, ezeket cserélgetjük
A
C
D
B
Filogenetikus fák (phylogenetic trees) Subtree pruning and regrafting (SPR)
Filogenetikus fák (phylogenetic trees) Tree bisection-reconnection (TBR)
Filogenetikus fák (phylogenetic trees) Problémák a parszimónia módszerekkel Long branch attraction: • gyorsan evolválódó fajok egymáshoz közelinek lesznek jósolva A
C
• emiatt nem statisztikusan konzisztens B
Parametrikus statisztikus modellek • explicit szubsztitúciós modellt használnak • az egyes ágakon más-más lehet az evolúció sebessége • többszörös mutációkat is figyelembe tudja venni • az egyes fákhoz valószínőségi értékeket rendelnek
D
Filogenetikus fák (phylogenetic trees) Szubsztitúciós modellek – sztochasztikus Markov folyamatok Átmeneti mátrixok (transition matrix)
tranzíció (nagy nagy) transzverzió (nagy kicsi, kicsi nagy) Ráta mátrixok (rate matrix)
P (t + dt ) = P (t ) + QP (t )dt P ( t + ∆ t ) = e Q ∆t P ( t ) egyensúlyi eloszlás: reverzibilitás:
Filogenetikus fák (phylogenetic trees) Szubsztitúciós modellek JC69 (Jukes, Cantor, 1969)
K80 (Kimura, 1980)
• tranzíció/transzverzió megkülönböztetve F81 (Felsenstein, 1981)
HKY85 (Hasegawa, Kishino, Yano, 1985)
Fehérjékre: PAM, BLOSUM mátrixok alapján
Filogenetikus fák (phylogenetic trees)
poszterior valószínőség prior valószínőség
Maximum likelihood módszer
P( D | T ) P (T ) P (T | D ) = P( D ) az egyes pozíciók függetlenek:
n
P( D | T ) = ∏ P( D (i ) | T ) i =1
az egyes ágakon az evolúció független
P( D ( i ) | T ) = ∑∑∑∑ P ( A, C , C , C , G , x, y , z , w | T ) x
y
z
w
P ( A, C , C , C , G , x, y , z, w | T ) = P ( x ) P( y | x, t6 ) P( A | y , t1 ) P(C | y , t2 ) P( z | x, t8 ) P(C | z, t3 ) P( w | z , t7 ) P(C | w, t4 ) P(G | w, t5 )
P ( D | T ) = ∑ P( x ) ∑ P ( y | x, t6 ) P( A | y , t1 ) P(C | y, t2 ) x y (i )
× ∑ P ( z | x, t8 ) P (C | z, t3 ) × ∑ P ( w | z, t7 ) P(C | w, t4 ) P(G | w, t5 ) w z
Filogenetikus fák (phylogenetic trees) Maximum likelihood módszer • számításigényes • távolabbi szekvenciák vizsgálatára is alkalmas • a kapott fa szignifikanciáját nehéz megbecsülni Maximum a posteriori probability (MAP) módszerek • az egyes fáknak prior valószínőséget adnak (pl. speciáció – elágazás valószínősége) • sztochasztikus módszerrel keresnek a fa-térben, pl: Markov chain Monte Carlo (MCMC) • legvalószínőbb fák egy sokaságát adják
Fehérjeszerkezet predikció Homológia modellezés (homology modeling, comparative modeling) • megfigyelés: a fehérjék harmadlagos szerkezete konzerváltabb, mint az aminosav szekvencia • magas szekvenciaazonosság homológia szerkezeti hasonlóság • a szerkezetépítéshez templátokat használ (hasonló fehérjéket) • lépések: • templát választás (általában 1 db) • szekvenciaillesztés • modellépítés • modell értékelés
• fontos egy jó minıségő illesztés • régiók, amelyekrıl a templát nem tartalmaz információt – loopok
Fehérjeszerkezet predikció Homológia modellezés (homology modeling, comparative modeling) Modellépítési módszerek Fragmens összeállítás (fragment assembly) • közeli fehérjékben egy mag (core) régió szerkezete erısen konzervált, elıször ezt építik fel • a változó régiókat különbözı szerkezetekbıl veszik Szegmens illesztés (segment matching) • a kérdéses szekvenciát felosztja szegmensekre, amelyekhez külön-külön keres templátot Távolságkényszerek alkalmazása • a templát alapján geometriai kritériumokat állít fel, és ezeket próbálja kielégíteni
Fehérjeszerkezet predikció Homológia modellezés (homology modeling, comparative modeling) MODELLER • az ötlet NMR spektroszkópiás szerkezetmeghatározási módszerekbıl ered • kényszereket hoz létre: • távolságokra és gerinc torziós szögekre az illesztés (templát) alapján • kötéshossz, kötésszög preferenciákat a CHARMM-22 force field alapján • oldalláncok torziós szögeire statisztikus preferenciákat (rotamer könyvtárak) • nemkötı atomok távolságeloszlására • a kényszereket valószínőség-sőrőségfüggvényekké alakítja • konjugált gradiensek optimalizáció, szimulált hıkezelés • elıször a gerinc felépítése, majd rögzített gerinc mellett az oldalláncok optimalizációja (itt nagyobb a hiba lehetısége)
Fehérjeszerkezet predikció Homológia modellezés Modell értékelés • gyors módszerek, pl. WHAT_CHECK • Ramachandran-térkép ellenırzése • oldalláncok torziós szögei, rotamer állapotok • hidrogénkötések optimalizálása, pl. Asn/Gln fejcsoportjának 180°elfordítása
gerinc
Fehérjeszerkezet predikció Homológia modellezés Modell értékelés statisztikus potenciálokkal DOPE (Discrete Optimized Protein Energy) • ismert szerkezetek alapján atomtípus-párok távolságeloszlása
• ennek alapján megbecsülhetı, hogy egy új szerkezet mennyire „valószínő” • fizikai potenciálként is értelmezhetı:
(potential of mean force, Boltzmann-statisztika) léteznek aminosav felbontású modellek (aminosav kontaktusok alapján) hatékonyabbak, mint a fizikai energiát számoló módszerek aminosavankénti pontszámok esetén azonosíthatók a gyenge minıségú régiók
Fehérjeszerkezet predikció Homológia modellezés Modell értékelés fizikai energia számolásával • valamilyen molekulamechanikai force-field (pl. OPLS, CHARMM) alapján legfontosabb kölcsönhatások: van der Waals
elektrosztatikus • oldószer figyelembevétele (implicit szolvatációs modell) • entropikus járulékok figyelembe vétele számításigényes!
Fehérjeszerkezet predikció Homológia modellek pontossága • erısen függ a templát kiválasztásától és a szekvencia illesztés minıségétıl • 50% azonosság felett: • gerinc RMSD ~1 Å körüli • közepes minıségő NMR szerkezeteknek felel meg • hibák lehetnek az oldalláncok pakolásában, kisebb gerinc torzulások, nagyobb hibák lehetnek a loop régiókban • 30-50% azonosság: • jelentısebb hibák is elıfordulhatnak, fıleg a loop régiókban • a gerinc 90%-a ~1.5 Å körüli • 30% alatt („twilight zone”) • alapvetı hibák lehetnek, pl. rossz fold • jelentısen megnövekszik az illesztési hibák száma • nem túl jól használható olyan esetben, amikor pontos atomi felbontású szerkezetre van szükség (pl. racionális gyógyszertervezés, fehérje-fehérje kölcsönhatások jóslása) • kvalitatív következtetések levonhatók, pl. egyes aminosavak szerkezeti szerepe, konzerváltságának oka, stb.
Fehérjeszerkezet predikció Paracelsus challenge (1994) • alakítsunk át egy fehérjét teljesen más foldra, legalább 50% szekvenciaazonosság megtartásával • megoldás 1997: Janus fehérje • a szekvenciaazonosság nem feltétlenül jelent szerkezeti hasonlóságot
Fehérjeszerkezet predikció Protein threading
• a kérdéses szekvenciát ismert fehérjeszerkezetekre ráfőzzük (thread) • becslést teszünk az illeszkedés jóságára • elmélet: a természetben legfeljebb kb. 2000 különbözı szerkezeti család (fold) létezik, ebbıl kb. 1100 azonosított • strukturális illesztés • fold recognition Ab initio fehérjeszerkezet jóslás • folding probléma • nem használ fel elızetes szerkezeti információt • a pontozófüggvénynek nem feltétlenül kell fizikai jelentést hordoznia http://en.wikipedia.org/wiki/Protein_structure_prediction_software
