Target prediction and a statistical sampling algorithm for RNA-RNA interaction.
BACKGROUND
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(N(6)) time and O(N(4)) 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.N(3)).


BACKGROUND
The algorithms described here are implemented in C as part of the rip package. The source code of rip2 can be downloaded from http://www.combinatorics.cn/cbpc/rip.html and http://www.bioinf.uni-leipzig.de/Software/rip.html.


BACKGROUND
Supplementary data are available at Bioinformatics online.
Huang
Fenix W D
FW
Center for Combinatorics, LPMC-TJKLC, Nankai University, Tianjin 300071, PR China.
Qin
Jing
J
Reidys
Christian M
CM
Stadler
Peter F
PF
D000465:Algorithms; D001665:Binding Sites; D019295:Computational Biology / Q000379:methods; D030541:Databases, Genetic; D035683:MicroRNAs / Q000737:chemistry / Q000378:metabolism; D008958:Models, Molecular; D015233:Models, Statistical; D009690:Nucleic Acid Conformation; D012313:RNA / Q000737:chemistry* / Q000378:metabolism; D034741:RNA, Small Interfering / Q000737:chemistry / Q000378:metabolism; D012984:Software
D035683:MicroRNAs; D034741:RNA, Small Interfering; D012313:RNA