CB09

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, pre
- 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?

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)