1-BIN-301, 2-AIN-501 Methods in Bioinformatics, 2022/23

Introduction · Rules · Tasks and dates · Materials · Moodle · Discussion
Quizzes can be found in Moodle.
Homework assignments and journal club papers can be found in Tasks and dates.
Groups for journal club have each their own channel in MS Teams.


MBI 2010/2011: Rozdiel medzi revíziami

Z MBI
Prejsť na: navigácia, hľadanie
(Created page with '=UCSC genome browser, cvičenia pre biológov= * Používajte čierne počítače, zvoľte v menu Bioinformatika, užívatel Bioinformatika * V programe Firefox choďte na strán…')
 
Riadok 1: Riadok 1:
 +
* [[Sekvenovanie genómov, cvičenia pre informatikov]]
 +
* [[Zarovnávanie sekvencií, cvičenia pre biológov]]
 +
* [[Zarovnávanie sekvencií 2, cvičenia pre biológov]]
 +
* [[Zarovnávanie sekvencií, cvičenia pre informatikov]]
 +
* [[Zarovnávanie sekvencií 2, cvičenia pre informatikov]]
 +
* [[Hľadanie génov a anotácia sekvencií, cvičenia pre biológov]]
 +
* [[Skryté Markovove modely, cvičenia pre informatikov]]
 +
* [[Evolúcia, cvičenia pre biológov]]
 +
* [[Evolúcia 2, cvičenia pre biológov]]
 +
* [[Evolúcia, cvičenia pre informatikov]]
 +
* [[Evolúcia 2, cvičenia pre informatikov]]
 +
* [[Proteíny, cvičenia pre biológov]]
 +
* [[Evolúcia 3 a proteíny, cvičenia pre informatikov]]
 +
* [[Proteíny, cvičenia pre informatikov]]
 +
* [[Expresia génov, cvičenia pre biológov]]
 +
* [[Proteíny 2, cvičenia pre informatikov]]
 +
* [[Hľadanie motívov, cvičenia pre informatikov]]
 +
* [[Hľadanie motívov a populačná genetika, cvičenia pre biológov]]
 +
* [[Populačná genetika, cvičenia pre informatikov]]
 +
 +
=Počítanie fylogenetických stromov, cvičenia pre informatikov=
 +
* Ako definujeme strom v teorii grafov? suvisly acyklicky neorientovany graf
 +
* Strom s n vrcholmi ma n-1 hran
 +
* Nezakoreneny binarny fylogeneticky strom: neorientovany suvisl acyklicky graf, v listoch sucasne druhy, vsetky vnutorne vrcholy stupna 3
 +
* Zakoreneny binarny fylogeneticky strom: vsetky hrany orientujeme od korena smerom k listom, kazdy vnutorny vrchol ma dve deti
 +
* Niekedy uvazujeme aj nebinarne stromy, v ktorych mame vnutorne vrcholy vyssieho stupna
 +
* Zakoreneny binarny strom s n listami ma n-1 vnutornch vrcholov, teda 2n-2 hran
 +
* Nezakoreneny binarny strom s n listami ma n-2 vnutornych vrcholov, teda 2n-3 hran
 +
* Pocet nezakorenenych fylogenetickych stromov s n listami:
 +
** a(3) = 1, a(4) = 3, a(n+1) = a(n) * (2n-3) a teda a(n) = 1 * 3 * 5 * ... * (2n-5) = (2n-5)!!
 +
* Pocet zakorenenych fylogenetickych stromov s n listami:
 +
** zakoren strom s n listami kazdy 2n-3 sposobmi, teda (2n-3)!!
 +
 
=UCSC genome browser, cvičenia pre biológov=
 
=UCSC genome browser, cvičenia pre biológov=
 
* Používajte čierne počítače, zvoľte v menu Bioinformatika, užívatel Bioinformatika
 
* Používajte čierne počítače, zvoľte v menu Bioinformatika, užívatel Bioinformatika
Riadok 148: Riadok 181:
 
* Realne pouzivana technologia, aj pre sekvenovanie novej generacie, napr. Zerbino and Birney 2008 program Velvet
 
* Realne pouzivana technologia, aj pre sekvenovanie novej generacie, napr. Zerbino and Birney 2008 program Velvet
  
=Počítanie fylogenetických stromov, cvičenia pre informatikov=
+
=Sekvenovanie genómov, cvičenia pre biológov=
* Ako definujeme strom v teorii grafov? suvisly acyklicky neorientovany graf
+
* Cvicenia pre biológov zo sekvenovania, pracovna verzia poznamok
* Strom s n vrcholmi ma n-1 hran
+
* Ospravedlnujem sa za chybajucu diakritiku
* Nezakoreneny binarny fylogeneticky strom: neorientovany suvisl acyklicky graf, v listoch sucasne druhy, vsetky vnutorne vrcholy stupna 3
+
* Pozrite tiez grafy k pravdepodobnosti: http://compbio.fmph.uniba.sk/vyuka/mbi/poznamky/cb02.pdf
* Zakoreneny binarny fylogeneticky strom: vsetky hrany orientujeme od korena smerom k listom, kazdy vnutorny vrchol ma dve deti
+
 
