Genomika 2016/17

Úvod

Stránka k predmetu 2-INF-269/15 Genomika

• cvičenie na prvý týždeň
• Predbežné informácie k štátniciam

Obsahové prerekvizity

• Metódy v bioinformatike a Integrácia dátových zdrojov
• Ak ste skúsení v práci na príkazovom riadku v Linuxe, Integráciu je možné brať aj súčasne s Genomikou

Prednášky

• Prednášky spolu s predmetom PriF.KBCh/N-mCBI-119/15 na Prírodovedeckej fakulte (pre magisterské programy Genetika, Biochémia a Molekulárna biológia)
• Pozor prednášky sa riadia harmonogramom PriFUK, kde je semester 13.2.2017 až 12.5.2017
• Prednášajú Peter Baráth (Chemický ústav SAV), Ingrid Bhatia (Katedra biochémie PriFUK), Broňa Brejová (Katedra informatiky FMFI), Richard Kollár (Katedra aplikovanej matematiky a štatistiky FMFI), Martina Neboháčová (Katedra biochémie PriFUK), Jozef Nosek (Katedra biochémie PriFUK), Ľubomír Tomáška (Katedra genetiky PriFUK), Ivan Valent (Katedra fyzikálnej a teoretickej chémie PriFUK), Tomáš Vinař (Katedra aplikovanej informatiky FMFI)
• Moodle s materiálmi k prednáškam
• Učebnica čiernobiela, farebná, vo fakultnej knižnici na prezenčné použitie so signatúrou I-INF-N-20

Cvičenia

• Cvičiaci Broňa Brejová a Tomáš Vinař
• Náplňou cvičení je tvorba prehliadača genómov na báze softvéru UCSC genome browser pre vybrané genómy. Pri tejto tvorbe si precvičíme prácu s genomickými dátami a vytvoríme aj potenciálne užitočný nástroj
• Budeme pracovať ako skupina, ktorá má spoločný cieľ. Konkrétne podciele na najbližší čas si vždy rozdelíme medzi jednotlivých členov (prípadne dvojice) na spoločnom stretnutí.
• Stretnutie sa uskutoční v rozvrhovom čase pre cvičenia približne raz za dva týždne. Jednotliví členovia skupiny zosumarizujú, čo sa im z predchádzajúcich úloh podarilo a čo nie, na aké problémy narazili, čo sa zaujímavé naučili a pod. Podiskutujeme, ako by sa tieto problémy mohli riešiť, rozmyslíme ďalšie úlohy a dohodneme sa, kto bude čo robiť.
• Po skončení diskusnej časti stretnutia začnete na dohodnutých úlohách pracovať v počítačovej miestnosti, pokračujete individuálne do ďalšieho stretnutia
• Ak sa v danom týždni nekoná stretnutie celej skupiny, môžete v čase cvičení využiť miestnosť na prácu na projekte, najmä ak chcete koordinovať viac ľudí. V prípade záujmu môžeme prísť aj my a niečo poradiť (dohodnite si to vopred).

Hodnotenie

• Prednášková časť je ukončená písomnou skúškou, ktorá tvorí 50% známky, skúšku organizuje prof. Nosek
• 50% známky je za prácu na cvičeniach, pričom cca 25% známky je celkový dojem z úspešnosti skupiny ako celku a 25% z individuálneho prínosu daného študenta
• Známky A: 90+, B: 80+, C: 70+, D: 60+, E: 50+

Poznámky k hodnoteniu cvičení

• Ak niektorí študenti budú mať obzvlášť malý alebo obzvlášť veľký podiel na práci skupiny, môže byť váha ich individuálneho hodnotenia zvýšená (v extrémnych prípadoch až 50% celej známky)
• Za každú fázu skupinového projektu (t.j. po každom stretnutí) vám budú pridelené čierne a/alebo červené body
  • Červené body sú za splnené úlohy a ich počet odzrkadľuje kvalitu, kvantitu a náročnosť práce
  • Čierne body sú za úlohy, ktoré vám boli priradené, ale ktoré ste nesplnili, obzvlášť ak od nich závisí ďalší postup ostatných členov skupiny. Takisto čierne body dostanete za iné správanie, ktoré narúša úspešné napredovanie skupiny (neospravedlnená neprítomnosť na stretnutí, narušenie práce spoločného servera a pod.)
  • Individuálne hodnotenie je neklesajúca funkcia od počtu červených bodov a nerastúca od počtu čiernych, presný prepočet určíme neskôr.

