title: RNA motif search with data-driven element ordering.
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 .
authors.affiliation: Department of Computer Science, University of Toronto, Toronto, M5R 3G4, ON, Canada.|Department of Pharmaceutical Sciences, Chemistry, and Molecular Biology and Biochemistry, University of California, Irvine, 2141 Natural Sciences 2, Irvine, 92697, CA, USA.|Faculty of Mathematics, Physics, and Informatics, Comenius University, Mlynská dolina, Bratislava, 842 48, Slovakia.
authors.forename: Ladislav
authors.initials: L
authors.lastname: Rampášek
authors.affiliation: Department of Pharmaceutical Sciences, Chemistry, and Molecular Biology and Biochemistry, University of California, Irvine, 2141 Natural Sciences 2, Irvine, 92697, CA, USA.
authors.forename: Randi M
authors.initials: RM
authors.lastname: Jimenez
authors.affiliation: Department of Pharmaceutical Sciences, Chemistry, and Molecular Biology and Biochemistry, University of California, Irvine, 2141 Natural Sciences 2, Irvine, 92697, CA, USA. aluptak@uci.edu.
authors.forename: Andrej
authors.initials: A
authors.lastname: Lupták
authors.affiliation: Faculty of Mathematics, Physics, and Informatics, Comenius University, Mlynská dolina, Bratislava, 842 48, Slovakia.
authors.forename: Tomáš
authors.initials: T
authors.lastname: Vinař
authors.affiliation: Faculty of Mathematics, Physics, and Informatics, Comenius University, Mlynská dolina, Bratislava, 842 48, Slovakia. brejova@dcs.fmph.uniba.sk.
authors.forename: Broňa
authors.initials: B
authors.lastname: Brejová
mesh_terms: D000465:Algorithms; D019277:Entropy; D006801:Humans; D059372:Nucleotide Motifs; D012313:RNA / Q000737:chemistry*; D017423:Sequence Analysis, RNA / Q000379:methods*
chemical_list: D012313:RNA
keywords: Entropy; Pseudoknot; RNA motif search; Search order