Partition Function and Base Pairing Probabilities for RNA-RNA Interaction Prediction

The RNA-RNA interaction problems (RIP) deals with the energetically optimal structure of two RNA molecules that bind to each other. The standard model introduced by Alkan et al. (J. Comput. Biol. 13: 267-282, 2006) allows secondary structures in both partners as well as additional base-pairs between the two RNAs subjects to certain restrictions that allow a polynomial-time dynamic programming solution. We derive the partition function for RIP based on a notion of "tight structures" as an alternative to the approach of Chitsaz et al. (Bioinformatics, ISMB 2009). This dynamic programming approach is extended here by a full-fledged computation of the base-pairing probabilities. The O(N6) time and O(N4) space algorithm is implemented in C (available from http://www.combinatorics.cn/cbpc/rip.html) and is efficient enough to investigate for instance the interactions of small bacterial RNAs and their target mRNAs.