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
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