Journal Article

Target prediction and a statistical sampling algorithm for RNA–RNA interaction

Fenix W. D. Huang, Jing Qin, Christian M. Reidys and Peter F. Stadler

in Bioinformatics

Volume 26, issue 2, pages 175-181
Published in print January 2010 | ISSN: 1367-4803
Published online November 2009 | e-ISSN: 1460-2059 | DOI:

More Like This

Show all results sharing this subject:

  • Bioinformatics and Computational Biology


Show Summary Details


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


Supplementary information: Supplementary data are available at Bioinformatics online.

Journal Article.  5413 words.  Illustrated.

Subjects: Bioinformatics and Computational Biology

Users without a subscription are not able to see the full content. Please, subscribe or login to access all content.