Exam

Pokyny ku skúške

Hlavná časť skúšky je písomná:

• Treba získať aspoň polovicu bodov
• Zadanie a odovzdávanie v Moodli, čas 3 hodiny
• MS Teams: na začiatku skúšky online stretnutie s pokynmi, počas skúšky píšte vyučujúcim do súkromného čet-u otázky, sledujte prípadné oznamy na online stretnutí počas skúšky
• Môžete odovzdať pdf vytvorené v editore alebo písať na papier, odfotiť, konvertovať do pdf.
• Každý príklad sa odovzdáva zvlášť

Povolené pomôcky:

• Materiály na stránke predmetu (poznámky, prezentácie, skriptá)
• Vaše vlastné poznámky z predmetu
• Textové a grafické editory na zapisovanie riešenia (nepoužívať funkcie nesúvisiace priamo s editovaním)
• Softvér na digitalizáciu papierových riešení
• Jednoduchá kalkulačka (hardvér alebo softvér)
• MS Teams len na komunikácii s vyučujúcimi
• Moodle len na čítanie zadaní a odovzdanie riešení

Zakázané pomôcky:

• Komunikácia s inými osobami než vyučujúcimi
• Iné webstránky
• Iný softvér (napr. špecializované bioinformatické programy)

Ústna skúška

• Videohovor cez MS Teams
• Koná sa po písomnej časti, vypíšeme termíny počas niekoľkých dní
• Budeme diskutovať o odovzdanej písomke
• Mali by ste vedieť podrobne zdôvodniť vaše odpovede
• Kvalita ústnej časti môže mierne ovplyvniť body zo skúšky
• Ak nebudeme vedieť vysvetliť vaše odpovede, môžeme vás hodnotiť Fx

Opravný termín skúšky bude mať buď rovnakú formu ako riadny alebo bude čisto ústny.

Sylabus a ukážky príkladov

Nižšie uvádzame pre každý okruh učiva stručný zoznam najdôležitejších pojmov, ktoré by biológovia aj informatici mali poznať.

Navyše uvádzame aj niekoľko jednoduchých príkladov. Za príklady tohto typu bude možné pre biológov aj informatikov na skúške získať približne polovicu bodov. Samozrejme, na skúške nepoužijeme všetky tieto príklady a konkrétne reťazce, čísla, stromy a pod. budú iné.

Ostatné príklady na skúške budú prekvapením. V minulosti sa vyskytli:

• Krátke príklady na pochopenie základných pojmov
• Pre informatikov: navrhnite/modifikujte algoritmus alebo model
• Pre biológov: usudzovanie z konkrétnych výsledkov, výber metódy pre daný problém

Sekvenovanie, zostavovanie genómov

Sekvenovanie DNA a jeho využitie, čítanie (read), spárované čítania, kontig, problém najkratšieho spoločného nadslova, de Bruijnove grafy

• Nájdite najkratšie spoločné nadslovo reťazcov GACAATAA, ATAACAC, GTATA, TAATTGTA.
• Zostavte deBruijnov graf pre k=2 (vrcholy budú dvojice) a čítania CCTGCC, GCCAAC

Zarovnávanie sekvencií

Problém lokálneho a globálneho zarovnania dvoch sekvencií, jeho riešenie pomocou dynamického programovania, skórovacia matica a jej pravdepodobnostný význam, štatistická významnosť (E-value, P-value), heuristické hľadanie lokálnych zarovnaní (BLAST), celogenómové a viacnásobné zarovnania

• Vyplňte maticu dynamického programovania pre lokálne (resp. globálne) zarovnanie reťazcov TACGT a CAGGATT, pričom zhodu skórujeme ako +3, nezhodu -1, medzeru -2. Napíšte aj optimálne zarovnanie, ktoré ste takto našli.
• Spočítajte skóre nižšie uvedeného zarovnania, pričom použijete skórovaciu maticu uvedenú nižšie, začatie medzery -5, rozšírenie medzery o jednu ďalšiu bázu -2. Nájdite globálne zarovnanie s vyšším skóre pre tieto dve sekvencie (netreba nájsť optimálne zarovnanie; pri hľadaní môžete použiť ľubovoľný postup alebo úvahu) a spočítajte aj skóre vášho nového zarovnania.

Zarovnanie:                             Matica:
ATAGTTTAA                                 A   C   G   T
A-GGG--AA                             A   2  -2  -1  -2
                                      C  -2   1  -2  -1    
                                      G  -1  -2   1  -2
                                      T  -2  -1  -2   2

• Uvažujme BLASTn, ktorý začína z jadier veľkosti w=3. Koľko jadier nájde pri porovnávaní sekvencií GATTACGGAT a CAGGATT? Ktoré to budú?

