1-BIN-301, 2-AIN-501 Methods in Bioinformatics

Website moved to https://fmfi-compbio.github.io/mbi/


CB09: Rozdiel medzi revíziami

Z MBI
Prejsť na: navigácia, hľadanie
(Vytvorená stránka „==Bezkontextové gramatiky== * Na modelovanie štruktúry RNA sa používajú stochastické bezkontextové gramatiky (bude na ďalšej prednáške) * My si teraz ukáž...“)
 
(→‎Cvicenie pri pocitaci)
 
(3 intermediate revisions by the same user not shown)
Riadok 20: Riadok 20:
  
 
'''Cvičenia'''
 
'''Cvičenia'''
−
* Zostavte gramatiku na slova typu aa..abb..b kde acok je rovnako alebo viac ako bcok, <math>a^ib^j</math> pre <math>i\ge j</math>
+
* Zostavte gramatiku na slová typu aa..abb..b kde á-čok je rovnako alebo viac ako b-čok, <math>a^ib^j</math> pre <math>i\ge j</math>
 
** S->aSb|aS|epsilon
 
** S->aSb|aS|epsilon
−
* Zostavte gramatiku pre slova toho isteho typu, kde acok je viac ako bcok, t.j. i>j
+
* 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)
 
** 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.
+
* Zostavte gramatiku pre dobre uzátvorkované výrazy zo zátvoriek (,),[,]. Napr. [()()([])] je dobre uzátvorkovaný, ale [(])  nie je.
 
** S->SS|(S)|[S]|epsilon
 
** S->SS|(S)|[S]|epsilon
−
** priklad odvedenia v tejto gramatike: S->[S]->[SS]->[SSS]->[(S)SS]->[()SS]->[()(S)S]->[()()S]->[()()(S)]->[()()([S])]->[()()([])]
+
** príklad odvodenia 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
+
'''Parsovanie reťazca''' pomocou gramatiky: určiť, ako mohol byt reťazec vygenerovaný pomocou pravidiel
−
* Gramatika pre dobre uzatvrokovane vyrazy nam pomoze urcit, ktora zatvorka patri ku ktorej: tie, ktore boli vygenerovane v jednom kroku
+
* 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
  
−
'''Dalsie cvicenia'''
+
'''Ďalšie cvičenia'''
 
* Zostavte gramatiku na DNA palindromy, t.j. sekvencie, ktore zozadu po skomplementovani baz daju to iste, ako napr. GATC
 
* 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
 
** S->gSc|cSg|aSt|tSa|epsilon
Riadok 41: Riadok 41:
 
** ako bude generovat aababbba?
 
** ako bude generovat aababbba?
 
** preco vie vygenerovat vsetky take retazce?
 
** 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 [http://compbio.fmph.uniba.sk/vyuka/mbi-data/cb08/zoznam_genov.txt 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 [http://compbio.fmph.uniba.sk/vyuka/mbi-data/cb08/g_Profiler.html 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 [http://genome-euro.ucsc.edu/cgi-bin/hgTracks?db=hg38&position=chr7%3A121873089-122062036]
 
−
* 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)
 

Aktuálna revízia z 13:30, 3. december 2020

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?
Zdroj: „https://compbio.fmph.uniba.sk/vyuka/mbi/index.php?title=CB09&oldid=2501“