memerna: Sparse RNA Folding Including Coaxial Stacking

Abstract

AO_SCPLOWBSTRACTC_SCPLOWDetermining 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 stabilizing interaction in which the ends of multi-loops are stacked. In particular, optimal coaxial stacking is computed as part of the dynamic programming state, rather than inline. We introduce a new notion of sparsity, which we call replaceability. The modified formulation 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 RNA folding implementation out of several popular RNA folding packages supporting coaxial stacking. We also introduce a new notation for secondary structure which includes coaxial stacking, terminal mismatches, and dangles (CTDs) information.