Huang, F.W.D.F.W.D.HuangQin, J.J.QinReidys, C.M.C.M.ReidysStadler, P.F.P.F.Stadler2022-03-042022-03-042010https://publica.fraunhofer.de/handle/publica/22129010.1093/bioinformatics/btp6352-s2.0-752490932422-s2.0-77950472609Motivation: 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).en610570journal article