Koordinácia v rámci skupiny a s cvičiacimi

• Projekt na GitHube https://github.com/bbrejova/genomika-2017
  • Slúži na ukladanie skriptov a dokumentácie, koordinácia úloh pomocou issues
  • Verejne prístupný, píšeme po anglicky, neuvádzame záležitosti súvisiace skôr s predmetom než samotným cieľom našej práce
  • Nabudúce spolu dohodneme vhodnú štruktúru

• Každý študent má Google document, v ktorom si vedie stručný denník
  • Tento denník zdieľajte s cvičiacimi na zápis, budú vám tam dopisovať body
  • V každej fáze uveďte ako nadpis dátum stretnutia, ktorým fáza začala a pod neho stručný zoznam vecí, ktoré ste spravili s linkami do GitHubu na výsledky vašej práce
  • Uveďte tiež stručný sumár, čo sa vám oproti plánu podarilo alebo nepodarilo, prípadne či s niečím boli ťažkosti, či ste spravili niečo oproti plánu navyše a pod.
  • Tento denník je vhodným podkladom pre ďalšie plánovacie stretnutie, kde sa o vašich výsledkoch budeme rozprávať, treba si ho teda pripraviť pred stretnutím
  • Ak si na stretnutí spomeniete na niečo, čo chcete pridať k denníku predchádzajúcej fázy, spravte to čím skôr (hneď po stretnutí), potom už predchádzajúcu fázu nemeňte
  • Najnovšiu fázu majte vždy na vrchu dokumentu, aby sa dala rýchlo nájsť

• Chceme aj nejaký mailing list / skupinu na oznamy ostatným členom? Alternatívne návrhy k GitHubu a Google docs?

Plán na prvé týždne

• 22.2.: organizačné detaily, práca s UCSC prehliadačom: cvičenie, rozdelenie do skupín
• 1.3. a 8.3.: ciele skupiny, podrobnejšie rozplánovanie prvých úloh

Genomika: cvičenie UCSC browser

Cvičenie na predmet Genomika

Základy browsera, gény

• On-line grafický nástroj na prezeranie genómov
• Konfigurovateľný, veľa možností, ale pomerne málo organizmov
• V programe Firefox choďte na stránku UCSC genome browser http://genome-euro.ucsc.edu/ (európsky mirror stránky http://genome.ucsc.edu/ )
• Hore v modrom menu zvoľte Genomes, potom zvoľte ľudský genóm verzia hg38. Do okienka search term zadajte HOXA2. Vo výsledkoch hľadania (Known genes) zvoľte gén homeobox A2 na chromozóme 7.
  • Pozrime si spolu túto stránku
  • V hornej časti sú ovládacie prvky na pohyb vľavo, vpravo, približovanie, vzďaľovanie
  • Pod tým schéma chromozómu, červeným vyznačená zobrazená oblasť
  • Pod tým obrázok vybranej oblasti, rôzne tracky
  • Pod tým zoznam všetkých trackov, dajú sa zapínať, vypínať a konfigurovať
  • Po kliknutí na obrázok sa často zobrazí ďalšia informácia o danom géne alebo inom zdroji dát (treba mať zapnuté na full alebo pack, inak prepína úroveň zobrazenia)
  • V génoch exóny hrubé, UTR tenšie, intróny vodorovné čiary

• Koľko má HOXA2 exónov? Na ktorom chromozóme a pozícii je? Pozor, je na opačnom vlákne. Ako je táto skutočnosť naznačená na obrázku?
• V tracku GENCODE kliknite na gén, mali by ste sa dostať na stránku popisujúcu jeho rôzne vlastnosti, pozrite si ju.

