Simulating RNA folding kinetics on approximated energy landscapes

We present a general computational approach to simulate RNA folding kinetics that can be used to extract population kinetics, folding rates and the formation of particular substructures that might be intermediates in the folding process. Simulating RNA folding kinetics can provide unique insight into RNA whose functions are dictated by folding kinetics and not always by nucleotide sequence or the structure of the lowest free-energy state. The method first builds an approximate map (or model) of the folding energy landscape from which the population kinetics are analyzed by solving the master equation on the map. We present results obtained using an analysis technique, map-based Monte Carlo simulation, which stochastically extracts folding pathways from the map. Our method compares favorably with other computational methods that begin with a comprehensive free-energy landscape, illustrating that the smaller, approximate map captures the major features of the complete energy landscape. As a result, our method scales to larger RNAs. For example, here we validate kinetics of RNA of more than 200 nucleotides. Our method accurately computes the kinetics-based functional rates of wild-type and mutant ColE1 RNAII and MS2 phage RNAs showing excellent agreement with experiment.     

Structure and stability of RNA/RNA kissing complex: with application to HIV dimerization initiation signal

We develop a statistical mechanical model to predict the structure and folding stability of the RNA/RNA kissing-loop complex. One of the key ingredients of the theory is the conformational entropy for the RNA/RNA kissing complex. We employ the recently developed virtual bond-based RNA folding model (Vfold model) to evaluate the entropy parameters for the different types of kissing loops. A benchmark test against experiments suggests that the entropy calculation is reliable. As an application of the model, we apply the model to investigate the structure and folding thermodynamics for the kissing complex of the HIV-1 dimerization initiation signal. With the physics-based energetic parameters, we compute the free energy landscape for the HIV-1 dimer. From the energy landscape, we identify two minimal free energy structures, which correspond to the kissing-loop dimer and the extended-duplex dimer, respectively. The results support the two-step dimerization process for the HIV-1 replication cycle. Furthermore, based on the Vfold model and energy minimization, the theory can predict the native structure as well as the local minima in the free energy landscape. The root-mean-square deviations (RMSDs) for the predicted kissing-loop dimer and extended-duplex dimer are ∼3.0 Å. The method developed here provides a new method to study the RNA/RNA kissing complex.     

Using motion planning to study protein folding pathways.

We present a framework for studying protein folding pathways and potential landscapes which is based on techniques recently developed in the robotics motion planning community. Our focus in this work is to study the protein folding mechanism assuming we know the native fold. That is, instead of performing fold prediction, we aim to study issues related to the folding process, such as the formation of secondary and tertiary structure, and the dependence of the folding pathway on the initial denatured conformation. Our work uses probabilistic roadmap (PRM) motion planning techniques which have proven successful for problems involving high-dimensional configuration spaces. A strength of these methods is their efficiency in rapidly covering the planning space without becoming trapped in local minima. We have applied our PRM technique to several small proteins (~60 residues) and validated the pathways computed by comparing the secondary structure formation order on our paths to known hydrogen exchange experimental results. An advantage of the PRM framework over other simulation methods is that it enables one to easily and efficiently compute folding pathways from any denatured starting state to the (known) native fold. This aspect makes our approach ideal for studying global properties of the protein's potential landscape, most of which are difficult to simulate and study with other methods. For example, in the proteins we study, the folding pathways starting from different denatured states sometimes share common portions when they are close to the native fold, and moreover, the formation order of the secondary structure appears largely independent of the starting denatured conformation. Another feature of our technique is that the distribution of the sampled conformations is correlated with the formation of secondary structure and, in particular, appears to differentiate situations in which secondary structure clearly forms first and those in which the tertiary structure is obtained more directly. Overall, our results applying PRM techniques are very encouraging and indicate the promise of our approach for studying proteins for which experimental results are not available.     

Protein folding by motion planning

We investigate a novel approach for studying protein folding that has evolved from robotics motion planning techniques called probabilistic roadmap methods (PRMs). Our focus is to study issues related to the folding process, such as the formation of secondary and tertiary structures, assuming we know the native fold. A feature of our PRM-based framework is that the large sets of folding pathways in the roadmaps it produces, in just a few hours on a desktop PC, provide global information about the protein's energy landscape. This is an advantage over other simulation methods such as molecular dynamics or Monte Carlo methods which require more computation and produce only a single trajectory in each run. In our initial studies, we obtained encouraging results for several small proteins. In this paper, we investigate more sophisticated techniques for analyzing the folding pathways in our roadmaps. In addition to more formally revalidating our previous results, we present a case study showing that our technique captures known folding differences between the structurally similar proteins G and L.     

