Target prediction and a statistical sampling algorithm for RNA-RNA interaction.

FW Huang, J Qin, CM Reidys, PF Stadler

Research output: Contribution to journalJournal articleResearchpeer-review


Motivation: It has been proven that the accessibility of the target sites has a critical influence on RNA–RNA binding, in general and the specificity and efficiency of miRNAs and siRNAs, in particular. Recently, O(N6) time and O(N4) space dynamic programming (DP) algorithms have become available that compute the partition function of RNA–RNA interaction complexes, thereby providing detailed insights into their thermodynamic properties.

Results: Modifications to the grammars underlying earlier approaches enables the calculation of interaction probabilities for any given interval on the target RNA. The computation of the ‘hybrid probabilities’ is complemented by a stochastic sampling algorithm that produces a Boltzmann weighted ensemble of RNA–RNA interaction structures. The sampling of k structures requires only negligible additional memory resources and runs in O(k·N3).

Availability: The algorithms described here are implemented in C as part of the rip package. The source code of rip2 can be downloaded from and
Original languageEnglish
Issue number2
Pages (from-to)175-181
Publication statusPublished - 15. Jan 2010
Externally publishedYes


Dive into the research topics of 'Target prediction and a statistical sampling algorithm for RNA-RNA interaction.'. Together they form a unique fingerprint.

Cite this