How RNA folds.

We describe the RNA folding problem and contrast it with the much more difficult protein folding problem. RNA has four similar monomer units, whereas proteins have 20 very different residues. The folding of RNA is hierarchical in that secondary structure is much more stable than tertiary folding. In RNA the two levels of folding (secondary and tertiary) can be experimentally separated by the presence or absence of Mg2+. Secondary structure can be predicted successfully from experimental thermodynamic data on secondary structure elements: helices, loops, and bulges. Tertiary interactions can then be added without much distortion of the secondary structure. These observations suggest a folding algorithm to predict the structure of an RNA from its sequence. However, to solve the RNA folding problem one needs thermodynamic data on tertiary structure interactions, and identification and characterization of metal-ion binding sites. These data, together with force versus extension measurements on single RNA molecules, should provide the information necessary to test and refine the proposed algorithm.     

Protein topology prediction through constraint-based search and the evaluation of topological folding rules.

An algorithm for predicting protein alpha/beta-sheet topologies from secondary structure and topological folding rules (constraints) has been developed and implemented in Prolog. This algorithm (CBS1) is based on constraint satisfaction and employs forward pruned breadth-first search and rotational invariance. CBS1 showed a 37-fold increase in efficiency over an exhaustive generate and test algorithm giving the same solution for a typical sheet of five strands whose topology was predicted from secondary structure with four topological folding constraints. Prolog specifications of a range of putative protein folding rules were then used to (i) replicate published protein topology predictions and (ii) validate these rules against known protein structures of nucleotide-binding domains. This demonstrated that (i) manual techniques for topology prediction can lead to non-exhaustive search and (ii) most of these protein folding principles were violated by specific proteins. Various extensions to the algorithm are discussed.     

Optimal computer folding of large RNA sequences using thermodynamics and auxiliary information.

This paper presents a new computer method for folding an RNA molecule that finds a conformation of minimum free energy using published values of stacking and destabilizing energies. It is based on a dynamic programming algorithm from applied mathematics, and is much more efficient, faster, and can fold larger molecules than procedures which have appeared up to now in the biological literature. Its power is demonstrated in the folding of a 459 nucleotide immunoglobulin gamma 1 heavy chain messenger RNA fragment. We go beyond the basic method to show how to incorporate additional information into the algorithm. This includes data on chemical reactivity and enzyme susceptibility. We illustrate this with the folding of two large fragments from the 16S ribosomal RNA of Escherichia coli.     

Molecular basis of co-operativity in protein folding.

The folding/unfolding transition of proteins is a highly co-operative process characterized by the presence of very few or no thermodynamically stable partially folded intermediate states. The purpose of this paper is to present a thermodynamic formalism aimed at describing quantitatively the co-operative folding behavior of proteins. In order to account for this behavior, a hierarchical algorithm aimed at evaluating the folding/unfolding partition function has been developed. This formalism defines the partition function in terms of multiple levels of interacting co-operative folding units. A co-operative folding unit is defined as a protein structural element that exhibits two-state folding/unfolding behavior. At the most fundamental level are those structural elements that behave co-operatively as a result of purely local interactions. Higher-order co-operative folding units are formed through interactions between different structural elements. The hierarchical formalism utilizes the crystallographic structure of the protein as a template to generate partially folded conformations defined in terms of co-operative folding units. The Gibbs free energy of those states and their corresponding statistical weights are then computed using experimental energetic parameters determined calorimetrically. This formalism has been applied to the case of myoglobin. It is shown that the hierarchical partition function correctly predicts the presence, energetics and co-operativity of the heat and cold denaturation transitions. The major contribution to the co-operative folding behavior arises from the solvent exposure of non-polar residues located in regions complementary to those that have undergone unfolding. This entropically uncompensated and energetically unfavorable solvent exposure characterizes all partially folded states but not the unfolded state, thus minimizing the population of partially folded intermediates throughout the folding/unfolding transition.     

Alignment of a sparse protein signature with protein sequences: application to fold prediction for three small globulins.

A novel algorithm has been developed for scoring the match between an imprecise sparse signature and all the protein sequences in a sequence database. The method was applied to a specific problem: signatures were derived from the probable folding nucleus and positions obtained from the determined interactions that occur during the folding of three small globular proteins and points of inter-element contact and sequence comparison of the actual three-dimensional structures of the same three proteins. In the case of two of these, lysozyme and myoglobin, the residues in the folding nucleus corresponded well to the key residues spotted by examination of the structures and in the remaining case, barnase, they did not. The diagnostic performance of the two types of signatures were compared for all three proteins. The significance of this for the application of an understanding of the protein folding mechanisms for structure prediction is discussed. The algorithm is generic and could be applied to other user-defined problems of sequence analysis.     

