1-BIN-301, 2-AIN-501 Methods in Bioinformatics, 2023/24

Introduction · Rules · Tasks and dates · Materials · Moodle
Quizzes can be found in Moodle.
Homework assignments and journal club papers can be found in Tasks and dates.
Exam rules, example questions and syllabus
Groups for journal club have each their own group in Moodle.


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áž...“)
 
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)
 

Verzia zo dňa a času 11:02, 19. november 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?