An Improved Algorithm for RNA Secondary Structure Prediction

Abstract

Though not as abundant in known biological processes as proteins,
RNA molecules serve as more than mere intermediaries between
DNA and proteins, e.g. as catalytic molecules. Furthermore,
RNA secondary structure prediction based on free energy
rules for stacking and loop formation remains one of the few major
breakthroughs in the field of structure prediction. We present a
new method to evaluate all possible internal loops of size at most
k in an RNA sequence, s, in time O(k|s|^2); this is an improvement
from the previously used method that uses time O(k^2|s|^2).
For unlimited loop size this improves the overall complexity of
evaluating RNA secondary structures from O(|s|^4) to O(|s|^3) and
the method applies equally well to finding the optimal structure
and calculating the equilibrium partition function. We use our
method to examine the soundness of setting k = 30, a commonly
used heuristic.