Teema 8 - Probabilistlikud meetodid

1. Ülesandepüstitus ja sissejuhatus
2. Positsiooni-spetsiifilised kaalumaatriksid (PWM, PSSM)
3. Peidetud Markovi Mudelid (HMM)
4. Stohhastilised kontekstivabad grammatikad (SCFG)

Kirjandust

• Molecular Information Theory and the Theory of Molecular Machines (Tom Schneider)

• Markovi ahelad statistikas

• G. Z. Hertz, Gary D. Stormo: Identifying DNA and protein patterns with statistically significant alignments of multiple sequences. Bioinformatics 15(7): 563-577 (1999)

• paar testi: Dr. Matrix Biology links; Test MathML

Ülesandepüstitus

• Vajadused

• Alati ei saa mustrit ette anda lihtsalt ühe stringina ega ka regulaar-avaldisena

• Mõnikord on vaja et kasutataks tõenäosuslikke mudeleid

• See vastab sageli reaalsele füüsikalisele maailmale - näiteks valgu ja DNA vahelise võimaliku kokkupuute korral saab hinnata jõude mis määravad seondumise tugevuse

• Bioloogilised süsteemid ei ole diskreetsed digitaalsed arvutusmasinad vaid pigem analoogsed

Positsiooni-spetsiifiline kaalu-maatriks

• Vaata ka pakkimismeetode: Entroopia ja informatsiooni sisaldus (Entropy and Information Content)

• Olgu 8 sekventsi mis omavad teatud omadust:

  GATGAG
  GATGGG
  GCTGAG
  GAAGAG
  AATGAG
  GATGAA
  GTTGAG
  GATGAT
  

• Kuidas summeerida informatsiooni mis on esitatud nende 8 järjestuse pealt?

• C_i,j - tähe i esinemiste arv veerus j.

  Sagedused: Ci,j
  
  A     1    6    1    0    7    1
  C     0    1    0    0    0    0
  G     7    0    0    8    1    6
  T     0    1    7    0    0    1
  
        G    A    T    G    A    G     (konsensus?)
  

• Kas konsensus esitab kogu informatsiooni? Ei!

• Mis oleks kui otsiks konsensus-motiivi ühe lubatud veaga?

• Aga siis võib saada hoopis vale vastuse, näiteks lubaks erinevust seal kus see on väga ebatõenäoline!

  
  A G A T G A G T G
  
  1 0 1 0 1 1         = 4
    7 6 7 8 7 6       = 41
      1 0 0 0 1 1     = 3
        0 0 1 8 0 6   = 15
  
  

  GCTGAA = 7 1 7 8 7 1 = 31
  

• p_i,j - tähe i tõenäosus positsioonis j

• p_i,j = f_i,j / N (N = sekventside arv)

• Tõenäosuste tabel:

  A   0.125   0.75     0.125    0    0.875   0.125
  C     0     0.125      0      0     0       0
  G   0.875     0        0      1    0.125   0.75
  T     0     0.125    0.875    0     0      0.125
  

• Selle teisendusega pole me saavutanud veel midagi, sest suhted on samad.

  Veerus i olevate tõenäosuste summa peab olema 1: ∑_i=1..c p_i,j = 1

• Vaatame veergu j

• -log₂ P_i - Tõenäosusele P_i vastav "üllatusmoment" bittides

• Kui tõenäosus on väga väike siis oleme rohkem "üllatunud"

• Summeerime üllatuse üle kõigi võimalike tähtede ja korrutame omakorda nende tähtede tõenäosusega, et saada keskmine

• H = - ∑_i=1..c p_i log₂ p_i

• Infosisalduse tabel

  A   0.375    0.311    0.375    0    0.169   0.375
  C     0      0.375     0       0     0       0
  G   0.169     0        0       1    0.375   0.311
  T     0      0.375    0.169    0     0      0.375
  --------------------------------------------------
  H=  0.544    1.061    0.544    0    0.544   1.061
  
  

  

• Logo: Veeru kõrgus on 2 - H

• Logo: Tähe kõrgus on suhteline osa vastavast veerust: p_i*(2-H)