Dôležité tracky

Tracky sú rozdelené do viacerých skupín

• Mapping and sequencing: kvalita sekvencie zostavenej z čítaní, základné vlastnosti ako napr. GC%
• Genes and Gene Predictions: známe gény z rôznych databáz, automatické predikcie
• Phenotype and Literature: gény a iné miesta v genóme spomínané v literatúre alebo v databázach o ľudských chorobách a pod.
• mRNA and EST: osekvenované mRNA sekvencie
• Expression: údaje o expresii génov v rôznych tkanivách, napr. GTEx
• Regulation: merania o regulácii aktivity génov (väzobné miesta transkripčných faktorov, histónové modifikácie)
• Comparative genomics: porovnanie viacerých genómov
  • PhyloP - uroven konzerovanosti danej bazy len na zaklade jedneho stlpca zarovnania
  • Element Conservation/Conserved Elements vysledky z phyloHMM phastCons, ktory berie do uvahy aj okolite stlpce
  • multiz celogenómové zarovnania
  • nets and chains: zodpovedajúce si úseky rôznych genómov
• Variation: populacna genomika a polymorfizmy (viac v starsich verziach ludskeho genomu)
  • napr. v starsej verzii ludskeho genomu je aj trojuholnikovy graf linkage disequilibria
  • hg18, zapnite "HapMap LD Phased" na Full (cast Variation and Repeats)
• Repeats: casti genomu, ktore sa velakrat opakuju, ale aj segmentalne duplikacie

Verzie genómov, prechádzanie medzi verziami (liftOver)

• Vráťte sa na UCSC genome browser http://genome-euro.ucsc.edu/
• Pozrieme si niekoľko vecí týkajúcich sa sekvenovania a skladania genómov
• Hore v modrom menu zvoľte Genomes, časť Other
• Na ďalšej stránke zvoľte človeka a pomocou menu Human Assembly zistite, kedy boli pridané posledné dve verzie ľudského genómu (hg19 a hg38)
• Na tej istej stránke dole nájdete stručný popis zvolenej verzie genómu.
• Zapnite si tracky "Assembly" a "Gaps" a pozrite si región chr2:110,000,000-110,300,000 v hg19: [1] 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ĺžka aj tak nebola známa, nakoľko nebola osekvenovaná).
• Cez menu položku View, In other genomes si pozrite, ako zobrazený úsek vyzerá vo verzii hg38. Ako sa zmenila dĺžka z pôvodných 300kb?

BLAT, prechádzanie medzi genómami rôznych druhov

• Sekvencia uvedená nižšie vznikla sekvenovaním ľudskej mRNA
• Choďte na UCSC genome browser http://genome.ucsc.edu/ , na modrej lište zvoľte BLAT, zadajte túto sekvenciu a hľadajte ju v ľudskom genóme. Akú podobnosť (IDENTITY) má najsilnejší nájdený výskyt? Aký dlhý úsek genómu zasahuje? (SPAN). Všimnite si, že ostatné výskyty sú oveľa kratšie.
• V stĺpci ACTIONS si pomocou Details môžete pozrieť detaily zarovnania a pomocou Browser si pozrieť príslušný úsek genómu.
• V tomto úseku genómu si zapnite track Vertebrate net na full a kliknutím na farebnú čiaru na obrázku pre tento track zistite, na ktorom chromozóme sliepky sa vyskytuje homologický úsek.
• Skusme tu istu sekvenciu zarovnat ku genomu sliepky programom Blat: stlacte najprv na hornej modrej liste Genomes, zvolte Vertebrates a Chicken a potom na hornej liste BLAT. Do okienka zadajte tu istu sekvenciu. Akú podobnosť a dĺžku má najsilnejší nájdený výskyt teraz? Na ktorom je chromozóme?

Ľudská sekvencia pre BLAT