Practicality and time complexity of a sparsified RNA folding algorithm

Commonly used RNA folding programs compute the minimum free energy structure of a sequence under the pseudoknot exclusion constraint. They are based on Zuker's algorithm which runs in time O(n(3)). Recently, it has been claimed that RNA folding can be achieved in average time O(n(2)) using a sparsification technique. A proof of quadratic time complexity was based on the assumption that computational RNA folding obeys the "polymer-zeta property". Several variants of sparse RNA folding algorithms were later developed. Here, we present our own version, which is readily applicable to existing RNA folding programs, as it is extremely simple and does not require any new data structure. We applied it to the widely used Vienna RNAfold program, to create sibRNAfold, the first public sparsified version of a standard RNA folding program. To gain a better understanding of the time complexity of sparsified RNA folding in general, we carried out a thorough run time analysis with synthetic random sequences, both in the context of energy minimization and base pairing maximization. Contrary to previous claims, the asymptotic time complexity of a sparsified RNA folding algorithm using standard energy parameters remains O(n(3)) under a wide variety of conditions. Consistent with our run-time analysis, we found that RNA folding does not obey the "polymer-zeta property" as claimed previously. Yet, a basic version of a sparsified RNA folding algorithm provides 15- to 50-fold speed gain. Surprisingly, the same sparsification technique has a different effect when applied to base pairing optimization. There, its asymptotic running time complexity appears to be either quadratic or cubic depending on the base composition. The code used in this work is available at: .     

Visualization of Protein Folding Funnels in Lattice Models

Protein folding occurs in a very high dimensional phase space with an exponentially large number of states, and according to the energy landscape theory it exhibits a topology resembling a funnel. In this statistical approach, the folding mechanism is unveiled by describing the local minima in an effective one-dimensional representation. Other approaches based on potential energy landscapes address the hierarchical structure of local energy minima through disconnectivity graphs. In this paper, we introduce a metric to describe the distance between any two conformations, which also allows us to go beyond the one-dimensional representation and visualize the folding funnel in 2D and 3D. In this way it is possible to assess the folding process in detail, e.g., by identifying the connectivity between conformations and establishing the paths to reach the native state, in addition to regions where trapping may occur. Unlike the disconnectivity maps method, which is based on the kinetic connections between states, our methodology is based on structural similarities inferred from the new metric. The method was developed in a 27-mer protein lattice model, folded into a 3×3×3 cube. Five sequences were studied and distinct funnels were generated in an analysis restricted to conformations from the transition-state to the native configuration. Consistent with the expected results from the energy landscape theory, folding routes can be visualized to probe different regions of the phase space, as well as determine the difficulty in folding of the distinct sequences. Changes in the landscape due to mutations were visualized, with the comparison between wild and mutated local minima in a single map, which serves to identify different trapping regions. The extension of this approach to more realistic models and its use in combination with other approaches are discussed.     

Conformational heterogeneity of an equilibrium folding intermediate quantified and mapped by scanning mutagenesis

It is challenging to experimentally define an energy landscape for protein folding that comprises multiple partially unfolded states. Experimental results are often ambiguous as to whether a non-native state is conformationally homogeneous. Here, we tested an approach combining systematic mutagenesis and a Br?nsted-like analysis to reveal and quantify conformational heterogeneity of folding intermediate states. Using this method, we resolved an otherwise apparently homogeneous equilibrium folding intermediate of Borrelia burgdorferi OspA into two conformationally distinct species and determined their relative populations. Furthermore, we mapped the structural differences between these intermediate species, which are consistent with the non-native species that we previously proposed based on native-state hydrogen exchange studies. When treated as a single state, the intermediate ensemble exhibited fractional Phi-values for mutations and Hammond-type behaviors that are often observed for folding transition states. We found that a change in relative population of the two species within the intermediate ensemble explains these properties well, suggesting that fractional Phi-values and Hammond-type behaviors exhibited by folding intermediates and transition states may arise more often from conformational heterogeneity than from a single partial structure. Our results are consistent with the presence of multiple minima in a rugged energy landscape predicted from theoretical studies. The method described here provides a promising means to probe a complex folding energy landscape.     

Predicting Secondary Structural Folding Kinetics for Nucleic Acids

