An Improved Algorithm for RNA Secondary Structure Prediction

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