1-BIN-301, 2-AIN-501 Metódy v bioinformatike, ZS 2018/19

Úvod · Pravidlá · Termíny a zadania · Prednášky a poznámky · Facebook (oznamy a diskusie) (návod a pravidlá)
Zadania domácich úloh a články na journal club nájdete v časti Termíny a zadania.
Pozrite si ukážkové príklady na skúšku.
Rozpis skupín pre journal club je zverejnený.


CI11

Z MBI
Prejsť na: navigácia, hľadanie

RNA struktura

Opakovanie Nussinovovej algoritmu

Z cvičných príkladov na skúšku

  • Vyplnte maticu dynamického programovania (Nussinovovej algoritmus) pre nájdenie najväčšieho počtu dobre uzátvorkovaných spárovaných báz v RNA sekvencii GAACUUCACUGA (dovoľujeme len komplementárne páry A-U, C-G) a nakreslite sekundárnu štruktúru, ktorú algoritmus našiel.
 G A A C U U C A C U G A
 0 0 0 1 1 2 3 3 3 4 4 4  G
   0 0 0 1 2 2 2 2 3 4 4  A
     0 0 1 1 1 2 2 2 3 4  A
       0 0 0 0 1 1 1 2 3  C
         0 0 0 1 1 1 2 3  U
           0 0 1 1 1 2 3  U
             0 0 0 1 2 2  C
               0 0 1 1 1  A
                 0 0 1 1  C
                   0 0 1  U
                     0 0  G
                       0  A

Rozsirenia Nussinovovej algoritmu

  • lahke: kazdy par i,j musi mat vzdialenost |i-j|>=3 (RNA sa na kratsom useku nevie ohnut o 180 stupnov)
  • tazsie (bolo s hintom na skuske): chceme davat skore iba "stackovanym parom", t.j. ak i a j aj i+1 a j-1 su sparovane, dostaneme +1, osamotene pary nedostavaju ziadne skore. Úlohou je opäť pre danú sekvenciu nájsť dobre uzátvorkovanú štruktúru s maximálnym skóre.
    • pomocka: pouzijeme dve tabulky A a B, pričom A[i,j] obsahuje maximálne skóre pre podreťazec X[i...j] a B[i...j] obsahuje maximálne skóre pre podreťazec X[i...j], za predpokladu, že X[i] a X[j] sú spárované v štruktúre (táto hodnota je definovaná iba pre i a j, kde sú X[i] a X[j] komplementárne).

Stochasticke bezkontextove gramatiky

  • Ako asi funguje algoritmus, ktory hlada najpravdepodobnejsie odvodenie?
    • rozsirme Nussinovovej algoritmus o dalsi rozmer - neterminal, z ktoreho je podretazec X[i...j] vygenerovany
  • Je najpravdepodobnejsie odvodenie to iste ako najpravdepodobnejsia sekundarna struktura pri gramatike z prednasky?
    • S->aSu|uSa|cSg|gSc|aS|cS|gS|uS|Sa|Sc|Sg|Su|SS|epsilon
    • jednu strukturu vieme vyjadrit pomocou viacerych odvodeni, napr. v jednoduchej strukure nizsie vieme slucku ccg generovat zlava aj sprava (cS vs Su), tiez hocikde vieme spravit S->SS a potom jedno S znicit
acgccucgu
(((...)))
  • Viete zmenit gramatiku tak aby najlavejsie odvodenia zodpovedali 1 k 1 sekundarnym strukturam?
    • napr. S->aS|cS|gS|tS|aSuS|uSaS|cSgS|gScS|epsilon
    • vid clanok Dowell RD, Eddy SR. Evaluation of several lightweight stochastic context-free grammars for RNA secondary structure prediction. BMC bioinformatics. 2004 Jun 4;5(1):71. [1]