We report a new computational approach to the prediction of RNA secondary structure folding kinetics. In this approach, each elementary kinetic step is represented as the transformation between two secondary structures that differ by a helix. Based on the free energy landscape analysis, we identify three types of dominant pathways and the rate constants for the kinetic steps: 1), formation; 2), disruption of a helix stem; and 3), helix formation with concomitant partial melting of a competing (incompatible) helix. The third pathway, termed the tunneling pathway, is the low-barrier dominant pathway for the conversion between two incompatible helices. Comparisons with experimental data indicate that this new method is quite reliable in predicting the kinetics for RNA secondary structural folding and structural rearrangements. The approach presented here may provide a robust first step for further systematic development of a predictive theory for the folding kinetics for large RNAs.     

Salt contribution to RNA tertiary structure folding stability

Accurate quantification of the ionic contribution to RNA folding stability could greatly enhance our ability to understand and predict RNA functions. Recently, motivated by the potential importance of ion correlation and fluctuation in RNA folding, we developed the tightly bound ion (TBI) model. Extensive experimental tests showed that the TBI model can lead to better treatment of multivalent ions than the Poisson-Boltzmann equation. In this study, we use the model to quantify the contribution of salt (Na⁺ and Mg²⁺) to the RNA tertiary structure folding free energy. Folding of the RNA tertiary structure often involves intermediates. We focus on the folding transition from an intermediate state to the native state, and compute the electrostatic folding free energy of the RNA. Based on systematic calculations for a variety of RNA molecules, we derive a set of formulas for the electrostatic free energy for tertiary structural folding as a function of the sequence length and compactness of the RNA and the Na⁺ and Mg²⁺ concentrations. Extensive comparisons with experimental data suggest that our model and the extracted empirical formulas are quite reliable.     

A rugged free energy landscape separates multiple functional RNA folds throughout denaturation

The dynamic mechanisms by which RNAs acquire biologically functional structures are of increasing importance to the rapidly expanding fields of RNA therapeutics and biotechnology. Large energy barriers separating misfolded and functional states arising from alternate base pairing are a well-appreciated characteristic of RNA. In contrast, it is typically assumed that functionally folded RNA occupies a single native basin of attraction that is free of deeply dividing energy barriers (ergodic hypothesis). This assumption is widely used as an implicit basis to interpret experimental ensemble-averaged data. Here, we develop an experimental approach to isolate persistent sub-populations of a small RNA enzyme and show by single molecule fluorescence resonance energy transfer (smFRET), biochemical probing and high-resolution mass spectrometry that commitment to one of several catalytically active folds occurs unexpectedly high on the RNA folding energy landscape, resulting in partially irreversible folding. Our experiments reveal the retention of molecular heterogeneity following the complete loss of all native secondary and tertiary structure. Our results demonstrate a surprising longevity of molecular heterogeneity and advance our current understanding beyond that of non-functional misfolds of RNA kinetically trapped on a rugged folding-free energy landscape.     

Consensus folding of unaligned RNA sequences revisited.

As one of the earliest problems in computational biology, RNA secondary structure prediction (sometimes referred to as "RNA folding") problem has attracted attention again, thanks to the recent discoveries of many novel non-coding RNA molecules. The two common approaches to this problem are de novo prediction of RNA secondary structure based on energy minimization and the consensus folding approach (computing the common secondary structure for a set of unaligned RNA sequences). Consensus folding algorithms work well when the correct seed alignment is part of the input to the problem. However, seed alignment itself is a challenging problem for diverged RNA families. In this paper, we propose a novel framework to predict the common secondary structure for unaligned RNA sequences. By matching putative stacks in RNA sequences, we make use of both primary sequence information and thermodynamic stability for prediction at the same time. We show that our method can predict the correct common RNA secondary structures even when we are given only a limited number of unaligned RNA sequences, and it outperforms current algorithms in sensitivity and accuracy.     

A novel approach for large-scale polypeptide folding based on elastic networks using continuous optimization

We present a new computationally efficient method for large-scale polypeptide folding using coarse-grained elastic networks and gradient-based continuous optimization techniques. The folding is governed by minimization of energy based on Miyazawa-Jernigan contact potentials. Using this method we are able to substantially reduce the computation time on ordinary desktop computers for simulation of polypeptide folding starting from a fully unfolded state. We compare our results with available native state structures from Protein Data Bank (PDB) for a few de-novo proteins and two natural proteins, Ubiquitin and Lysozyme. Based on our simulations we are able to draw the energy landscape for a small de-novo protein, Chignolin. We also use two well known protein structure prediction software, MODELLER and GROMACS to compare our results. In the end, we show how a modification of normal elastic network model can lead to higher accuracy and lower time required for simulation.     

