Fast prediction of RNA-RNA interaction

In this paper we present a novel algorithm to accurately predict the minimum free energy structure of RNA-RNA interaction under the most general type of interactions studied in the literature. Moreover, we introduce a fast heuristic method to predict the specific (multiple) binding sites of two interacting RNAs.We verify the performance of our algorithms for joint structure and binding site prediction on a set of known interacting RNA pairs. Experimental results show our algorithms are highly accurate and outperform all competitive approaches.Regulatory non-coding RNAs (ncRNAs) play an important role in gene regulation. Studies on both prokaryotic and eukaryotic cells show that such ncRNAs usually bind to their target mRNA to regulate the translation of corresponding genes. Many regulatory RNAs such as microRNAs and small interfering RNAs (miRNAs/siRNAs) are very short and have full sequence complementarity to the targets. However some of the regulatory antisense RNAs are relatively long and are not fully complementary to their target sequences. They exhibit their regulatory functions by establishing stable joint structures with target mRNA initiated by one or more loop-loop interactions.In this paper we present an efficient method for the RNA-RNA interaction prediction (RIP) problem with multiple binding domains. Alkan et al. [1] proved that RIP, in its general form, is an NP-complete problem and provided algorithms for predicting specific types of interactions and two relatively simple energy models - under which RIP is polynomial time solvable. We focus on the same type of interactions, which to the best of our knowledge, are the most general type of interactions considered in the literature; however the energy model we use is the joint structure energy model recently presented by Chitsaz et al. [2] which is more general than the one used by Alkan et al.In what follows below, we first describe a combinatorial algorithm to compute the minimum free energy joint str