AACCATGGGTATATACGACTCACTATAGGGGGATATCAGCTGGGATGGCAAATAATGATTTTATTTTGAC
TGATAGTGACCTGTTCGTTGCAACAAATTGATAAGCAATGCTTTCTTATAATGCCAACTTTGTACAAGAA
AGTTGGGCAGGTGTGTTTTTTGTCCTTCAGGTAGCCGAAGAGCATCTCCAGGCCCCCCTCCACCAGCTCC
GGCAGAGGCTTGGATAAAGGGTTGTGGGAAATGTGGAGCCCTTTGTCCATGGGATTCCAGGCGATCCTCA
CCAGTCTACACAGCAGGTGGAGTTCGCTCGGGAGGGTCTGGATGTCATTGTTGTTGAGGTTCAGCAGCTC
CAGGCTGGTGACCAGGCAAAGCGACCTCGGGAAGGAGTGGATGTTGTTGCCCTCTGCGATGAAGATCTGC
AGGCTGGCCAGGTGCTGGATGCTCTCAGCGATGTTTTCCAGGCGATTCGAGCCCACGTGCAAGAAAATCA
GTTCCTTCAGGGAGAACACACACATGGGGATGTGCGCGAAGAAGTTGTTGCTGAGGTTTAGCTTCCTCAG
TCTAGAGAGGTCGGCGAAGCATGCAGGGAGCTGGGACAGGCAGTTGTGCGACAAGCTCAGGACCTCCAGC
TTTCGGCACAAGCTCAGCTCGGCCGGCACCTCTGTCAGGCAGTTCATGTTGACAAACAGGACCTTGAGGC
ACTGTAGGAGGCTCACTTCTCTGGGCAGGCTCTTCAGGCGGTTCCCGCACAAGTTCAGGACCACGATCCG
GGTCAGTTTCCCCACCTCGGGGAGGGAGAACCCCGGAGCTGGTTGTGAGACAAATTGAGTTTCTGGACCC
CCGAAAAGCCCCCACAAAAAGCCG

Table browser

Genome browser is nice for manual browsing but also allows programmers to download data

• each track based on one or several tables in an SQL database
• you can download genomic sequences and data from these tables [2]
• you can also write queries for a public SQL server [3] or create queries using Table browser forms (blue bar: Tools->Table browser)
• conversely, you can also display your own data in "custom tracks" of the browser

Table browser examples

• Basic type of query: e.g. export all genes in the part of the genome displayed in the browser
• Several output formats, e.g.:
  • sequence: file of protein or DNA sequences of these genes (various settings)
  • GTF: coordinates of genes and their exons
  • Hyperlinks to genome browser: list of genes with links to the browser for each gene
  • Instead of export we can get summary statistics (number of items, how much sequence they cover)
• More complex query, "intersection" of two tables: e.g. all genes that are more than 50% covered by simple repeats, filtering

Predbežné informácie k štátniciam

Na tejto stránke sú predbežné neoficiálne informácie k magisterskému štátnicovému predmetu Bioinformatika a strojové učenie pre školský rok 2016/17. Môže ešte dôjsť k nejakým zmenám, finálna verzia by sa v prebehu pár dní mala objaviť na stránke Katedry informatiky.

Úvod

Jedným z cieľov štátnic je uvedomiť si prepojenia medzi rôznymi predmetmi. Predmety v štátnicovom predmete Bioinformatika a strojové učenie navzájom súvisia, ale tieto súvislosti sa len v malej miere ukážu priamo v osnovách jednotlivých predmetov. Preto sme vybrali články z vedeckej literatúry, ktoré spájajú témy z viacerých predmetov a budú odrazovým mostíkom pre diskusiu na štátnych skúškach. Na štátnej skúške si vylosujete jeden z nižšie uvedených článov a trojicu otázok s ním súvisiacich. V prvej otázke bude vždy vašim cieľom sumarizovať hlavné výsledky článku a vysvetliť ich aj informatikom, ktorí nie sú priamo odborníkmi v oblasti zamerania článku. V tejto otázke očakávame cca 5-minútový prehľad článku s dôrazom na vysvetlenie potrebných pojmov a základných myšlienok článku, nie technických detailov. Druhá otázka bude z nižšie uvedených okruhov učiva. Môže ale nemusí súvisieť s témou článku. Tretia otázka bude podrobne vysvetliť niektorý technický detail článku (napr. nejakú časť algoritmu, zložitejšiu definíciu, dôkaz lemy, detaily experimentu a podobne). Po vylosovaní otázky dostanete k dispozícii vytlačený článok a budete mať aspoň hodinu času na prípravu, takže nie je potrebné tieto články poznať naspamäť. Pri príprave na štátnice vám odporúčame okrem opakovania si učiva v uvedených okruhoch pozrieť si aj uvedené články a s nimi súvisiacu terminológiu.