Using motion planning to map protein folding landscapes and analyze folding kinetics of known native structures.

We investigate a novel approach for studying the kinetics of protein folding. Our framework has evolved from robotics motion planning techniques called probabilistic roadmap methods (PRMs) that have been applied in many diverse fields with great success. In our previous work, we presented our PRM-based technique and obtained encouraging results studying protein folding pathways for several small proteins. In this paper, we describe how our motion planning framework can be used to study protein folding kinetics. In particular, we present a refined version of our PRM-based framework and describe how it can be used to produce potential energy landscapes, free energy landscapes, and many folding pathways all from a single roadmap which is computed in a few hours on a desktop PC. Results are presented for 14 proteins. Our ability to produce large sets of unrelated folding pathways may potentially provide crucial insight into some aspects of folding kinetics, such as proteins that exhibit both two-state and three-state kinetics that are not captured by other theoretical techniques.     

Predicting RNA pseudoknot folding thermodynamics

Based on the experimentally determined atomic coordinates for RNA helices and the self-avoiding walks of the P (phosphate) and C₄ (carbon) atoms in the diamond lattice for the polynucleotide loop conformations, we derive a set of conformational entropy parameters for RNA pseudoknots. Based on the entropy parameters, we develop a folding thermodynamics model that enables us to compute the sequence-specific RNA pseudoknot folding free energy landscape and thermodynamics. The model is validated through extensive experimental tests both for the native structures and for the folding thermodynamics. The model predicts strong sequence-dependent helix-loop competitions in the pseudoknot stability and the resultant conformational switches between different hairpin and pseudoknot structures. For instance, for the pseudoknot domain of human telomerase RNA, a native-like and a misfolded hairpin intermediates are found to coexist on the (equilibrium) folding pathways, and the interplay between the stabilities of these intermediates causes the conformational switch that may underlie a human telomerase disease.     

Concerted kinetic folding of a multidomain ribozyme with a disrupted loop-receptor interaction

The free energy landscape for the folding of large, multidomain RNAs is rugged, and kinetically trapped, misfolded intermediates are a hallmark of RNA folding reactions. Here, we examine the role of a native loop-receptor interaction in determining the ruggedness of the energy landscape for folding of the Tetrahymena ribozyme. We demonstrate a progressive smoothing of the energy landscape for ribozyme folding as the strength of the loop-receptor interaction is reduced. Remarkably, with the most severe mutation, global folding is more rapid than for the wild-type ribozyme and proceeds in a concerted fashion without the accumulation of long-lived kinetic intermediates. The results demonstrate that a complex interplay between native tertiary interactions, divalent ion concentration, and non-native secondary structure determines the ruggedness of the energy landscape. Furthermore, the results suggest that kinetic folding transitions involving large regions of highly structured RNAs can proceed in a concerted fashion, in the absence of significant stable, preorganized tertiary structure.     

Using ultraviolet absorption spectroscopy to study nanoswitches based on non-canonical DNA structures

Non-canonical forms of DNA are attracting increasing interest for applications in nanotechnology. It is frequently convenient to characterize DNA molecules using a label-free approach such as ultraviolet absorption spectroscopy. In this paper we present the results of our investigation into the use of this technique to probe the folding of quadruplex and triplex nanoswitches. We confirmed that four G-quartets were necessary for folding at sub-mM concentrations of potassium and found that the wrong choice of sequence for the linker between G-tracts could dramatically disrupt folding, presumably due to the presence of kinetic traps in the folding landscape. In the case of the triplex nanoswitch we examined, we found that the UV spectrum showed a small change in absorbance when a triplex was formed. We anticipate that our results will be of interest to researchers seeking to design DNA nanoswitches based on quadruplexes and triplexes.     

Predicting RNA folding thermodynamics with a reduced chain representation model

Based on the virtual bond representation for the nucleotide backbone, we develop a reduced conformational model for RNA. We use the experimentally measured atomic coordinates to model the helices and use the self-avoiding walks in a diamond lattice to model the loop conformations. The atomic coordinates of the helices and the lattice representation for the loops are matched at the loop-helix junction, where steric viability is accounted for. Unlike the previous simplified lattice-based models, the present virtual bond model can account for the atomic details of realistic three-dimensional RNA structures. Based on the model, we develop a statistical mechanical theory for RNA folding energy landscapes and folding thermodynamics. Tests against experiments show that the theory can give much more improved predictions for the native structures, the thermal denaturation curves, and the equilibrium folding/unfolding pathways than the previous models. The application of the model to the P5abc region of Tetrahymena group I ribozyme reveals the misfolded intermediates as well as the native-like intermediates in the equilibrium folding process. Moreover, based on the free energy landscape analysis for each and every loop mutation, the model predicts five lethal mutations that can completely alter the free energy landscape and the folding stability of the molecule.     

