Rnall: an efficient algorithm for predicting RNA local secondary structural landscape in genomes.
BACKGROUND
The information of RNA local secondary structures (LSSs) can help retrieve biologically important motifs and study functions of RNA molecules. Most of the current RNA secondary structure prediction tools are not suitable for RNA LSS prediction on the genome scale due to high computational complexity.


METHODS
We developed a new computer package Rnall based on a dynamic programming technique, which scans an RNA sequence with a sliding window and extracts all RNA LSSs with sizes no larger than the window size using the nearest neighbor thermodynamic parameters. The worst case running time of Rnall is O(W(3)L), where W is the window size and L is the query sequence length. In practice we observed a running time of O(W(2)L). We further introduced the concept of energy landscape for illustrating RNA LSS, which may facilitate RNA motif mining on the genomic scale.


RESULTS
Rnall shows better prediction accuracy than two other prediction tools Lfold and Quickfold. Rnall is also applied to scan for RNA LSSs in three genomes, and the prediction maps well with known RNA motifs.


CONCLUSIONS
Rnall is designed for RNA LSS prediction and together with the energy landscape, it has unique features that could be used for RNA structural motif mining. Rnall is freely available for download at http://digbio.missouri.edu/~wanx/Rnall or http://www.sysbio.muohio.edu/Rnall.
Wan
Xiu-Feng
XF
Department of Computer Science and Christopher S. Bond Life Sciences Center, University of Missouri - Columbia, Columbia, MO 65211, USA. wanx@muohio.edu
Lin
Guohui
G
Xu
Dong
D
D000465:Algorithms; D001483:Base Sequence; D002874:Chromosome Mapping / Q000379:methods*; D003198:Computer Simulation; D008956:Models, Chemical; D008958:Models, Molecular; D008969:Molecular Sequence Data; D009690:Nucleic Acid Conformation; D012313:RNA / Q000737:chemistry* / Q000235:genetics*; D017423:Sequence Analysis, RNA / Q000379:methods*; D012984:Software
D012313:RNA