Rnall: an efficient algorithm for predicting RNA local secondary structural landscape in genomes.

Abstract

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.