We found a match
Your institution may have rights to this item. Sign in to continue.
- Title
RNA motif search with data-driven element ordering.
- Authors
Rampášek, Ladislav; Jimenez, Randi M.; Lupták, Andrej; Vinař, Tomáš; Brejová, Broňa
- 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.
- Subjects
NON-coding RNA; NON-coding DNA; ALGORITHMS; HOMOLOGY (Biology); HELICES (Algebraic topology); APTAMERS; NUCLEOTIDE sequencing
- Publication
BMC Bioinformatics, 2016, Vol 17, p1
- ISSN
1471-2105
- Publication type
Article
- DOI
10.1186/s12859-016-1074-x