* Niekedy uvazujeme aj nebinarne stromy, v ktorych mame vnutorne vrcholy vyssieho stupna
+
===UCSC genome browser===
* Zakoreneny binarny strom s n listami ma n-1 vnutornch vrcholov, teda 2n-2 hran
+
* http://genome.ucsc.edu/
* Nezakoreneny binarny strom s n listami ma n-2 vnutornych vrcholov, teda 2n-3 hran
+
* Ukazali sme si niekolko trackov, ktore maju suvis so sekvenovanim a skladanim genomov, napr. gaps, quality score a pod. (v genomoch cloveka a macky)
* Pocet nezakorenenych fylogenetickych stromov s n listami:
+
 
** a(3) = 1, a(4) = 3, a(n+1) = a(n) * (2n-3) a teda a(n) = 1 * 3 * 5 * ... * (2n-5) = (2n-5)!!
+
===Pravdepodobnost===
* Pocet zakorenenych fylogenetickych stromov s n listami:  
+
 
** zakoren strom s n listami kazdy 2n-3 sposobmi, teda (2n-3)!!
+
* Nas problem: spocitanie pokrytia
 +
** G = dlzka genomu, napr. 1 000 000
 +
** N = pocet segmentov (readov), napr. 10 000
 +
** L = dlzka readu, napr. 1000
 +
** Celkova dlzka segmentov NL, pokrytie (coverage) NL/G, v nasom pripade 10x
 +
** V priemere kazda baza pokryta 10x
 +
** Niektore su ale pokryte viackrat, ine menej.
 +
** Zaujimaju nas otazky typu: kolko baz ocakavame, ze bude pokrytych menej ako 3x?
 +
** Dolezite pri planovani experimentov (aku velke pokrytie potrebujem na dosiahnutie urcitej kvality)
 +
 
 +
* Uvod do pravdepodobnosti
 +
** Myslienkovy experiment, v ktorom vystupuje nahoda, napr. hod idealnou kockou/korunou
 +
** Vysledkom experimentu je nejaka hodnota (napr. cislo, alebo aj niekolko cisel, retazec)
 +
** Tuto neznamu hodnotu budeme volat nahodna premenna
 +
** Zaujima nas pravdepodobnost, s akou nahodna premenna nadobuda jednotlive mozne hodnoty
 +
** T.j. ak experiment opakujeme vela krat, ako casto uvidime nejaky vysledok
 +
** Priklad 1: hodime idealizovanou kockou, premenna X bude hodnota, ktoru dostaneme
 +
** Mozne hodnoty 1,2,..,6, kazda rovnako pravdepodobna
 +
** Piseme napr. Pr(X=2)=1/6
 +
** Priklad 2: hodime 2x kockou, nahodna premenna X bude sucet hodnot, ktore dostaneme
 +
** Mozne hodnoty: 2,3,...,12
 +
** Kazda dvojica hodnot na kocke rovnako pravdepodobna, t.j. pr. 1/36
 +
** Sucet 5 mozeme dostat 1+4,2+3,3+2,4+1 - t.j. P(X=5) = 4/36
 +
** Sucet 11 mozeme dostat 5+6 alebo 6+5, t.j. P(X=11) = 2/36
 +
** Rozdelenie pravdepodobnosti: 2: 1/36, 3:2/36, 4: 3/36, ... 7: 6/36, 8: 5/36 ... 12: 1/36
 +
** Overte, ze sucet je 1
 +
 
 +
* Pokrytie genomu: predpokladame, ze kazdy segment zacina na nahodnej pozicii zo vsetkych moznych G-L+1
 +
* Takze ak premenna Y_i bude zaciatok i-teho segmentu, jej rozdelenie bude rovnomerne
 +
** P(Y_i=1) = P(Y_i=2) = ... = P(Y_i=G-L+1) = 1/G-L+1
 +
* Uvazujme premennu X_j, ktora udava pocet segmentov pokryvajucich poziciu j
 +
** mozne hodnoty 0..N
 +
** i-ty segment pretina poziciu j s pravdepodobnostou L/(G-L+1), oznacme tuto hodnotu p
 +
** to iste ako keby sme N krat hodili mincou, na ktorej spadne hlava s pravd. p a znak 1-p a oznacili ako X_j pocet hlav
 +
** Priklad: majme mincu, ktora ma hlavu s pr. 1/4 a hodime je 3x.
 +
<pre>
 +
HHH 1/64
 +
HHT 3/64
 +
HTH 3/64
 +
HTT 9/64
 +
THH 3/64
 +
THT 9/64
 +
TTH 9/64
 +
TTT 27/64
 +
</pre>
 +
* P(X_j=3) = 1/64, P(X_j=2)=9/64, P(X_j=1)=27/64, P(X_j=0)=27/64
 +
** taketo rozdelenie pravdepodobnosti sa vola binomicke
 +
** P(X_j = k) = (N choose k) p^k (1-p)^(N-k), kde <math>{N \choose k} = \frac{N!}{k!(N-k)!}</math> a n! = 1*2*...*n
 +
** napr pre priklad s troma hodmi kockou P(X_j=2) = 3!/(2!*1!) * (1/4)^2 * (3/4)^1 = 9/64
 +
** Zle sa pocita pre velke N, preto sa niekedy pouziva aproximacia Poissonovym rozdelenim s parametrom lambda = Np, ktore ma <math>e^{-\lambda}\lambda^k / k!</math>
 +