SSCP primer design based on single-strand DNA structure predicted by a DNA folding program.

To predict alterations in single-strand DNA mobility in non-denaturing electrophoretic gels, Zuker's RNA folding program was modified. Energy files utilized by the LRNA RNA folding algorithm were modified to emulate folding of single-strand DNA. Energy files were modified to disallow G-T base pairing. Stacking energies were corrected for DNA thermodynamics. Constraints on loop nucleotide sequences were removed. The LRNA RNA folding algorithm using the DNA fold energy files was applied to predict folding of PCR generated single-strand DNA molecules from polymorphic human ALDH2 and TPH alleles. The DNA-Fold version 1.0 program was used to design primers to create and abolish SSCP mobility shifts. Primers were made that add a 5' tag sequence or alter complementarity to an internal sequence. Differences in DNA secondary structure were assessed by SSCP analysis and compared to single-strand DNA secondary structure predictions. Results demonstrate that alterations in single-strand DNA conformation may be predicted using DNA-Fold 1.0.     

基于新杂合进化算法的蛋白质折叠计算

蛋白质能量最小化是蛋白质折叠的重要内容。用于蛋白质折叠的新的杂合进化算法结合了交叉和柯西变异。基于toy模型的蛋白质能量最小化算例表明,这个新的杂合进化算法是有效的。     

The computer simulation of RNA folding involving pseudoknot formation.

The algorithm and the program for the prediction of RNA secondary structure with pseudoknot formation have been proposed. The algorithm simulates stepwise folding by generating random structures using Monte Carlo method, followed by the selection of helices to final structure on the basis of both their probabilities of occurrence in a random structure and free energy parameters. The program versions have been tested on ribosomal RNA structures and on RNAs with pseudoknots evidenced by experimental data. It is shown that the simulation of folding during RNA synthesis improves the results. The introduction of pseudoknot formation permits to predict the pseudoknotted structures and to improve the prediction of long-range interactions. The computer program is rather fast and allows to predict the structures for long RNAs without using large memory volumes in usual personal computer.     

RNA folding pathway functional intermediates: their prediction and analysis.

The massively parallel genetic algorithm (GA) for RNA structure prediction uses the concepts of mutation, recombination, and survival of the fittest to evolve a population of thousands of possible RNA structures toward a solution structure. As described below, the properties of the algorithm are ideally suited to use in the prediction of possible folding pathways and functional intermediates of RNA molecules given their sequences. Utilizing Stem Trace, an interactive visualization tool for RNA structure comparison, analysis of not only the solution ensembles developed by the algorithm, but also the stages of development of each of these solutions, can give strong insight into these folding pathways. The GA allows the incorporation of information from biological experiments, making it possible to test the influence of particular interactions between structural elements on the dynamics of the folding pathway. These methods are used to reveal the folding pathways of the potato spindle tuber viroid (PSTVd) and the host killing mechanism of Escherichia coli plasmid R1, both of which are successfully explored through the combination of the GA and Stem Trace. We also present novel intermediate folds of each molecule, which appear to be phylogenetically supported, as determined by use of the methods described below.     

A study of accessible motifs and RNA folding complexity.

mRNA molecules are folded in the cells and therefore many of their substrings may actually be inaccessible to protein and microRNA binding. The need to apply an accessibility criterion to the task of genome-wide mRNA motif discovery raises the challenge of overcoming the core O(n(3)) factor imposed by the time complexity of the currently best known algorithms for RNA secondary structure prediction. We speed up the dynamic programming algorithms that are standard for RNA folding prediction. Our new approach significantly reduces the computations without sacrificing the optimality of the results, yielding an expected time complexity of O(n(2) psi(n)), where psi(n) is shown to be constant on average under standard polymer folding models. A benchmark analysis confirms that in practice the runtime ratio between the previous approach and the new algorithm indeed grows linearly with increasing sequence size. The fast new RNA folding algorithm is utilized for genome-wide discovery of accessible cis-regulatory motifs in data sets of ribosomal densities and decay rates of S. cerevisiae genes and to the mining of exposed binding sites of tissue-specific microRNAs in A. thaliana.     

