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, $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)