** Spat k sekvenovaniu: vieme spocitat rozdelenie pravdepodobnosti a tiez napr. P(X_i<3) = P(X_i=0)+P(X_i=1)+P(X_i=2) = 0.000045+0.00045+0.0023=0.0028 (v priemere ocakavame 45 baz nepokrytych)
 +
** Takyto graf, odhad, vieme lahko spravit pre rozne pocty segmentov a tak naplanovat, kolko segmentov potrebujeme
 +
 
 +
* Chceme tiez odhadnut pocet kontigov (nebrali sme na cviceni, uvedene len pre zaujimavost)
 +
** Ak niekolko baz vobec nie je pokrytych segmentami, prerusi sa kontig
 +
** Vieme, kolko baz je v priemere nepokrytych, ale niektore mozu byt vedla seba
 +
** Novy kontig vznikne aj ak sa susedne segmenty malo prekryvaju
 +
** Predpokladajme, ze na spojenie dvoch segmentov potrebujeme prekryv aspon T
 +
** Lander a Waterman 1988 odhadli, ze dany segment ma pravdepodobnost zhruba exp(-N(L-T)/G), ze bude posledny v kontigu
 +
** Pre N segmentov dostaneme priemerny pocet kontigov 1+N*exp(-N(L-T)/G)
 +
** Ako keby sme dlzku segmentu skratili o dlzku prekryvu
 +
** Pre T=50 dostaneme priemerny pocet kontigov 1.75, ak znizime N na 5000 (5x pokrytie) dostaneme 44 kontigov
 +
 
 +
* Tento jednoduchy model nepokryva vsetky faktory:
 +
** Segmenty nemaju rovnaku dlzku
 +
** Problemy v zostavovani kvoli chybam, opkaovaniam a pod.
 +
** Segmenty nie su rozlozene rovnomerne (cloning bias a pod.)
 +
** Vplyv koncov chromozomov
 +
** Uzitocny ako hruby odhad
 +
** Na spresnenie mozeme skusat spravit zlozitejsie modely, alebo simulovat data
 +
 
 +
* Poznamka: pravdepodobnosti z binomickeho rozdelenia mozeme lahko spocitat napr. statistickym softverom R. Tu su prikazy, ktore sa na to hodia, pre pripad, ze by vas to zaujimalo:
 +
<pre>
 +
dbinom(10,1e4,0.001);  #(12.5% miest ma pokrytie presne 10)
 +
pbinom(10,1e4,0.001,lower.tail=TRUE); #(58% miest ma pokrytie najviac 10)
 +
dbinom(0:30,1e4,0.001); #tabulka pravdepodobnosti
 +
[1] 4.517335e-05 4.521856e-04 2.262965e-03 7.549258e-03 1.888637e-02
 +
[6] 3.779542e-02 6.302390e-02 9.007019e-02 1.126216e-01 1.251601e-01
 +
[11] 1.251726e-01 1.137933e-01 9.481826e-02 7.292252e-02 5.207187e-02
 +
[16] 3.470068e-02 2.167707e-02 1.274356e-02 7.074795e-03 3.720595e-03
 +
[21] 1.858621e-03 8.841718e-04 4.014538e-04 1.743354e-04 7.254524e-05
 +
[26] 2.897743e-05 1.112843e-05 4.115040e-06 1.467156e-06 5.050044e-07
 +
[31] 1.680146e-07
 +
</pre>
 +
 
 +
====Zhrnutie====
 +
* Pravdedpobnostny model: myslienkovy experiment, v ktorom vystupuje nahoda, napr. hod idealizovanou kockou
 +
* Vysledok je hodnota, ktoru budeme volat nahodna premenna
 +
* Tabulka, ktora pre kazdu moznu hodnotu nahodnej premennej urci je pravdepodobnost sa vola rozdelenie pravdepodobnosti, sucet hodnot v tabulke je 1
 +
* Znacenie typu P(X=7)=0.1
 +
 
 +
* Priklad: mame genom dlzky G=1mil., nahodne umiestnime N=10000 segmentov dlzky L=1000
 +
* Nahodna premenna X_i je pocet segmentov pokryvajucich urcitu poziciu i
 +
* Podobne, ako keby sme N krat hodili kocku, ktora ma cca 1 promile sancu padnu ako hlava a 99.9% ako znak a pytame sa, kolko krat padne znak (1 promile sme dostali po zaukruhleni z L/(G-L+1))
 +
* Rozdelenie pravdepobnosti sa v tomto pripade vola binomicke a existuje vzorec, ako ho spocitat
 +
* Takyto model nam moze pomoct urcit, kolko segmentov potrebujeme osekvenovat, aby napr. aspon 95% pozicii bolo pokrytych aspon 4 segmentami
 +
 
 +
===Eulerovský ťah===
 +
* Nestihli sme na cviceniach, uvedene pre zaujimavost
 +
* Orientovany graf
 +
* Silne suvisly orientovany graf
 +
* Eulerovsky tah, uzatvoreny eulerovsky tah
 +
* Pouzitie v de Bruijnovom grafe na zostavovanie genomu
 +
* Silne súvislý orientovany graf ma uzatvoreny eulerovsky tah prave vtedy, ked v kazdom vrchole je rovnako vchadzajucich a vychadzajucich hran
 +