• Logo: Tähed sorteeritakse vastavalt p_i*(2-H)

• Mis siis kui iga tähte pole? Selle saab arvesse võtta kui panna algselt iga tähe esinemisteks 1, st. kokku justkui N=12 (8+4).

  Sagedused:
  A     2    7    2    1    8    2
  C     1    2    1    1    1    1
  G     8    1    1    9    2    7
  T     1    2    8    1    1    2
  

• Tähestik ei pea muidugi olema piiratud 4 tähega. Valkude puhul on tavaliselt 20 amino happest koosnev tähestik.

  
  Profile:
  A     5    3   93   97   97   92   55    4    1    3    2
  C     4    0    1    0    0    0    3    0    0    1    8
  G     5   94    5    0    0    0    2    0    1    0    6
  T    85    2    0    2    2    7   39   95   97   95   83
  
   
  
  

Tahad ise logosid teha?

• Tom Schneideri kodulehekülg
• WebLogo Sequence Logo Generation Form
• SEQLOGO, part of Expression Profiler

Kuidas konstrueerida selline PWM millega tasub otsida?

• Lugedes kokku iga tähe esinemiste arvu saame hinnata tähtede suhtelisi sagedusi (observed frequencies)

• Suhteliste sageduste ja eeldatava sageduse suhe (odds score)

• Eeldatavate sageduste jaoks võib võtta DNA tähestikus P_A=P_C=P_T=P_G=1/4

• Kuna sageli on sagedused erinevad, siis saab võtta ka tegelikud sagedused üle kogu genoomi, näteks.

• Näiteks kui sagedus on 0.79 ja eeldatav taustasagedus on 0.25, on shansside suhe 0.79/0.25 = 3.16. (odds score)

• Lõpuks, konverteerime shansside suhte võttes neist logaritmi alusel 2.

• W_i,j = log₂(f_i,j/p_i,), kus W_i,j on tähe i skoor veerus j.

• Et vältida olukorda kus logaritm tuleks võtta nullist võib kasutada skeemi nagu varem (igal tähel váhemalt üks esinemine) või ka valemit:

  W_i,j = log₂ (C_i,j + p_i)/ (N + 1)P_i (mis on enamváhem ekvivalentne ≈ log₂(F_i,j/P_i,) )

  kus C_i,j on i-nda tähe esinemiste arv positsioonis j ja N on kõikide sekventside arv.

  Näide - Gary Stormo (vaata artiklit)

  

• Kogu selise joonduse kohta saab anda statistilise hinnangu:

  I_seqalign = ∑_j ∑_i f_i,j log ( f_i,j / p_i,j )

• Sellise joonduse informatsiooni sisaldus (aka normaliseeritud log-odds ratio) teised nimed on Kullback-Leibler informatsioon (Kullback, Leibler, 1951) vÕi suhteline entroopia. Alternatiivselt on seda kutsutud ka large-deviation rate function (Bucklew, 1990).

• Valemil on mitmeid omadusi mis rahuldavad intuitsiooni sellise joonduse informatsiooni sisalduse kohta.

• Valem on näiteks kauguse mõõt jaotuse keskpunktist kus iga f_i,j = p_i,j.
  • Kaugus on minimaalne kui f_i,j = p_i,j
  • Kaugus on maksimaalne kui kõige vähem oodatud täht esineb eksklusiivselt, ehk f_m,j=1 ja p_m ≤ p_i iga i jaoks.

• Schneider et.al. (1986) panid tähele et 2^I_seqalign on enamvähem võrdne sagedusega millega esinevad DNA seondumis-saidid e.coli genoomis.

• Stormo etal: 2^I_seqalign on ülempiir statistilisele ootusele mis sagedusega esinevad joonduse sõnad juhuslikus sekventsis.

• Kaalumaatriksit saab vaadelda ka kui väga lihtsat 1-st neuronist koosnevat perceptroni (närvivõrgu lihtsaim alge)

• Muidugi on võimalik arendada ka keerukamaid, mitme-tasemelisi närvivõrke DNA signaalide esitamiseks

Kaalumaatriksiga otsimine

