Symmetric circular matchings and RNA folding

RNA secondary structures can be computed as optimal solutions of certain circular matching problems. An accurate treatment of this energy minimization problem has to account for the small — but non-negligible — entropic destabilization of secondary structures with non-trivial automorphisms. Such intrinsic symmetries are typically excluded from algorithmic approaches; however, because the effects are small, they play a role only for RNAs with symmetries at sequence level, and they appear only in particular settings that are less frequently used in practical application, such as circular folding or the co-folding of two or more identical RNAs. Here, we show that the RNA folding problem with symmetry terms can still be solved with polynomial-time algorithms. Empirically, the fraction of symmetric ground state structures decreases with chain length, so that the error introduced by neglecting the symmetry terms affects fewer and fewer predictions. We then explore the combinatorics of symmetric secondary structures in detail. Surprisingly, the singularities of the generating function coincide between symmetric and non-symmetric structures. Furthermore, generating functions and explicit asymptotic results for both the circular and the co-folding version are derived.