** ak ma tah, musi byt suvisly
 +
** ak ma tak, musia sediet pocty hran
 +
** ak je suvisly a sedia pocty hran:
 +
*** prechadzka po grafe, kym sa da pokracovat nepouzitou hranou
 +
*** musime skoncit, kde sme zacali (z ostatnych vrcholov vieme pokracovat)
 +
*** zvysok grafu stale splna podmienku s poctami hran
 +
*** najdi dalsi vrchol, ktory je na tahu a ma este nepouzite hrany
 +
*** musi taky existovat
 +
*** pokracuj v tom istom, az kym sa nevratime, kde sme zacali
 +
*** cele opakujeme, az kym sa neminu hrany
 +
* Poznamka: v neorientovanych grafoch musia byt stupne vsetkych vrcholov parne
 +
* Ak hladame otvoreny tah, spojime zaciatocny a koncovy vrchol hranou a najdeme uzatvoreny tah

Verzia zo dňa a času 20:23, 2. október 2011

Počítanie fylogenetických stromov, cvičenia pre informatikov

  • Ako definujeme strom v teorii grafov? suvisly acyklicky neorientovany graf
  • Strom s n vrcholmi ma n-1 hran
  • Nezakoreneny binarny fylogeneticky strom: neorientovany suvisl acyklicky graf, v listoch sucasne druhy, vsetky vnutorne vrcholy stupna 3
  • Zakoreneny binarny fylogeneticky strom: vsetky hrany orientujeme od korena smerom k listom, kazdy vnutorny vrchol ma dve deti
  • Niekedy uvazujeme aj nebinarne stromy, v ktorych mame vnutorne vrcholy vyssieho stupna
  • Zakoreneny binarny strom s n listami ma n-1 vnutornch vrcholov, teda 2n-2 hran
  • Nezakoreneny binarny strom s n listami ma n-2 vnutornych vrcholov, teda 2n-3 hran
  • Pocet nezakorenenych fylogenetickych stromov s n listami:
    • a(3) = 1, a(4) = 3, a(n+1) = a(n) * (2n-3) a teda a(n) = 1 * 3 * 5 * ... * (2n-5) = (2n-5)!!
  • Pocet zakorenenych fylogenetickych stromov s n listami:
    • zakoren strom s n listami kazdy 2n-3 sposobmi, teda (2n-3)!!

UCSC genome browser, cvičenia pre biológov

  • Používajte čierne počítače, zvoľte v menu Bioinformatika, užívatel Bioinformatika
  • V programe Firefox choďte na stránku UCSC genome browser http://genome.ucsc.edu
  • Hore v modrom menu zvoľte Genomes
  • Na ďalšej stránke zvoľte človeka a v menu Assembly zistite, kedy boli pridané posledné dve verzie ľudského genómu (hg18 a hg19)
  • Na tej istej stránke dole nájdete stručný popis zvolenej verzie genómu. Pre ktoré chromozómy máme viacero alternatívnych verzií?
  • Zadajte región chr21:31,200,000-31,400,000
  • Zapnite si track Mapability na "pack" a track RepeatMasker prepnite na "full"
  • Mapability: nakoľko sa daný úsek opakuje v genóme a či teda vieme jednoznačne jeho ready namapovať pri použití Next generation sequencing (detaily keď kliknete na linku "Mapability")
  • Približne v strede zobrazeného regiónu je pokles mapovateľnosti. Akému typu opakovania zodpovedá? (pozrite track RepeatMasker)
  • Zapnite si tracky "Assembly" a "Gaps" a pozrite si región chr2:110,000,000-110,300,000. Aká dlhá je neosekvenovaná medzera (gap) v strede tohto regiónu? Približnú veľkosť môžete odčítať z obrázku, presnejší údaj zistíte kliknutím na čierny obdĺžnik zodpovedajúci tejto medzere (úplne presnú dĺžku aj tak nepoznáme, nakoľko nie je osekvenovaná).
  • Prejdite na genóm Rhesus, región chr7:59,022,000-59,024,000, zapnite si tracky Contigs, Gaps, Quality scores
  • Aké typy problémov v kvalite sekvencie v tomto regióne vidíte?

Sekvenovanie genómov, cvičenia pre informatikov