On prediction of folding nuclei in globular proteins

The approach described in this paper on the prediction of folding nuclei in globular proteins with known three dimensional structures is based on a search of the lowest saddle points through the barrier separating the unfolded state from the native structure on the free-energy landscape of protein chain. This search is performed by a dynamic programming method. Comparison of theoretical results with experimental data on the folding nuclei of two dozen of proteins shows that our model provides good phi value predictions for proteins whose structures have been determined by X-ray analysis, with a less limited success for proteins whose structures have been determined by NMR techniques only. Consideration of a full ensemble of transition states results in more successful prediction than consideration of only the transition states with the minimal free energy. In conclusion we have predicted the localization of folding nuclei for three dimensional protein structures for which kinetics of folding is studied now but the localization of folding nuclei is still unknown.     

An efficient algorithm to compute the landscape of locally optimal RNA secondary structures with respect to the Nussinov-Jacobson energy model.

We make a novel contribution to the theory of biopolymer folding, by developing an efficient algorithm to compute the number of locally optimal secondary structures of an RNA molecule, with respect to the Nussinov-Jacobson energy model. Additionally, we apply our algorithm to analyze the folding landscape of selenocysteine insertion sequence (SECIS) elements from A. Bock (personal communication), hammerhead ribozymes from Rfam (Griffiths-Jones et al., 2003), and tRNAs from Sprinzl's database (Sprinzl et al., 1998). It had previously been reported that tRNA has lower minimum free energy than random RNA of the same compositional frequency (Clote et al., 2003; Rivas and Eddy, 2000), although the situation is less clear for mRNA (Seffens and Digby, 1999; Workman and Krogh, 1999; Cohen and Skienna, 2002),(1) which plays no structural role. Applications of our algorithm extend knowledge of the energy landscape differences between naturally occurring and random RNA. Given an RNA molecule a(1), ... , a(n) and an integer k > or = 0, a k-locally optimal secondary structure S is a secondary structure on a(1), ... , a(n) which has k fewer base pairs than the maximum possible number, yet for which no basepairs can be added without violation of the definition of secondary structure (e.g., introducing a pseudoknot). Despite the fact that the number numStr(k) of k-locally optimal structures for a given RNA molecule in general is exponential in n, we present an algorithm running in time O(n (4)) and space O(n (3)), which computes numStr(k) for each k. Structurally important RNA, such as SECIS elements, hammerhead ribozymes, and tRNA, all have a markedly smaller number of k-locally optimal structures than that of random RNA of the same dinucleotide frequency, for small and moderate values of k. This suggests a potential future role of our algorithm as a tool to detect noncoding RNA genes.     

Stochastic roadmap simulation: an efficient representation and algorithm for analyzing molecular motion.

Classic molecular motion simulation techniques, such as Monte Carlo (MC) simulation, generate motion pathways one at a time and spend most of their time in the local minima of the energy landscape defined over a molecular conformation space. Their high computational cost prevents them from being used to compute ensemble properties (properties requiring the analysis of many pathways). This paper introduces stochastic roadmap simulation (SRS) as a new computational approach for exploring the kinetics of molecular motion by simultaneously examining multiple pathways. These pathways are compactly encoded in a graph, which is constructed by sampling a molecular conformation space at random. This computation, which does not trace any particular pathway explicitly, circumvents the local-minima problem. Each edge in the graph represents a potential transition of the molecule and is associated with a probability indicating the likelihood of this transition. By viewing the graph as a Markov chain, ensemble properties can be efficiently computed over the entire molecular energy landscape. Furthermore, SRS converges to the same distribution as MC simulation. SRS is applied to two biological problems: computing the probability of folding, an important order parameter that measures the "kinetic distance" of a protein's conformation from its native state; and estimating the expected time to escape from a ligand-protein binding site. Comparison with MC simulations on protein folding shows that SRS produces arguably more accurate results, while reducing computation time by several orders of magnitude. Computational studies on ligand-protein binding also demonstrate SRS as a promising approach to study ligand-protein interactions.