An Improved Algorithm for RNA Secondary Structure Prediction

Rune B. Lyngsø, Michael Zuker, Christian N. S. Pedersen

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.

Full Text:

PDF


DOI: http://dx.doi.org/10.7146/brics.v6i15.20072
This website uses cookies to allow us to see how the site is used. The cookies cannot identify you or any content at your own computer.
OK


ISSN: 0909-0878 

Hosted by the Royal Danish Library and Aarhus University Library