Uvod do pravdepodobnosti, pocitanie pokrytia genomov

  • Nas problem: spocitanie pokrytia
    • G = dlzka genomu, napr. 1 000 000
    • N = pocet segmentov (readov), napr. 10 000
    • L = dlzka readu, napr. 1000
    • Celkova dlzka segmentov NL, pokrytie (coverage) NL/G, v nasom pripade 10x
    • V priemere kazda baza pokryta 10x
    • Niektore su ale pokryte viackrat, ine menej.
    • Zaujimaju nas otazky typu: kolko baz ocakavame, ze bude pokrytych menej ako 3x?
    • Dolezite pri planovani experimentov (aku velke pokrytie potrebujem na dosiahnutie urcitej kvality)
  • Uvod do pravdepodobnosti
    • Myslienkovy experiment, v ktorom vystupuje nahoda, napr. hod idealnou kockou/korunou
    • Vysledkom experimentu je nejaka hodnota (napr. cislo, alebo aj niekolko cisel, retazec)
    • Tuto neznamu hodnotu budeme volat nahodna premenna
    • Zaujima nas pravdepodobnost, s akou nahodna premenna nadobuda jednotlive mozne hodnoty
    • T.j. ak experiment opakujeme vela krat, ako casto uvidime nejaky vysledok
    • Priklad 1: hodime idealizovanou kockou, premenna X bude hodnota, ktoru dostaneme
    • Mozne hodnoty 1,2,..,6, kazda rovnako pravdepodobna
    • Piseme napr. Pr(X=2)=1/6
    • Priklad 2: hodime 2x kockou, nahodna premenna X bude sucet hodnot, ktore dostaneme
    • Mozne hodnoty: 2,3,...,12
    • Kazda dvojica hodnot na kocke rovnako pravdepodobna, t.j. pr. 1/36
    • Sucet 5 mozeme dostat 1+4,2+3,3+2,4+1 - t.j. P(X=5) = 4/36
    • Sucet 11 mozeme dostat 5+6 alebo 6+5, t.j. P(X=11) = 2/36
    • Rozdelenie pravdepodobnosti: 2: 1/36, 3:2/36, 4: 3/36, ... 7: 6/36, 8: 5/36 ... 12: 1/36
    • Sucet tychot hodnot je 1
  • Pokrytie genomu: predpokladame, ze kazdy segment zacina na nahodnej pozicii zo vsetkych moznych G-L+1
  • Takze ak premenna Y_i bude zaciatok i-teho segmentu, jej rozdelenie bude rovnomerne
    • P(Y_i=1) = P(Y_i=2) = ... = P(Y_i=G-L+1) = 1/G-L+1
  • Uvazujme premennu X_j, ktora udava pocet segmentov pokryvajucich poziciu j
    • mozne hodnoty 0..N
    • i-ty segment pretina poziciu j s pravdepodobnostou L/(G-L+1), oznacme tuto hodnotu p
    • to iste ako keby sme N krat hodili mincou, na ktorej spadne hlava s pravd. p a znak 1-p a oznacili ako X_j pocet hlav
    • taketo rozdelenie pravdepodobnosti sa vola binomicke
    • P(X_j = k) = (N choose k) p^k (1-p)^(N-k)
    • Zle sa pocita pre velke N, preto sa niekedy pouziva aproximacia Poissonovym rozdelenim s parametrom lambda = Np, ktore ma e^{{-\lambda }}\lambda ^{k}/k!
    • Spat k sekvenovaniu: vieme spocitat rozdelenie pravdepodobnosti a tiez napr. P(X_i<3) = P(X_i=0)+P(X_i=1)+P(X_i=2) = 0.000045+0.00045+0.0023=0.0028 (v priemere ocakavame 45 baz nepokrytych, 2800 s menej ako 3 segmentami)
    • Takyto graf, odhad, vieme lahko spravit pre rozne pocty segmentov a tak naplanovat, kolko segmentov potrebujeme
  • Chceme tiez odhadnut pocet kontigov (podla clanku Lander a Waterman 1988)
    • Ak niekolko baz vobec nie je pokrytych segmentami, prerusi sa kontig
    • Vieme, kolko baz je v priemere nepokrytych, ale niektore mozu byt vedla seba
    • Novy kontig vznikne aj ak sa susedne segmenty malo prekryvaju
    • Predpokladajme, ze na spojenie dvoch segmentov potrebujeme prekryv aspon T=50
    • Aka je pravdepodobnost, ze dany segment i bude posledny v kontigu?
    • Ziaden segment j!=i nesmie zacinat v prvych L-T bazach kontigu i
    • Kazdy segment tam zacina s pravdepodobnostou (L-T)/G, v priemere ich tam zacne N(L-T)/G
    • Pouzijeme Poissonovo rozdelenie pre \lambda =N(L-T)/G a k=0, t.j. pravdepodobnost, ze tam nezacne ziaden je zhruba exp(-N(L-T)/G)
    • Pre N segmentov dostaneme priemerny pocet kontigov N*exp(-N(L-T)/G)
    • Ako keby sme dlzku segmentu skratili o dlzku prekryvu
    • Pre T=50 dostaneme priemerny pocet kontigov 0.75 (v skutocnosti vzdy aspon 1, my sme vsak neuvazovali vplyv konca sekvencie). Ak znizime N na 5000 (5x pokrytie) dostaneme 43 kontigov
  • Tento jednoduchy model nepokryva vsetky faktory:
    • Segmenty nemaju rovnaku dlzku
    • Problemy v zostavovani kvoli chybam, opkaovaniam a pod.
    • Segmenty nie su rozlozene rovnomerne (cloning bias a pod.)
    • Vplyv koncov chromozomov
    • Uzitocny ako hruby odhad
    • Na spresnenie mozeme skusat spravit zlozitejsie modely, alebo simulovat data
  • Poznamka: pravdepodobnosti z binomickeho rozdelenia mozeme lahko spocitat napr. statistickym softverom R. Tu su prikazy, ktore sa na to hodia, pre pripad, ze by vas to zaujimalo:
