A new heuristic method for approximating the number of local minima in partial RNA energy landscapes

• We propose a new pooling procedure and evaluation strategy for sampling data over energy landscapes.
• The new method is embedded into the general framework devised by Granier and Kallel in 2002.
• The performance is evaluated on ten partial energy landscapes induced by RNA secondary structures.
• The average deviation of predictions from the true number of local minima is below 3%.
• Potential applications include microRNA target predictions and co-transcriptional RNA folding.

The analysis of energy landscapes plays an important role in mathematical modelling, simulation and optimisation. Among the main features of interest are the number and distribution of local minima within the energy landscape. Granier and Kallel proposed in 2002 a new sampling procedure for estimating the number of local minima. In the present paper, we focus on improved heuristic implementations of the general framework devised by Granier and Kallel with regard to run-time behaviour and accuracy of predictions. The new heuristic method is demonstrated for the case of partial energy landscapes induced by RNA secondary structures. While the computation of minimum free energy RNA secondary structures has been studied for a long time, the analysis of folding landscapes has gained momentum over the past years in the context of co-transcriptional folding and deeper insights into cell processes. The new approach has been applied to ten RNA instances of length between 99 nt and 504 nt and their respective partial energy landscapes defined by secondary structures within an energy offset ΔE above the minimum free energy conformation. The number of local minima within the partial energy landscapes ranges from 1440 to 3441. Our heuristic method produces for the best approximations on average a deviation below 3.0% from the true number of local minima.

Figure optionsDownload as PowerPoint slide