Agile inteRNA is the sparsified version of inteRNA proposed by Salari et al. (RECOMB 2010). Applying sparsification techniques reduces the complexity of the original algorithm, for two RNAs of length maximum n, from O(n^6) time and $O(n^4) space to O(n^4 ψ(n)) time and O(n^2 ψ(n)+n^3) space for some function ψ(n), which is linear to n in practice. Agile inteRNA uses the new interaction energy model introduced by Chitsaz et al. (ISMB/ECCB 2009).

**Sequences:**The input RNA sequences, target mRNA and antisense RNA, in two FASTA format files.

- Predicted joint structure with the minimum free energy is stored in a CONNECT (.ct) format file.
- Files '.out' and '.seq' are auxilary files for displaying the predicted interaction structure. Run 'java RNAConsule .seq .out ./' and checkout the interaction in 'graph.jpg'. Note that java should be from sun-java-jdk package.

** inteRNA** is the first program that aims to compute the joint structure prediction of two given RNA sequences through minimizing their total free energy, which, is a function of the topology of the joint structure. The algorithmic foundations of inteRNA were introduced by Alkan et al.(RECOMB 2005). *inteRNA* aims to minimize the joint free energy under a number of energy models with growing complexity. The default energy model is based mostly on stacked pair energies given by Mathews et al.(J. Mol. Biol. 1999) - the free energy model employed by Mfold. Because there is very little thermodynamic information on kissing loop sequences in the literature, inteRNA employs the approach used by Rivas and Eddy(J. Mol. Biol. 1999) to differentiate the thermodynamic parameters of "external" bonds from the "internal" bonds.

- A text file that contains the base pair information of the joint secondary structure. Here, each line denotes either a base pair with nucleotide indices or a gap. A base pair is represented by a quadruple (Sequence, Position, Sequence, Position) where Sequence can be either S or R (representing the first and the second sequences respectively) and Position is the base index. Gaps are represented with (S,"Gap",R,i) in sequence R and represented with (S,i,R,"Gap") in sequence S, where i is the index of the free nucleotide.
- A JPEG image file that can help visualize the joint secondary structure prediction of the input RNAs. The input RNAs are represented by their sequences only. Internal bonds are represented by blue arcs and external bonds are represented by red lines.
- A text file reporting the calculated free energy of the predicted joint secondary structure.

**Stacked Pair Model: **This model uses stacking pair energy functions both externally and internally. A **gap penalty** parameter is used to penalize opening a gap. Due to high computational complexity and memory requirements of this model, inteRNA can not accept inputs with large (>200nt) sequence lengths with this setting.

**Loop Model:** It has been observed that RNA molecules mostly preserve their independent secondary structure when they interact with other RNA. Interactions thus typically occur between kissing hairpin loops. The loop model first predicts the secondary structure of each RNA sequence independently (simply through the standard thermodynamic model or through alteRNA); it then identifies all independent subsequences of each RNA structure: these are substructures (each implied by a basepair) whose sequence length is less than **maximum subsequence length**. It then computes the joint secondary structure that can be established between each pair of independent subsequences (one subsequence from each RNA) and the free energy of this joint structure. Finally, it finds the set of independent subsequence pairs which can co-exist and minimize the total free energy of the overall secondary structure.

"Time and space efficient RNA-RNA interaction prediction via sparse folding",

Raheleh Salari, Mathias Mohl, Sebastian Will, S. Cenk Sahinalp, and Rolf Backofen.

RECOMB'10, Research in Computational Molecular Biology, (2010).

"RNA-RNA Interaction Prediction and Antisense RNA Target Search",

Can Alkan, Emre Karakoç, Joe Nadeau, S. Cenk Sahinalp, Kaizhong Zhang.

RECOMB'05, Research in Computational Molecular Biology, pp. 152-171, Cambridge, Ma. (2005).

"RNA-RNA Interaction Prediction and Antisense RNA Target Search",

C. Alkan, E. Karakoc, J. Nadeau, C. Sahinalp, K. Zhang.

Journal of Computational Biology, March 2006, Vol.13,No.2:267-283 (2006).