dbinom(10,1e4,0.001);  #(12.5% miest ma pokrytie presne 10)
pbinom(10,1e4,0.001,lower.tail=TRUE); #(58% miest ma pokrytie najviac 10)
dbinom(0:30,1e4,0.001); #tabulka pravdepodobnosti
 [1] 4.517335e-05 4.521856e-04 2.262965e-03 7.549258e-03 1.888637e-02
 [6] 3.779542e-02 6.302390e-02 9.007019e-02 1.126216e-01 1.251601e-01
[11] 1.251726e-01 1.137933e-01 9.481826e-02 7.292252e-02 5.207187e-02
[16] 3.470068e-02 2.167707e-02 1.274356e-02 7.074795e-03 3.720595e-03
[21] 1.858621e-03 8.841718e-04 4.014538e-04 1.743354e-04 7.254524e-05
[26] 2.897743e-05 1.112843e-05 4.115040e-06 1.467156e-06 5.050044e-07
[31] 1.680146e-07

Zhrnutie

  • Pravdedpobnostny model: myslienkovy experiment, v ktorom vystupuje nahoda, napr. hod idealizovanou kockou
  • Vysledok je hodnota, ktoru budeme volat nahodna premenna
  • Tabulka, ktora pre kazdu moznu hodnotu nahodnej premennej urci je pravdepodobnost sa vola rozdelenie pravdepodobnosti, sucet hodnot v tabulke je 1
  • Znacenie typu P(X=7)=0.1
  • Priklad: mame genom dlzky G=1mil., nahodne umiestnime N=10000 segmentov dlzky L=1000
  • Nahodna premenna X_i je pocet segmentov pokryvajucich urcitu poziciu i
  • Podobne, ako keby sme N krat hodili kocku, ktora ma cca 1 promile sancu padnu ako hlava a 99.9% ako znak a pytame sa, kolko krat padne znak (1 promile sme dostali po zaukruhleni z L/(G-L+1))
  • Rozdelenie pravdepobnosti sa v tomto pripade vola binomicke a existuje vzorec, ako ho spocitat
  • Takyto model nam moze pomoct urcit, kolko segmentov potrebujeme osekvenovat, aby napr. aspon 95% pozicii bolo pokrytych aspon 4 segmentami

Zostavovanie genomu pomocou eulerovskych tahov

  • Opakovanie z teorie grafov:
    • Hamiltonovska kruznica: cyklus, ktory prechadza kazdym vrcholom prave raz
    • Eulerov tah: tah, ktory prechadza po kazdej hrane prave raz
    • Zistit, ci ma graf H.c. je NP-tazke
    • Problem obchodneho cestujuceho: najst najlacnejsiu H.c. je tiez NP-tazky
    • Zistit ci ma graf E.t. a najst ho je lahke
      • neorientovany graf na E.t. <=> je suvisly a vsetky vrcholy okrem najviac dvoch maju parny stupen
      • orientovany graf ma E.t. z u do v <=> po pridani hrany z v do u je silne suvisly a vsetky vrcholy maju rovnako vchadzajucich ako vychadzajucich hran
  • Najkratsie spolocne nadslovo: zjednodusena verzia problemu zostavovania genomov zo segmentov
  • Mame danu mnozinu retazcov, chceme zostavit najkratsi retazec, ktoremu su vsetky podslova
  • Priklad: GCCAAC,CCTGCC,ACCTTC zlozime v poradi 2,1,3: CCTGCCAACCTTC
  • Mozeme si predstavit problem ako obmenu problemu obchodneho cestujuceho:
    • retazcom priradim vrcholy
    • dlzka hrany z a do b je |b|- prekryv medzi a a b
    • specialny zaciatocny vrchol, z ktoreho hrany do kazdeho a s cenou |a|
    • specialny koncovy vrchol, do ktoreho hrana z kazdeho a s cenou 0
    • hrana z koncoveho do zaciatocneho vrcholu na uzavretie cyklu
    • Hamiltonovske kruznice zodpovedaju nadslovam
    • Ak najdeme najlacnejsiu Hamiltonovsku kruznicu, mame najkratsie nadslovo
  • Ale vieme, ze problem obchodneho cestujuceho je NP-tazky
  • Je toto dokaz, ze aj najkratsie spolocne nadslovo je NP-tazke?
  • Pevzner, Tang and Waterman 2001 navrhuju namiesto Hamiltonovskej kruznice pouzit Eulerov tah (na inom grafe)
  • deBruijnov graf stupna k:
    • vrcholy: podretazce dlzky k vsetkych vstupnych retazcov
    • hrany: nadvazujuce k-tice v ramci kazdeho segmentu (s prekryvom k-1)
  • Priklad, k=2
  • Chceme prejst po vsetkych hranach, chceme chodit co najmenej, takze po kazdej len raz - Eulerov tah
  • V com je finta? Ako sme sa dostali od NP-tazkeho problemu k lahkemu?
  • Co ak deBruijnov graf nema Eulerovsky tah? Znasobime niektore hrany, tieto budu zodpovedat opakovaniam
  • Čo ak de Bruijnov graf má viacero Eulerovských ťahov?
    • Zoberieme taký ťah, ktorý obsahuje pôvodné segmenty ako podcesty
    • Zase ťažký problém, ale v praxi pomáhajú jednoduché pravidlá
  • Opatrné riešenie: Ak z vrcholu 2 cesty, rozdeľ na kontigy
  • Pouzitie sparovanych segmentov:
    • Nájdi vrcholy v grafe, ktoré im zodpovedajú
    • Ak je v grafe jediná cesta medzi týmito vrcholmi vhodnej dĺžky, premeň spárované segmenty na jeden veľký segment
  • Dalsie problemy, ktore treba riesit
    • sekvenovacie chyby: vytvaraju "bubliny" alebo slepe cesty
    • dve vlakna
  • Realne pouzivana technologia, aj pre sekvenovanie novej generacie, napr. Zerbino and Birney 2008 program Velvet