Hľadanie génov

Gén, exón, intrón, mRNA, zostrih a alternatívny zostrih, kodón, genetický kód, skrytý Markovov model (HMM), jeho stavy, pravdepodobnosti prechodu a emisie, použitie HMM na hľadanie génov

• Pre model na strane 16 prednášky o hľadaní génov (bol by v zadaní) spočítajte pravdepodobnosť vygenerovania báz AGT a stavov modrý,červený,modrý.

Evolúcia a komparatívna genomika

Fylogenetický strom (zakorenenený a nezakorenený), metóda maximálnej úspornosti (parsimony), metóda spájania susedov (neighbor joining), metóda maximálnej vierohodnosti (maximum likelihood), Jukes-Cantorov model substitúcií a zložitejšie substitučné matice, homológ, paralóg, ortológ, detekcia pozitívneho a negatívneho výberu, fylogenetické HMM, likelihood ratio test

• Na strome nižšie nájdite najúspornejšie ancestrálne znaky pre stĺpec zarovnania TTAAA (v poradí glum, hobit, človek, elf, ork). Odpoveď môžete spočítať ľubovoľným spôsobom.

Glum   ----|
           |----|
Hobit  ----|    |----|
                |    |
Človek ---------|    |
                     |---
Elf --------|        |
            |--------|
Ork --------|

• Nájdite najúspornejší strom pre zarovnanie uvedené nižšie. Aká je jeho cena (koľko mutácií je nutných na vysvetlenie týchto sekvencií)? Odpoveď môžete spočítať ľubovoľným spôsobom.

vtáčik biely       ACAACGTCT
vtáčik čierny      TCTGAATCA
vtáčik sivý        TGTGAAAGA
vtáčik modrý       ACTACGTCT
vtáčik zelený      TGTGAAAGA

• Uvažujme maticu vzdialeností uvedenú nižšie. Ktorú dvojicu vrcholov spojí metóda spájania susedov ako prvú a aká bude nová matica po spojení?

                biely   čierny  sivý   modrý
vtáčik biely      0       5       7       4
vtáčik čierny     5       0       8       5
vtáčik sivý       7       8       0       5
vtáčik modrý      4       5       5       0

• Uvažujme strom pre gluma, hobita atď uvedený v príklade vyššie (bol by v zadaní), pričom každá hrana má rovnakú dĺžku a pravdepodobnosť každej mutácie na jednej hrane je 0.1 (t.j. napr. Pr(C|A,t)=0.1) a teda pravdepodobnosť zachovania tej istej bázy je 0.7, pravdepodobnosť každej bázy v koreni je 0.25. Aká je pravdepodobnosť, že v listoch dostaneme TTAAA a vo vnútorných vrcholoch samé Áčka? Nájdite priradenie ancestrálnych báz vo vnútorných vrcholoch, ktoré má väčšiu pravdepodobnosť a spočítajte, aká tá pravdepodobnosť je (nemusíte nájsť najlepšie možné priradenie).

Expresia génov, regulácia, motívy

Určovanie génovej expresie pomocou microarray alebo sekvenovaním RNA-seq, hierarchické zhlukovanie, klasifikácia, reprezentácia sekvenčných motívov (väzobné miesta transkripčných faktorov) ako konsenzus, regulárny výraz a PSSM, hľadanie nových motívov v sekvenciách, consensus pattern problem, hľadanie motívu pomocou pravdepodobnostných modelov (EM algoritmus)

• Uvažujme microarray experimenty pre 5 génov. Medzi každými dvomi génmi sme spočítali vzdialenosť ich profilov expresie a dostali sme tabuľku vzdialeností uvedenú nižšie. Nájdite hierarchické zhlukovanie týchto génov, pričom vzdialenosť medzi dvoma zhlukmi (clustrami) bude vzdialenosť najbližších génov v nich. Uveďte aj v akom poradí ste jednotlivé zhluky tvorili.

         A    B    C    D    E
gén A    0   0.6  0.1  0.3  0.7    
gén B   0.6   0   0.5  0.5  0.4
gén C   0.1  0.5   0   0.6  0.6
gén D   0.3  0.5  0.6   0   0.8
gén E   0.7  0.4  0.6  0.8   0

• Uvažujte motív reprezentovaný profilom (skórovaciou maticou, PSSM) uvedenou nižšie. Spočítajte skóre reťazca GGAG. Ktorá sekvencia dĺžky 4 bude mať najmenšie a ktorá najväčšie skóre?

A   -3    3   -2   -2
C   -2   -2    1   -2
G    0   -2   -1    3
T    1   -1    1   -2

