memerna: Sparse RNA folding including coaxial stacking

Determining RNA secondary structure is a core problem in computational biology. Fast algorithms for predicting secondary structure are fundamental to this task. We describe a modified formulation of the Zuker-Stiegler algorithm with coaxial stacking, a stabilising interaction in which the ends of helices in multi-loops are stacked. In particular, optimal coaxial stacking is computed as part of the dynamic programming state, rather than in an inner loop. We introduce a new notion of sparsity, which we call replaceability. Replaceability is a more general condition and applicable in more places than the triangle inequality that is used by previous sparse folding methods. We also introduce non-monotonic candidate lists as an additional sparsification tool. Existing usages of the triangle inequality for sparsification can be thought of as an application of both replaceability and monotonicity together. The modified recurrences along with replaceability allows sparsification to be applied to coaxial stacking as well, which increases the speed of the algorithm. We implemented this algorithm in software we call memerna, which we show to have the fastest exact (non-heuristic) implementation of RNA folding under the complete Turner 2004 model with coaxial stacking, out of several popular RNA folding tools supporting coaxial stacking. We also introduce a new notation for secondary structure which includes coaxial stacking, terminal mismatches, and dangles (CTDs) information. The memerna package 0.1 release is available at https://github.com/Edgeworth/memerna/tree/release/0.1.