Sekvenovanie genómov, cvičenia pre biológov

UCSC genome browser

  • http://genome.ucsc.edu/
  • Ukazali sme si niekolko trackov, ktore maju suvis so sekvenovanim a skladanim genomov, napr. gaps, quality score a pod. (v genomoch cloveka a macky)

Pravdepodobnost

  • Nas problem: spocitanie pokrytia
    • G = dlzka genomu, napr. 1 000 000
    • N = pocet segmentov (readov), napr. 10 000
    • L = dlzka readu, napr. 1000
    • Celkova dlzka segmentov NL, pokrytie (coverage) NL/G, v nasom pripade 10x
    • V priemere kazda baza pokryta 10x
    • Niektore su ale pokryte viackrat, ine menej.
    • Zaujimaju nas otazky typu: kolko baz ocakavame, ze bude pokrytych menej ako 3x?
    • Dolezite pri planovani experimentov (aku velke pokrytie potrebujem na dosiahnutie urcitej kvality)
  • Uvod do pravdepodobnosti
    • Myslienkovy experiment, v ktorom vystupuje nahoda, napr. hod idealnou kockou/korunou
    • Vysledkom experimentu je nejaka hodnota (napr. cislo, alebo aj niekolko cisel, retazec)
    • Tuto neznamu hodnotu budeme volat nahodna premenna
    • Zaujima nas pravdepodobnost, s akou nahodna premenna nadobuda jednotlive mozne hodnoty
    • T.j. ak experiment opakujeme vela krat, ako casto uvidime nejaky vysledok
    • Priklad 1: hodime idealizovanou kockou, premenna X bude hodnota, ktoru dostaneme
    • Mozne hodnoty 1,2,..,6, kazda rovnako pravdepodobna
    • Piseme napr. Pr(X=2)=1/6
    • Priklad 2: hodime 2x kockou, nahodna premenna X bude sucet hodnot, ktore dostaneme
    • Mozne hodnoty: 2,3,...,12
    • Kazda dvojica hodnot na kocke rovnako pravdepodobna, t.j. pr. 1/36
    • Sucet 5 mozeme dostat 1+4,2+3,3+2,4+1 - t.j. P(X=5) = 4/36
    • Sucet 11 mozeme dostat 5+6 alebo 6+5, t.j. P(X=11) = 2/36
    • Rozdelenie pravdepodobnosti: 2: 1/36, 3:2/36, 4: 3/36, ... 7: 6/36, 8: 5/36 ... 12: 1/36
    • Overte, ze sucet je 1
  • Pokrytie genomu: predpokladame, ze kazdy segment zacina na nahodnej pozicii zo vsetkych moznych G-L+1
  • Takze ak premenna Y_i bude zaciatok i-teho segmentu, jej rozdelenie bude rovnomerne
    • P(Y_i=1) = P(Y_i=2) = ... = P(Y_i=G-L+1) = 1/G-L+1
  • Uvazujme premennu X_j, ktora udava pocet segmentov pokryvajucich poziciu j
    • mozne hodnoty 0..N
    • i-ty segment pretina poziciu j s pravdepodobnostou L/(G-L+1), oznacme tuto hodnotu p
    • to iste ako keby sme N krat hodili mincou, na ktorej spadne hlava s pravd. p a znak 1-p a oznacili ako X_j pocet hlav
    • Priklad: majme mincu, ktora ma hlavu s pr. 1/4 a hodime je 3x.