• Nájdite všetky výskyty regulárneho výrazu TA[CG][AT]AT v sekvencii GACGATATAGTATGTACAATATGC.

Proteíny

Primárna, sekundárna a terciálna štruktúra proteínov, proteínové domény a rodiny, reprezentovanie rodiny pravdepodobnostným profilom a profilovým HMM, protein threading, gene ontology.

• Zostavte profil (PSSM) pre zarovnanie sekvencií uvedené nižšie, pričom predpokladáme, že v celej databáze A tvorí 60% a G 40% všetkých sekvencií (iné aminokyseliny neuvažujeme). Použite prirodzený logaritmus (ln) a pseudocount 1.

AAGA
GAGA
GAAA
GGAG
GGAA

RNA

Sekundárna štruktúra RNA, pseudouzol a dobre uzátvorkovaná štruktúra, Nussinovovej algoritmus, minimalizácia energie, stochastické bezkontextové gramatiky, kovariančné modely.

• Doplňte chýbajúce hodnoty za otázniky v matici dynamického programovania (Nussinovovej algoritmus) pre nájdenie najväčšieho počtu dobre uzátvorkovaných spárovaných báz v RNA sekvencii GAACUAUCUGA (dovoľujeme len komplementárne páry A-U, C-G) a nakreslite sekundárnu štruktúru, ktorú algoritmus našiel.

 0 0 0 1 1 2 2 3 3 ? ?
   0 0 0 1 1 2 2 3 3 ?
     0 0 1 1 2 2 2 3 3
       0 0 1 1 1 1 2 3
         0 1 1 ? 1 2 3
           0 1 1 1 2 2
             0 0 0 1 2
               0 0 1 1
                 0 0 1
                   0 0
                     0

• Uvažujme RNA sekvenciu dĺžky 27, ktorá má v sekundárnej štruktúre spárované komplementárne bázy na pozíciách: (2,23), (3,22), (4,21), (5,13), (6,12), (8,16), (9,15), (10,14), (18,26) a (19,25). Koľko najmenej párov z tohto zoznamu musíme odstrániť, aby sme dostali štruktúru bez pseudouzlov? Ktoré páry to budú?

• Uvažujme sekvenciu RNA ACUGAGUCCAAGG, ktorá má v sekundárnej štruktúre spárované bázy na pozíciách (1,7), (2,6), (3,5), (8,13) a (9,12). (Pozície číslujeme od 1.) (Táto RNA je uvedená ako príklad na strane 12 prednášky o RNA.) Ukážte akou postupnosťou pravidiel by sme ju mohli odvodiť v gramatike uvedenej nižšie tak, aby spárované bázy boli vždy vytvorené v jednom kroku odvodenia.
  • Gramatika: S->aSu|uSa|cSg|gSc|aS|cS|gS|uS|Sa|Sc|Sg|Su|SS|epsilon
  • Iný príklad gramatiky: S->aSu|uSa|cSg|gSc|TS|ST|SS|epsilon; T->aT|cT|gT|tT|epsilon

Populačná genetika

Polymorfizmus, SNP, alela, homozygot, heterozygot, rekombinácia, frekvencia polymorfizmu ako markovovský reťazec, náhodný genetický drift, väzbová nerovnováha (linkage disequilibrium), mapovanie asociácií, LD blok, subpopulácia.

• Pre dvojice SNPov, ktorých tabuľky sú uvedené nižšie, určite, či môžeme štatisticky vylúčiť hypotézu, že sú v stave väzbovej rovnováhy (LE, linkage equilibrium) pri hladine významnosti p=0.05, resp. $\chi ^{2}>3.841$. Pre každú dvojicu spočítajte veličinu $\chi ^{2}$.

    Q   q              Q  q             Q  q
P  100 200          P 10  20         P  1  2
p  300 200          p 30  20         p  3  2

Ďalšie dôležité znalosti z cvičení pre informatikov

(iba informatická časť skúšky)

• Pokročilejšie ukážky dynamického programovania (proteíny MS/MS, varianty zarovnávania sekvencií, varianty Nussinovovej algoritmu)
• BLAST, MinHashing
• Algoritmy pre použitie HMM (Viterbiho, dopredný)
• Felsensteinov algoritmus
• Celočíselné lineárne programovanie
• EM algoritmus na hľadanie motívov

Ďalšie dôležité znalosti z cvičení pre biológov

(iba biologická časť skúšky)

• Interpretácia dotplotov
• Interpretácia fylogenetických stromov, bootstrap, zakorenenie
• Interpretácia vizualizácií z UCSC genome browsera
• Ukážky rôznych bioinformatických programov, súvis ich nastavení a výsledkov s pojmami z prednášky
• Analýza nadreprezentácie, multiple testing correction, K-means clustering