1-BIN-301, 2-AIN-501 Methods in Bioinformatics, 2021/22

Introduction · Rules · Tasks and dates · Materials · Moodle · Discussion
Cvičenia vo štvrtok o 14:00 sú určené pre študentov BIN, INF, mINF, mAIN, DAV. Cvičenia vo štvrtok o 17:20 sú pre študentov z PriFUK a z fyzikálnych odborov. Obidvoje cvičenia sa budú konať už v prvom týždni semestra.


CB09

Z MBI
Revízia z 14:30, 3. december 2020; Brona (Diskusia | príspevky)

(rozdiel) ← Staršia verzia | Aktuálna úprava (rozdiel) | Novšia verzia → (rozdiel)
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 slová typu aa..abb..b kde á-čok je rovnako alebo viac ako b-čok, a^{i}b^{j} pre i\geq j
    • S->aSb|aS|epsilon
  • Zostavte gramatiku pre slová toho istého typu, kde á-čok je viac ako b-čok, t.j. i>j
    • S->aSb|aT T->aT|epsilon (alebo S->aSb|aS|a)
  • Zostavte gramatiku pre dobre uzátvorkované výrazy zo zátvoriek (,),[,]. Napr. [()()([])] je dobre uzátvorkovaný, ale [(]) nie je.
    • S->SS|(S)|[S]|epsilon
    • príklad odvodenia v tejto gramatike: S->[S]->[SS]->[SSS]->[(S)SS]->[()SS]->[()(S)S]->[()()S]->[()()(S)]->[()()([S])]->[()()([])]

Parsovanie reťazca pomocou gramatiky: určiť, ako mohol byt reťazec vygenerovaný pomocou pravidiel

  • Gramatika pre dobre uzátvorkované výrazy nám pomôže určiť, ktorá zátvorka patrí ku ktorej: tie, ktoré boli vygenerované v jednom kroku

Ďalšie cvičenia

  • 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?