Observation of two families of folding pathways of BBL

BBL is an independent folding domain of a large multienzyme complex, 2-oxoglutarate dehydrogenase. The folding mechanism of BBL is under debate between the views of noncooperative downhill-type and classical two-state. Extensive replica exchange molecular dynamics simulations of BBL in explicit solvent have shown some non-two-state behaviors despite no definitive evidence of downhill folding. In this work, we postprocess the replica exchange data using our roadmap-based MaxFlux reaction path algorithm to reveal atomically detailed folding pathways. A connected graph is used to organize and visualize the folding pathways initiated from random coils. High structural and transition heterogeneity is seen in the early stage of folding. Two main parallel folding pathways emerge in the later stage; one path shows that tertiary contact and helix formation develop at different stages of folding, whereas the other path exhibits concurrence of secondary and tertiary structure formation to some extent. Because the native state of BBL is sensitive to experimental conditions, we speculate that the relative predominance of the two pathways may vary with the protein construct and solvent conditions, possibly leading to the seeming discrepancy of experimental results. Our roadmap-based reaction path algorithm is a general tool to extract path information from replica exchange.     

Distinguishing between sequential and nonsequentially folded proteins: implications for folding and misfolding.

We describe here an algorithm for distinguishing sequential from nonsequentially folding proteins. Several experiments have recently suggested that most of the proteins that are synthesized in the eukaryotic cell may fold sequentially. This proposed folding mechanism in vivo is particularly advantageous to the organism. In the absence of chaperones, the probability that a sequentially folding protein will misfold is reduced significantly. The problem we address here is devising a procedure that would differentiate between the two types of folding patterns. Footprints of sequential folding may be found in structures where consecutive fragments of the chain interact with each other. In such cases, the folding complexity may be viewed as being lower. On the other hand, higher folding complexity suggests that at least a portion of the polypeptide backbone folds back upon itself to form three-dimensional (3D) interactions with noncontiguous portion(s) of the chain. Hence, we look at the mechanism of folding of the molecule via analysis of its complexity, that is, through the 3D interactions formed by contiguous segments on the polypeptide chain. To computationally splice the structure into consecutively interacting fragments, we either cut it into compact hydrophobic folding units or into a set of hypothetical, transient, highly populated, contiguous fragments ("building blocks" of the structure). In sequential folding, successive building blocks interact with each other from the amino to the carboxy terminus of the polypeptide chain. Consequently, the results of the parsing differentiate between sequentially vs. nonsequentially folded chains. The automated assessment of the folding complexity provides insight into both the likelihood of misfolding and the kinetic folding rate of the given protein. In terms of the funnel free energy landscape theory, a protein that truly follows the mechanism of sequential folding, in principle, encounters smoother free energy barriers. A simple sequentially folded protein should, therefore, be less error prone and fold faster than a protein with a complex folding pattern.     

An implementation of the Gillespie algorithm for RNA kinetics with logarithmic time update

In this paper I outline a fast method called KFOLD for implementing the Gillepie algorithm to stochastically sample the folding kinetics of an RNA molecule at single base-pair resolution. In the same fashion as the KINFOLD algorithm, which also uses the Gillespie algorithm to predict folding kinetics, KFOLD stochastically chooses a new RNA secondary structure state that is accessible from the current state by a single base-pair addition/deletion following the Gillespie procedure. However, unlike KINFOLD, the KFOLD algorithm utilizes the fact that many of the base-pair addition/deletion reactions and their corresponding rates do not change between each step in the algorithm. This allows KFOLD to achieve a substantial speed-up in the time required to compute a prediction of the folding pathway and, for a fixed number of base-pair moves, performs logarithmically with sequence size. This increase in speed opens up the possibility of studying the kinetics of much longer RNA sequences at single base-pair resolution while also allowing for the RNA folding statistics of smaller RNA sequences to be computed much more quickly.     

Routes are trees: the parsing perspective on protein folding

An important puzzle in structural biology is the question of how proteins are able to fold so quickly into their unique native structures. There is much evidence that protein folding is hierarchic. In that case, folding routes are not linear, but have a tree structure. Trees are commonly used to represent the grammatical structure of natural language sentences, and chart parsing algorithms efficiently search the space of all possible trees for a given input string. Here we show that one such method, the CKY algorithm, can be useful both for providing novel insight into the physical protein folding process, and for computational protein structure prediction. As proof of concept, we apply this algorithm to the HP lattice model of proteins. Our algorithm identifies all direct folding route trees to the native state and allows us to construct a simple model of the folding process. Despite its simplicity, our model provides an account for the fact that folding rates depend only on the topology of the native state but not on sequence composition.     

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: .     

