Motivation: Though not as abundant in known biological processes as protein
s, RNA molecules serve as mol-e than mere intermediaries between DNA and pr
oteins. Research in the last 15 years demonstrates that RNA molecules serve
in many roles, including catalysis. Furthermore, RNA secondary structure p
rediction based on fi ee energy rules for stacking and loop formation remai
ns one of the few major breakthroughs in the field of structure prediction,
as minimum free energy structures and related quantities can be computed w
ith full mathematical rigor. However, with the curl-ent energy parameters,
the algorithms used hither to suffer the disadvantage of either employing h
euristics that risk (though highly unlikely) missing the optimal structure
or becoming prohibitively time consuming for model ate to large sequences.
Results: We present a new method to evaluate internal loops utilizing curre
ntly used energy rules. This method reduces the time complexity of this par
t of the structure prediction from O(n(4)) to O(n(3)), thus reducing the ov
erall complexity to O(n(3)). Even when the size of evaluated internal loops
is bounded by k (a commonly used heuristic), the method presented has a co
mpetitive edge by reducing the time complexity of internal loop evaluation
fi-om O(k(2)n(2)) to O(kn(2)). The method also applies to the calculation o
f the equilibrium partition function.