title: Partition function and base pairing probabilities for RNA-RNA interaction prediction.
abstract: BACKGROUND
  The RNA-RNA interaction problem (RIP) consists in finding the energetically optimal structure of two RNA molecules that bind to each other. The standard model allows secondary structures in both partners as well as additional base pairs between the two RNAs subject to certain restrictions that ensure that RIP is solvabale by a polynomial time dynamic programming algorithm. RNA-RNA binding, like RNA folding, is typically not dominated by the ground state structure. Instead, a large ensemble of alternative structures contributes to the interaction thermodynamics.
  
  
  RESULTS
  We present here an O(N(6)) time and O(N(4)) dynamics programming algorithm for computing the full partition function for RIP which is based on the combinatorial notion of 'tight structures'. Albeit equivalent to recent work by H. Chitsaz and collaborators, our approach in addition provides a full-fledged computation of the base pairing probabilities, which relies on the notion of a decomposition tree for joint structures. In practise, our implementation is efficient enough to investigate, for instance, the interactions of small bacterial RNAs and their target mRNAs.
  
  
  BACKGROUND
  The program rip is implemented in C. The source code is available for download from http://www.combinatorics.cn/cbpc/rip.html and http://www.bioinf.uni-leipzig.de/Software/rip.html.
authors: Center for Combinatorics, LPMC-TJKLC, Nankai University Tianjin 300071, P.R. China.
authors: Fenix W D
authors: FW
authors: Huang
authors: Jing
authors: J
authors: Qin
authors: Christian M
authors: CM
authors: Reidys
authors: Peter F
authors: PF
authors: Stadler
mesh_terms: D000465:Algorithms; D020029:Base Pairing; D019295:Computational Biology / Q000379:methods*; D030541:Databases, Genetic; D009690:Nucleic Acid Conformation; D012313:RNA / Q000737:chemistry* / Q000378:metabolism; D013816:Thermodynamics
chemical_list: D012313:RNA