Computational Biology
@ Comenius University in Bratislava

Ladislav Rampasek, Randi M. Jimenez, Andrej Luptak, Tomas Vinar, Brona Brejova. RNA motif search with data-driven element ordering. BMC Bioinformatics, 17(1):216. 2016.

Download preprint: not available

Download from publisher: http://dx.doi.org/10.1186/s12859-016-1074-x

Related web page: http://compbio.fmph.uniba.sk/rnarobo/

Bibliography entry: BibTeX

Abstract:

BACKGROUND: In this paper, we study the problem of RNA motif search in long
genomic sequences. This approach uses a combination of sequence and structure
constraints to uncover new distant homologs of known functional RNAs. The problem
is NP-hard and is traditionally solved by backtracking algorithms. RESULTS: We
have designed a new algorithm for RNA motif search and implemented a new motif
search tool RNArobo. The tool enhances the RNAbob descriptor language, allowing
insertions in helices, which enables better characterization of ribozymes and
aptamers. A typical RNA motif consists of multiple elements and the running time 
of the algorithm is highly dependent on their ordering. By approaching the
element ordering problem in a principled way, we demonstrate more than 100-fold
speedup of the search for complex motifs compared to previously published tools. 
CONCLUSIONS: We have developed a new method for RNA motif search that allows for 
a significant speedup of the search of complex motifs that include pseudoknots.
Such speed improvements are crucial at a time when the rate of DNA sequencing
outpaces growth in computing. RNArobo is available at
http://compbio.fmph.uniba.sk/rnarobo .