Články

• Apostolico A, Bock ME, Lonardi S, Xu X. Efficient detection of unusual words. Journal of Computational Biology. 2000 Feb 1;7(1-2):71-94. [4]

• Kanungo T, Mount DM, Netanyahu NS, Piatko CD, Silverman R, Wu AY. A local search approximation algorithm for k-means clustering. In Proceedings of the Eighteenth Annual Symposium on Computational Geometry 2002 (pp. 10-18). ACM. [5]

• Dowell RD, Eddy SR. Evaluation of several lightweight stochastic context-free grammars for RNA secondary structure prediction. BMC Bioinformatics. 2004 Jun 4;5(1):1. [6]

• L. Heng, R. Durbin (2009): Fast and accurate short read alignment with Burrows-Wheeler transform. Bioinformatics 25(14): 1754-1760 [7]

• Salzberg SL, Delcher AL, Kasif S, White O. Microbial gene identification using interpolated Markov models. Nucleic Acids Research. 1998 Jan 1;26(2):544-8. [8]

• Yoshinaga N, Kitsuregawa M. Polynomial to linear: Efficient classification with conjunctive features. In Proceedings of the 2009 Conference on Empirical Methods in Natural Language Processing: Volume 3 2009 (pp. 1542-1551). [9]

• Vermorel J, Mohri M. Multi-armed bandit algorithms and empirical evaluation. In European Conference on Machine Learning 2005 (pp. 437-448). [10]

• Glorot X, Bengio Y. Understanding the difficulty of training deep feedforward neural networks. In Artificial Intelligence and Statistics Conference 2010 (Vol. 9, pp. 249-256). [11]

Okruhy učiva

V zátvorke skratky súvisiacich predmetov: AOP: Aproximácia optimalizačných problémov; G: Genomika; IDZ: Integrácia dátových zdrojov; MBI: Metódy v bioinformatike; NS: Neurónové siete; PaŠ: Pravdepodobnosť a štatistika; SU: Strojové učenie; VPDŠ: Vybrané partie z dátových štruktúr

• Neurónové siete: viacvrstvový perceptrón, metóda spätného šírenia chyby, hlboké architektúry neurónových sietí, modely neurónových sietí s pamäťou, Hebbovské učenie (SU,NS)

• Modelovanie sekvenčných dát: Skryté Markovove modely, podmienená pravdepodobnosť a Bayesove vety, Viterbiho a dopredný algoritmus, príklady využitia v bioinformatike (hľadanie génov a profilové HMM), rekurentné neurónové siete, Hopfieldov model (MBI,PaŠ,NS)

• Klasifikačné modely: support vector machines, rozhodovacie stromy, náhodné lesy, bagging, boosting (SU)

• Regresia: lineárna a generalizovaná lineárna regresia, metóda najmenších štvorcov, štatistický model s normálnym rozdelením chýb, regularizácia (PaŠ,SU)

• Teória strojového učenia: štatistický model strojového učenia, výchylka vs. rozptyl, preučenie a podučenie, PAC učenie, odhady pomocou VC dimenzie (SU,NS)

• Strojové učenie bez učiteľa: zhlukovanie, samoorganizujúce sa zobrazenia, analýza hlavných komponentov, využitie na analýzu génovej expresie (SU,NS,MBI)

