Agile inteRNA

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).

Source Code

inteRNA version 3.3

Help

Run 'inteRNA' with '-h' or '--help' option.

Input

Output



inteRNA

Sequence(in FASTA format)

Or load sequence from file:

Algorithm:
Gap Penalty(>=0):
Max. Substructure Length ( <100):


Or get results via email:


Summary

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.

Input and Output

inteRNA requires as an input two RNA sequences in FASTA format. The sequences are represented as strings of characters from the alphabet {A,C,G,U,T} (the strings are case insensitive). There are three user specified parameters; gap penalty, maximum subsequence length and energy model. inteRNA reports the results in three different output forms:
  1. 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.
  2. 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.
  3. A text file reporting the calculated free energy of the predicted joint secondary structure.

Parameters

inteRNA can employ the following two models for approximating the total free energy of the joint 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.

Please cite

"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).