Basin Hopping Graph Framework
B(asin)H(opping)G(raph) is a novel coarse-grained model to approximate the folding landscapes of RNA molecules. Each vertex of the BHG is a local minimum, which represents the corresponding basin in the landscape. Its edges connect basins when there exists an ``energetically favorable’’ direct transition between them. The weights on the edges are the corresponding saddle heights and thus measure the difficulties of these favorable transitions. BHGs can be approximated efficiently and with high accuracy for RNAs well beyond the length range accessible to enumerative algorithms. The BHG contains more information than the barrier tree. The barrier tree is equivalent to the dendrogram obtained from the BHG by single linkage clustering. Efficient heuristics are utilized to overcome the stringent length restrictions imposed by enumerative approaches. The framework consists of two largely independent components:
- The RNAlocmin program generates a sample set of local minima within a user-defined energy range above the ground state. This component replaces the exhaustive enumeration of all low energy states and uses an adaptive schedule for setting up its parameters.
- The BHGbuilder algorithm is then used to estimate direct saddle points and to determine BHG-adjacency on the input set of LMs. As we show below, the edges and edge weights can be estimated along the way.