Efficient procedures for the numerical simulation of mid-size RNA kinetics

ABSTRACT: MotivationMethods for simulating the kinetic folding of RNAs by numerically solving the chemical master equation have been developed since the late 90's, notably the programs Kinfold and Treekin with Barriers that are available in the Vienna RNA package. Our goal is to formulate extensions to the algorithms used, starting from the Gillespie algorithm, that will allow numerical simulations of mid-size (~ 60--150 nt) RNA kinetics in some practical cases where numerous distributions of folding times are desired. These extensions can contribute to analyses and predictions of RNA folding in biologically significant problems. RESULTS: By describing in a particular way the reduction of numerical simulations of RNA folding kinetics into the Gillespie stochastic simulation algorithm for chemical reactions, it is possible to formulate extensions to the basic algorithm that will exploit memoization and parallelism for efficient computations. These can be used to advance forward from the small examples demonstrated to larger examples of biological interest.SoftwareThe implementation that is described and used for the Gillespie algorithm is freely available by contacting the authors, noting that the efficient procedures suggested may also be applicable along with Vienna's Kinfold.     

Efficient pairwise RNA structure prediction and alignment using sequence alignment constraints

Background  

We are interested in the problem of predicting secondary structure for small sets of homologous RNAs, by incorporating limited comparative sequence information into an RNA folding model. The Sankoff algorithm for simultaneous RNA folding and alignment is a basis for approaches to this problem. There are two open problems in applying a Sankoff algorithm: development of a good unified scoring system for alignment and folding and development of practical heuristics for dealing with the computational complexity of the algorithm.     

Hydrophobic folding units at protein-protein interfaces: implications to protein folding and to protein-protein association.

A hydrophobic folding unit cutting algorithm, originally developed for dissecting single-chain proteins, has been applied to a dataset of dissimilar two-chain protein-protein interfaces. Rather than consider each individual chain separately, the two-chain complex has been treated as a single chain. The two-chain parsing results presented in this work show hydrophobicity to be a critical attribute of two-state versus three-state protein-protein complexes. The hydrophobic folding units at the interfaces of two-state complexes suggest that the cooperative nature of the two-chain protein folding is the outcome of the hydrophobic effect, similar to its being the driving force in a single-chain folding. In analogy to the protein-folding process, the two-chain, two-state model complex may correspond to the formation of compact, hydrophobic nuclei. On the other hand, the three-state model complex involves binding of already folded monomers, similar to the association of the hydrophobic folding units within a single chain. The similarity between folding entities in protein cores and in two-state protein-protein interfaces, despite the absence of some chain connectivities in the latter, indicates that chain linkage does not necessarily affect the native conformation. This further substantiates the notion that tertiary, non-local interactions play a critical role in protein folding. These compact, hydrophobic, two-chain folding units, derived from structurally dissimilar protein-protein interfaces, provide a rich set of data useful in investigations of the role played by chain connectivity and by tertiary interactions in studies of binding and of folding. Since they are composed of non-contiguous pieces of protein backbones, they may also aid in defining folding nuclei.     

Kinetics of cytochrome C folding: atomically detailed simulations

The vast range of time scales (from nanoseconds to seconds) during protein folding is a challenge for experiments and computations. To make concrete predictions on folding mechanisms, atomically detailed simulations of protein folding, using potentials derived from chemical physics principles, are desired. However, due to their computational complexity, straightforward molecular dynamics simulations of protein folding are impossible today. An alternative algorithm is used that makes it possible to compute approximate atomically detailed long time trajectories (the Stochastic Difference Equation in Length). This algorithm is used to compute 26 atomically detailed folding trajectories of cytochrome c (a millisecond process). The early collapse of the protein chain (with marginal formation of secondary structure), and the earlier formation of the N and C helices (compare to the 60's helix) are consistent with the experiment. The existence of an energy barrier upon entry to the molten globule is examined as well. In addition to (favorable) comparison to experiments, we show that non-native contacts drive the formation of the molten globule. In contrast to popular folding models, the non-native contacts do not form off-pathway kinetic traps in cytochrome c.