HHH 1/64
HHT 3/64
HTH 3/64
HTT 9/64
THH 3/64
THT 9/64
TTH 9/64
TTT 27/64
  • P(X_j=3) = 1/64, P(X_j=2)=9/64, P(X_j=1)=27/64, P(X_j=0)=27/64
    • taketo rozdelenie pravdepodobnosti sa vola binomicke
    • P(X_j = k) = (N choose k) p^k (1-p)^(N-k), kde {N \choose k}={\frac  {N!}{k!(N-k)!}} a n! = 1*2*...*n
    • napr pre priklad s troma hodmi kockou P(X_j=2) = 3!/(2!*1!) * (1/4)^2 * (3/4)^1 = 9/64
    • Zle sa pocita pre velke N, preto sa niekedy pouziva aproximacia Poissonovym rozdelenim s parametrom lambda = Np, ktore ma e^{{-\lambda }}\lambda ^{k}/k!
    • Spat k sekvenovaniu: vieme spocitat rozdelenie pravdepodobnosti a tiez napr. P(X_i<3) = P(X_i=0)+P(X_i=1)+P(X_i=2) = 0.000045+0.00045+0.0023=0.0028 (v priemere ocakavame 45 baz nepokrytych)
    • Takyto graf, odhad, vieme lahko spravit pre rozne pocty segmentov a tak naplanovat, kolko segmentov potrebujeme
  • Chceme tiez odhadnut pocet kontigov (nebrali sme na cviceni, uvedene len pre zaujimavost)
    • Ak niekolko baz vobec nie je pokrytych segmentami, prerusi sa kontig
    • Vieme, kolko baz je v priemere nepokrytych, ale niektore mozu byt vedla seba
    • Novy kontig vznikne aj ak sa susedne segmenty malo prekryvaju
    • Predpokladajme, ze na spojenie dvoch segmentov potrebujeme prekryv aspon T
    • Lander a Waterman 1988 odhadli, ze dany segment ma pravdepodobnost zhruba exp(-N(L-T)/G), ze bude posledny v kontigu
    • Pre N segmentov dostaneme priemerny pocet kontigov 1+N*exp(-N(L-T)/G)
    • Ako keby sme dlzku segmentu skratili o dlzku prekryvu
    • Pre T=50 dostaneme priemerny pocet kontigov 1.75, ak znizime N na 5000 (5x pokrytie) dostaneme 44 kontigov
  • Tento jednoduchy model nepokryva vsetky faktory:
    • Segmenty nemaju rovnaku dlzku
    • Problemy v zostavovani kvoli chybam, opkaovaniam a pod.
    • Segmenty nie su rozlozene rovnomerne (cloning bias a pod.)
    • Vplyv koncov chromozomov
    • Uzitocny ako hruby odhad
    • Na spresnenie mozeme skusat spravit zlozitejsie modely, alebo simulovat data
  • Poznamka: pravdepodobnosti z binomickeho rozdelenia mozeme lahko spocitat napr. statistickym softverom R. Tu su prikazy, ktore sa na to hodia, pre pripad, ze by vas to zaujimalo:
dbinom(10,1e4,0.001);  #(12.5% miest ma pokrytie presne 10)
pbinom(10,1e4,0.001,lower.tail=TRUE); #(58% miest ma pokrytie najviac 10)
dbinom(0:30,1e4,0.001); #tabulka pravdepodobnosti
 [1] 4.517335e-05 4.521856e-04 2.262965e-03 7.549258e-03 1.888637e-02
 [6] 3.779542e-02 6.302390e-02 9.007019e-02 1.126216e-01 1.251601e-01
[11] 1.251726e-01 1.137933e-01 9.481826e-02 7.292252e-02 5.207187e-02
[16] 3.470068e-02 2.167707e-02 1.274356e-02 7.074795e-03 3.720595e-03
[21] 1.858621e-03 8.841718e-04 4.014538e-04 1.743354e-04 7.254524e-05
[26] 2.897743e-05 1.112843e-05 4.115040e-06 1.467156e-06 5.050044e-07
[31] 1.680146e-07

Zhrnutie

  • Pravdedpobnostny model: myslienkovy experiment, v ktorom vystupuje nahoda, napr. hod idealizovanou kockou
  • Vysledok je hodnota, ktoru budeme volat nahodna premenna
  • Tabulka, ktora pre kazdu moznu hodnotu nahodnej premennej urci je pravdepodobnost sa vola rozdelenie pravdepodobnosti, sucet hodnot v tabulke je 1
  • Znacenie typu P(X=7)=0.1
  • Priklad: mame genom dlzky G=1mil., nahodne umiestnime N=10000 segmentov dlzky L=1000
  • Nahodna premenna X_i je pocet segmentov pokryvajucich urcitu poziciu i
  • Podobne, ako keby sme N krat hodili kocku, ktora ma cca 1 promile sancu padnu ako hlava a 99.9% ako znak a pytame sa, kolko krat padne znak (1 promile sme dostali po zaukruhleni z L/(G-L+1))
  • Rozdelenie pravdepobnosti sa v tomto pripade vola binomicke a existuje vzorec, ako ho spocitat
  • Takyto model nam moze pomoct urcit, kolko segmentov potrebujeme osekvenovat, aby napr. aspon 95% pozicii bolo pokrytych aspon 4 segmentami

Eulerovský ťah

  • Nestihli sme na cviceniach, uvedene pre zaujimavost
  • Orientovany graf
  • Silne suvisly orientovany graf
  • Eulerovsky tah, uzatvoreny eulerovsky tah
  • Pouzitie v de Bruijnovom grafe na zostavovanie genomu
  • Silne súvislý orientovany graf ma uzatvoreny eulerovsky tah prave vtedy, ked v kazdom vrchole je rovnako vchadzajucich a vychadzajucich hran
    • ak ma tah, musi byt suvisly
    • ak ma tak, musia sediet pocty hran
    • ak je suvisly a sedia pocty hran:
      • prechadzka po grafe, kym sa da pokracovat nepouzitou hranou
      • musime skoncit, kde sme zacali (z ostatnych vrcholov vieme pokracovat)
      • zvysok grafu stale splna podmienku s poctami hran
      • najdi dalsi vrchol, ktory je na tahu a ma este nepouzite hrany
      • musi taky existovat
      • pokracuj v tom istom, az kym sa nevratime, kde sme zacali
      • cele opakujeme, az kym sa neminu hrany
  • Poznamka: v neorientovanych grafoch musia byt stupne vsetkych vrcholov parne
  • Ak hladame otvoreny tah, spojime zaciatocny a koncovy vrchol hranou a najdeme uzatvoreny tah