Approximating the Set of Local Minima in Partial RNA Folding Landscapes

Sudhakar Sahoo, Andreas Albrecht

Research output: Contribution to journalArticlepeer-review

2 Citations (Scopus)


Motivation: We study a stochastic method for approximating the set of local minima in partial RNA folding landscapes associated with a bounded-distance neighbourhood of folding conformations. The conformations are limited to RNA secondary structures without pseudoknots. The method aims at exploring partial energy landscapes pL induced by folding simulations and their underlying neighbourhood relations. It combines an approximation of the number of local optima devised by Garnier and Kallel (2002) with a run-time estimation for identifying sets of local optima established by Reeves and Eremeev (2004).

Results: The method is tested on nine sequences of length between 50 nt and 400 nt, which allows us to compare the results with data generated by RNAsubopt and subsequent barrier tree calculations. On the nine sequences, the method captures on average 92% of local minima with settings designed for a target of 95%. The run-time of the heuristic can be estimated by O(n2D?ln?), where n is the sequence length, ? is the number of local minima in the partial landscape pL under consideration and D is the maximum number of steepest descent steps in attraction basins associated with pL.
Original languageEnglish
Article numberbtr715
Pages (from-to)523-530
Number of pages8
Issue number4
Publication statusPublished - Feb 2012

ASJC Scopus subject areas

  • Biochemistry
  • Molecular Biology
  • Computational Theory and Mathematics
  • Computer Science Applications
  • Computational Mathematics
  • Statistics and Probability
  • Medicine(all)


Dive into the research topics of 'Approximating the Set of Local Minima in Partial RNA Folding Landscapes'. Together they form a unique fingerprint.

Cite this