CI11: Rozdiel medzi revíziami

Aktuálna revízia z 14:54, 8. december 2022

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.

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 strukture nizsie vieme slucku ccu 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]