• Testovanie štatistických hypotéz: Fisherov exaktný test, Welchov t-test, Mann-Whitneyho U-test, Bonferroniho korekcia viacnásobného testovania, log likelihood ratio test, príklady použitia testov v bioformatike (PaŠ,IDZ,MBI)

• Stredná hodnota náhodnej premennej: linearita strednej hodnoty, Markovova a Čebyševova nerovnosť (PaŠ)

• Limitné vety teórie pravdepodobnosti: centrálna limitná veta, Moivrova-Laplaceova veta, slabý zákon veľkých čísel (PaŠ)

• Sekvenovanie DNA: technológie sekvenovania a ich charakteristiky (Sanger, Illumina, nanopórové sekvenovanie), skladanie genómov, deBruijnove grafy, RNA-seq (MBI,G)

• Fylogenetika a komparatívna genomika: metóda spájania susedov, metóda úspornosti, Jukes-Cantorov model a iné substitučné modely, pozitívna a negatívna selekcia a jej vplyv na evolúciu biologických sekvencií (MBI, G)

• Zarovnania a algoritmy na reťazcoch: lokálne a globálne zarovnávanie sekvencií, BLAST (jadrá zarovnaní), perfektné hešovanie, Bloomov filter, efektívna reprezentácia sekvencií (sufixové stromy a polia, Burrowsova–Wheelerova transformácia, FM index) (MBI,VPDŠ)

• Metóda maximálnej vierohodnosti: odhad parametrov rozdelenia, nevychýlené odhady parametrov, metóda maximálnej vierohodnosti na rekonštrukciu fylogenetických stromov, Felsensteinov algoritmus, EM algoritmus, trénovanie skrytých Markovových modelov, hľadanie sekvenčných motívov (PaŠ, MBI)

• Lineárne programovanie: lineárne a kvadratické programovanie, simplexová metóda, dualita, celočíselné lineárne programovanie a jeho využitie na riešenie ťažkých problémov v bioinformatike, využitie lineárneho programovania v aproximačných algoritmoch (deterministické zaokrúhľovanie, iterované zaokrúhľovanie, randomizované zaokrúhľovanie + derandomizácia, primárno-duálne metódy), semidefinitné programovanie a max-cut, využitie duality v support vector machines (kernelové metódy) (AOP, SU, MBI)

• Aproximovateľnosť: Zložitostné triedy aproximačných algoritmov, PCP veta a jej použitie, AP-redukcia, APX úplné problémy, aproximovateľnosť problému obchodného cestujúceho, polynomiálne aproximačné schémy a príklady PTAS algoritmov (AOP)

• Aplikácie formálnych jazykov: Knuth-Morris-Pratt algoritmus na hľadanie vzorky v texte, stochastické bezkontextové gramatiky, kovariačný model a rodiny RNA, Nussinovovej algoritmus (MBI, VPDŠ)

• Modely dátových štruktúr: amortizovaná zložitosť a potenciálová funkcia, I/O model a B-stromy, cache-oblivious model a statický binárny strom s van Emde Boas rozložením, úsporné dátové štruktúry (rank a select) (VPDŠ)

• Dátové štruktúry pre intervaly: range minimum query, lowest common ancestor, segmentové stromy, rozsahové stromy (VPDŠ)

Príklad otázok

Príklady otázok ku článku Glorot X, Bengio Y. Understanding the difficulty of training deep feedforward neural networks.

Otázka 1: Sumarizujte hlavné výsledky článku a vysvetlite, prečo je skúmaný problém dôležitý pre moderné strojové učenie (ak v odpovedi na túto otázku nevysvetlíte, čo je neurónová sieť, pravdepodobne sa vás spýtame na definíciu)

Otázka 2: Vysvetlite, čo je normalizovaná inicializácia a na obrázkoch 7 a 9 vysvetlite, aký má normalizovaná inicializácia vplyv na priebeh učenia. (bude k dispozícii projektor, na ktorom sa dajú obrázky z článku ukázať)

Otázka 3: Štatistický model strojového učenia, výchylka vs. rozptyl, preučenie a podučenie