RNA Structure Prediction Including Pseudoknots through Direct Enumeration of States

The accurate prediction of RNA secondary structure from primary sequence data has had enormous impact on research from the past forty years. While many algorithms exist to make these predictions, the inclusion of non-nested loops, termed pseudoknots, still poses challenges. We describe how the entropies of pseudoknots of arbitrary complexity can be formulated analytically through a Feynman diagram-like integral formulation. Furthermore, we demonstrate that for sufficiently short RNA sequences (~45 nucleotides) the complete enumeration of possible secondary structures can be accomplished quickly despite the NP-complete nature of the problem. By employing exhaustive enumeration, we are able to exactly compute the entire free energy landscape of potential structures resulting from a primary RNA sequence.