title: Target prediction and a statistical sampling algorithm for RNA-RNA interaction.
abstract: 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.
authors.affiliation: Center for Combinatorics, LPMC-TJKLC, Nankai University, Tianjin 300071, PR China.
authors.forename: Fenix W D
authors.initials: FW
authors.lastname: Huang
authors.forename: Jing
authors.initials: J
authors.lastname: Qin
authors.forename: Christian M
authors.initials: CM
authors.lastname: Reidys
authors.forename: Peter F
authors.initials: PF
authors.lastname: Stadler
mesh_terms: 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
chemical_list: D035683:MicroRNAs; D034741:RNA, Small Interfering; D012313:RNA