Meno:Ladislav
Priezvisko:Rampášek
Názov:Computational Complexity and Practical Implementation of RNA Motif Search
Vedúci:Mgr. Bronislava Brejová PhD.
Rok:2012
Blok:INF
Kľúčové slová:RNA motív, vyhľadávanie v texte, NP-úplnosť, prehľadávanie s návratom, RNArobo
Abstrakt:V tejto práci sme sa venovali problému vyhľadávania štrukturálnych RNA motívov. Naša práca je motivovaná výskumom Prof. Andreja Luptáka [Ruminski et al., 2010] v oblasti kataliticky aktívnych RNA, tzv. ribozýmov. Táto práca nadväzuje na našu pred- chádzajúcu prácu [Rampášek, 2010], v ktorej sme navrhli nový algoritmus na vyhľadávanie RNA motívov založený na publikovanom prehľadávaní s návratom [Gautheret et al., 1990]. Náplňou tejto diplomovej práce sú tri hlavné výsledky. Za prvé, dokázali sme NP-úplnosť problému vyhľadávania RNA štrukturálnych motívov pomocou redukcie z problému ONE- IN-THREE 3SAT. Ďalej, navrhli sme adaptívnu metódu pre usporiadanie elementov v prehľadávaní s návratom použitom v RNArobo. Túto metódu sme implementovali v nástroji RNArobo 2.0. Táto zmena priniesla značné zrýchlenie. Pre zložité motívy je tak RNArobo 2.0 rýchlejší ako zaužívané nástroje RNAbob [Eddy, 1996] a RNAMotif [Macke et al., 2001]. Na záver, vyvinuli sme nástroje, ktoré umožňujú ohodnotiť nájdené výskyty daného motívu na základe odhadu stability ich štruktúry. Celkovo naša práca vyústila v sadu nástrojov, ktoré umožňujú automatizovaný postup využiteľný pre objavovanie nových výskytov funkčných RNA, podobný postupu navrhnutému v [Jimenez et al., 2012].

Súbory diplomovej práce:

dipl_Rampasek.pdf
rnarobo2.0.0.zip