Fast Prediction of RNA-RNA Interaction

Background: Regulatory antisense RNAs are a class of ncRNAs that regulate gene expression by prohibiting thetranslation of an mRNA by establishing stable interactions with a target sequence. There is great demand forefficient computational methods to predict the specific interaction between an ncRNA and its target mRNA(s).There are a number of algorithms in the literature which can predict a variety of such interactions - unfortunatelyat a very high computational cost. Although some existing target prediction approaches are much faster, they arespecialized for interactions with a single binding site.Methods: In this paper we present a novel algorithm to accurately predict the minimum free energy structure ofRNA-RNA interaction under the most general type of interactions studied in the literature. Moreover, we introducea fast heuristic method to predict the specific (multiple) binding sites of two interacting RNAs.Results: We verify the performance of our algorithms for joint structure and binding site prediction on a set ofknown interacting RNA pairs. Experimental results show our algorithms are highly accurate and outperform allcompetitive approaches.