• Olgu antud tähestik Σ ja kaalumaatriks (W_i,j) kus tähele i veerus j vastab kaal W_i,j

• 
  Algoritm: Kaalumaatriksi otsimine
  Sisend: Kaalumaatriks (Wi,j), i∈1..|Σ|, j∈1..m, 
  	string S, künnisväärtus K
  Väljund: Kõik Wi,j esinemised S-is mis ületavad künnist K
  
  1. for p=1 .. |S|-m+1
  2.    sum = 0 ;
  3.    for j=1 .. m
  4.	  sum  +=  W[ S[p+j-1] ][ j ]
  5.    if sum ≥ K then report match at position p with score sum
  
  
  

• Sisuliselt on tegu täpse otsimise jõumeetodi algoritmiga

• Kas saab aga paremini kui künnis K on piisavalt kõrge? (kodune harjutus)
  • Lõpeta kui on teada et skoori ei saa paremaks kui K
  • Katseta 4 venelase tehnikat
  • Aho Corasick?

• Milline on kõikide esinemiste skooride sagedusjaotus?

• Kui tihti võib eeldada et juhuslik sekvents sisaldab esinemist skooriga ≥ K ?

Peidetud Markovi Mudelid (HMM)

• Introductory material on hidden Markov models
• ``Profile hidden Markov models'' Sean R. Eddy, Bioinformatics 14(9):755-63, 1998. (kohalik)
• ``Hidden Markov Models and Protein Sequence Analysis'' Rachel Karchin, UCSC.

• Hidden Markov Models

• Tõenäosuslik automaat!

• 

• Olekut ei saa otseselt testida (hidden)

• Vaatlused on oleku probabilistlikud funktsioonid

• Oleku-üleminekud on tõenäosuslikud

  ---

• Kui on antud HMM, siis milline on tõenäosus et on läbitud antud olekud ja väljastatud vastav sekvents?

• Kui on antud sekventsid, genereeri HMM mis maksimeeriks tõenäosuse et just need sekventsid on genereeritud selle HMM poolt.

• Näited genereerivad mudeli ja mudel genereerib näited...

• Kirjelda terve sekventside pere (näiteks valkude pere) ühe HMM abil.

• Uue sekventsi puhul küsi, kui tõenäoline, et see on samast perest...

  ---

• Võtame veidi keerulisema näite

• Valgud, tähestiku suurus on 20

• Otsesel läbimisel produtseeriks 3 tähe pikkuseid stringe

• lisaks on olekud insertion ja deletion

• 

• Olekus m1 on kõige tõenäolisem C, olekus m2 suvaline, ja m3 F, Y ja W.

  ---

• Erinevaid algoritme õppimiseks ja hindamiseks kui tõenäoline on iga string.

• Forward, Forward-backward, Viterbi, etc...

  ---

• Erinevaid HMM mudeli esituskujusid

• Tavaliselt õpitakse teatud parameetreid, näiteks kaale, kuid mitte kogu HMM topoloogiat.

• 

• HMM on kasutust leidnud kõnetuvastuses ja väga palju molekulaarbioloogia andmete analüüsis (bioinformaatikas)

Stohhastilised kontekstivabad grammatikad SCFG

• Stochastic Context Free Grammars
• Vaata artikleid

• Sakakibara et.al. 1993

• Kontekstivaba grammatika ja produktsioonid:

• 

• Süntaksianalüüsi puu (produktsioonid)

• 

• 

• Anname igale produktsioonile tõenäosuse, nii et ühe mitteterminali produktsioonide tõenäosuste summa oleks 1

• Millised puud kokku võivad anda tõenäosuse?

• 

• 

• 

• Loengumaterjal, Mark Craven

• Kolm peamist küsimust

  1. Kui tõenäoline on antud sekvents?
     the Inside algorithm

  2. Milline on antud sekventsi kõige tõenäolisem süntaksipuu?
     the Cocke-Younger-Kasami (CYK) algorithm

  3. Kuidas saame õppida parameetreid kui on antud reeglid ja hulk sekventse?
     the Inside-Outside algorithm