Parisien and Major (2008) described an algorithm for finding a secondary structure of an RNA that includes non-canonical base-pairs (MC-Fold) as well as a second algorithm (MC-Sym) for finding the three-dimensional structure, given the MC-Fold prediction.
The database behind MC-Fold is interesting as it contains counts not only for the 4x4 possible pairings but for the specific paired edges (in the .hinge-files). This information, however, is then integrated out and only the statistical potential for each pair remains.
The implementation by Parisien and Major (2008) gives an exponential runtime in the input sequence size. MC-Fold-DP, described in Höner zu Siederdissen et al. (2011) is an algorithm similar (not equal as we do not possess the required knowledge of internal workings) to MC-Fold with polynomial O(n3) runtime. In addition, the algorithm is unambiguous, which means that one can enumerate all structures within a score range above the best structure. We are currently working on including the McCaskill partition function calculations in both, MC-Fold-DP and RNAwolf.
To use MC-Fold-DP, you need to download the sources or binaries here and the original MC-Fold database (a link is provided here).
In case you want to compile the sources yourself and/or change the sources, please read the section "On compiling" on the download page. The sources are distributed under the GPLv3.
Höner zu Siederdissen, Christian, Stephan H. Bernhart, Peter F. Stadler, and Ivo L. Hofacker. 2011. A Folding Algorithm for Extended RNA Secondary Structures. Bioinformatics 27: 129–36. doi:10.1093/bioinformatics/btr220.
Parisien, Marc, and Francois Major. 2008. The MC-Fold and MC-Sym pipeline infers RNA structure from sequence data. Nature 452: 51–55. doi:10.1038/nature06684.