1-BIN-301, 2-AIN-501 Metódy v bioinformatike, ZS 2018/19

Úvod · Pravidlá · Termíny a zadania · Prednášky a poznámky · Facebook (oznamy a diskusie) (návod a pravidlá)
Zadania domácich úloh a články na journal club nájdete v časti Termíny a zadania.
Pozrite si ukážkové príklady na skúšku.
Rozpis skupín pre journal club je zverejnený.


CB09

Z MBI
Prejsť na: navigácia, hľadanie

Bezkontextové gramatiky

  • Na modelovanie štruktúry RNA sa používajú stochastické bezkontextové gramatiky (bude na ďalšej prednáške)
  • My si teraz ukážeme bezkontextové gramatiky, ktoré nemajú pravdepodobnosti
  • Zaviedol Noam Chomsky v lingvistike 50-te roky 20. storočia, tiež dôležité v informatike

Gramatika

  • Príklad: S->aSb, S->epsilon (píšeme aj skrátene S->aSb|epsilon)
  • Dva typy symbolov: terminály (malé písmená), neterminály (veľké písmená)
  • Pravidlá prepisujúce neterminál na reťazec terminálov a neterminálov (môže byť aj prázdny reťazec, ktorý označujeme epsilon)
  • Neterminál S je "štartovací"

Použitie gramatiky na generovanie reťazcov

  • Začneme so štartovacím neterminálom S
  • V každom kroku prepíšeme najľavejší neterminál podľa niektorého pravidla
  • Skončíme, keď nezostanú žiadne neterminály
  • Príklad: S->aSb->aaSbb->aaaSbbb->epsilon
  • Aké všetky slová vie táto gramatika generovať?
    • V tvare aa...abb...b s rovnakým počtom á-čok a b-čiek (informatici píšu a^{k}b^{k})

Cvičenia

  • Zostavte gramatiku na slova typu aa..abb..b kde acok je rovnako alebo viac ako bcok, a^{i}b^{j} pre i\geq j
    • S->aSb|aS|epsilon
  • Zostavte gramatiku pre slova toho isteho typu, kde acok je viac ako bcok, t.j. i>j
    • S->aSb|aT T->aT|epsilon (alebo S->aSb|aS|a)
  • Zostavte gramatiku pre dobre uzatvorkovane vyrazy zo zatvoriek (,),[,]. Napr. [()()([])] je dobre uzatvorkovany, ale [(]) nie je.
    • S->SS|(S)|[S]|epsilon
    • priklad odvedenia v tejto gramatike: S->[S]->[SS]->[SSS]->[(S)SS]->[()SS]->[()(S)S]->[()()S]->[()()(S)]->[()()([S])]->[()()([])]

Parsovanie retazca pomocou gramatiky: urcit, ako mohol byt retazec vygenerovany pomocou pravidiel

  • Gramatika pre dobre uzatvrokovane vyrazy nam pomoze urcit, ktora zatvorka patri ku ktorej: tie, ktore boli vygenerovane v jednom kroku

Dalsie cvicenia

  • Zostavte gramatiku na DNA palindromy, t.j. sekvencie, ktore zozadu po skomplementovani baz daju to iste, ako napr. GATC
    • S->gSc|cSg|aSt|tSa|epsilon
  • Vlasenky RNA s lubovolne dlhou sparovanou castou a 3 nesparovanymi nukleotidmi v strede
    • S->gSc|cSg|aSu|uSa|aaa|aac|aag|aau|...|uuu
  • Tazsi priklad: Zostavte gramatiku na slova s rovnakym poctom acok a bcok v lubovolnom poradi
    • S->epsilon|aSbS|bSaS
    • ako bude generovat aababbba?
    • preco vie vygenerovat vsetky take retazce?

Nadreprezentácia, Uniprot (cvičenie pri počítači)

Data o expresii ludskych genov v roznych tkanivach a podobne v UCSC genome browseri

  • Chodte na genome browser http://genome-euro.ucsc.edu/
  • Zvolte Tools->Gene Sorter, sort by nechajme Expression (GTEx), a do okienka search zadajme identifikator genu PTPRZ1
    • Dostane tabulku genov s podobnym profilom expresie ako PTPRZ1 (červená je vysoká expresia, zelená nízka)
    • Zoznam tychto genov v textovom formate najdete tu
  • http://biit.cs.ut.ee/gprofiler/ mena genov skopirujme do policka Query, stlacte g:Profile!
    • Ak by výpočet dlho trval, nájdete ho aj tu
    • Vo výslednej tabuľke je každý riadok jedna funkcna kategoria, v ktorej su geny s tymto profilom expresie nadreprezentovane, kazdy stlpec jeden gen.
    • V spodnej casti tabuly su aj asociacie k chorobam a k transkripcnym faktorom, ktore by mohli prislusne geny regulovat
  • Co by sme na zaklade nadreprezentovanych kategorii usudzovali o gene PTPRZ1?
  • Najdite tento gen v Uniprote (http://www.uniprot.org/), potvrdzuje nase domnienky?
    • O mnohých údajoch na stránke sme sa rozprávali na prednáške (GO kategórie, domény, sekundárna a 3D štruktúra)
    • na veľa miestach na stránke je uvedené aj odkiaľ jednotlivé údaje pochádzajú
    • Všimnime si Pfam domény a pozrime si ich stránku
  • Vratme sa do genome browsera, najdime si PTPRZ1 gen v genome [1]
  • V browseri su rozne tracky tykajuce sa expresie, napr. GTEx. Precitajte si, co je v tomto tracku zobrazene, zapnite si ho a pozrite si expresiu okolitych genov okolo PTPRZ1
  • Kliknite na gen v tracku UCSC known genes. V tabulke uvidite zase prehlad expresie v roznych tkanivach (podla GTEx)