Computational Biology
@ Comenius University in Bratislava

Ladislav Rampášek. Computational Complexity and Practical Implementation of RNA Motif Search. Master thesis, Comenius University in Bratislava, 2012. Supervised by Broňa Brejová.

Download preprint: 12rampasekth.pdf, 1575Kb

Download from publisher: not available

Related web page: not available

Bibliography entry: BibTeX

Abstract:

    In this thesis we study the RNA structural motif search problem. Our work is mo-
tivated by the research of Prof. Andrej Lupták in the area of self-cleaving ribozymes
[Ruminski et al., 2010]. This thesis follows our previous work [Rampásek, 2010], where
we proposed a new algorithm for RNA motif search based on a published backtrack-
ing method [Gautheret et al., 1990]. Here, we present three main results. Firstly, we
have proven the RNA structural motif search problem to be NP-complete by a reduction
from ONE-IN-THREE 3SAT. Secondly, we have devised a data-driven element ordering
strategy for the backtracking search of RNArobo. We have implemented this strategy in
RNArobo 2.0. This change has considerably improved the running time, and for complex
motifs RNArobo 2.0 outperforms other search tools, RNAbob [Eddy, 1996] and RNAMotif
[Macke et al., 2001]. Finally, we have developed tools for post-processing RNArobo search
results by ranking them according to their estimated structural stability.
    Overall our work resulted in a practical computational pipeline, similar to that pro-
posed in [Jimenez et al., 2012], that can be used to discover new homologs of functional
RNAs.
Keywords: RNA motif, pattern matching, NP-completeness, backtracking, RNArobo