Combinatorics of RNA–RNA interaction

RNA–RNA binding is an important phenomenon observed for many classes of non-coding RNAs and plays a crucial role in a number of regulatory processes. Recently several MFE folding algorithms for predicting the joint structure of two interacting RNA molecules have been proposed. Here joint structure means that in a diagram representation the intramolecular bonds of each partner are pseudoknot-free, that the intermolecular binding pairs are noncrossing, and that there is no so-called “zigzag” configuration. This paper presents the combinatorics of RNA interaction structures including their generating function, singularity analysis as well as explicit recurrence relations. In particular, our results imply simple asymptotic formulas for the number of joint structures.     

Multiscale simulations of protein folding: application to formation of secondary structures

A multiscale simulation method of protein folding is proposed, using atomic representation of protein and solvent, combing genetic algorithms to determine the key protein structures from a global view, with molecular dynamic simulations to reveal the local folding pathways, thus providing an integrated landscape of protein folding. The method is found to be superior to previously investigated global search algorithms or dynamic simulations alone. For secondary structure formation of a selected peptide, RN24, the structures and dynamics produced by this method agree well with corresponding experimental results. Three most populated conformations are observed, including hairpin, β-sheet and α-helix. The energetic barriers separating these three structures are comparable to the kinetic energy of the atoms of the peptide, implying that the transition between these states can be easily triggered by kinetic perturbations, mainly through electrostatic interactions between charged atoms. Transitions between α-helix and β-sheet should jump over at least two energy barriers and may stay in the energetic trap of hairpin. It is proposed that the structure of proteins should be jointly governed by thermodynamic and dynamic factors; free energy is not the exclusive dominant for stability of proteins.     

Finding the needle in the haystack: towards solving the protein-folding problem computationally

Prediction of protein tertiary structures from amino acid sequence and understanding the mechanisms of how proteins fold, collectively known as “the protein folding problem,” has been a grand challenge in molecular biology for over half a century. Theories have been developed that provide us with an unprecedented understanding of protein folding mechanisms. However, computational simulation of protein folding is still difficult, and prediction of protein tertiary structure from amino acid sequence is an unsolved problem. Progress toward a satisfying solution has been slow due to challenges in sampling the vast conformational space and deriving sufficiently accurate energy functions. Nevertheless, several techniques and algorithms have been adopted to overcome these challenges, and the last two decades have seen exciting advances in enhanced sampling algorithms, computational power and tertiary structure prediction methodologies. This review aims at summarizing these computational techniques, specifically conformational sampling algorithms and energy approximations that have been frequently used to study protein-folding mechanisms or to de novo predict protein tertiary structures. We hope that this review can serve as an overview on how the protein-folding problem can be studied computationally and, in cases where experimental approaches are prohibitive, help the researcher choose the most relevant computational approach for the problem at hand. We conclude with a summary of current challenges faced and an outlook on potential future directions.     

Central and local limit theorems for RNA structures

A k-noncrossing RNA pseudoknot structure is a graph over {1,…,n} without 1-arcs, i.e. arcs of the form (i,i+1) and in which there exists no k-set of mutually intersecting arcs. In particular, RNA secondary structures are 2-noncrossing RNA structures. In this paper we prove a central and a local limit theorem for the distribution of the number of 3-noncrossing RNA structures over n nucleotides with exactly h bonds. Our analysis employs the generating function of k-noncrossing RNA pseudoknot structures and the asymptotics for the coefficients. The results of this paper explain the findings on the number of arcs of RNA secondary structures obtained by molecular folding algorithms and are of relevance for prediction algorithms of k-noncrossing RNA structures.     

Inverse folding of RNA pseudoknot structures

Background  

RNA exhibits a variety of structural configurations. Here we consider a structure to be tantamount to the noncrossing Watson-Crick and G-U-base pairings (secondary structure) and additional cross-serial base pairs. These interactions are called pseudoknots and are observed across the whole spectrum of RNA functionalities. In the context of studying natural RNA structures, searching for new ribozymes and designing artificial RNA, it is of interest to find RNA sequences folding into a specific structure and to analyze their induced neutral networks. Since the established inverse folding algorithms, RNAinverse, RNA-SSD as well as INFO-RNA are limited to RNA secondary structures, we present in this paper the inverse folding algorithm Inv which can deal with 3-noncrossing, canonical pseudoknot structures.     

Simultaneous modeling of multiple loops in proteins.

The most reliable methods for predicting protein structure are by way of homologous extension, using structural information from a closely related protein, or by "threading" through a set of predefined protein folds ("inverse folding"). Both sets of methods provide a model for the core of the protein--the structurally conserved secondary structures. Due to the large variability both in sequence and size of the loops that connect these secondary structures, they generally cannot be modeled using these techniques. Loop-closure algorithms are aimed at predicting loop structures, given their end-to-end distance. Various such algorithms have been described, and all have been tested by predicting the structure of a single loop in a known protein. In this paper we propose a method, which is based on the bond-scaling-relaxation loop-closure algorithm, for simultaneously predicting the structures of multiple loops, and demonstrate that, for two spatially close loops, simultaneous closure invariably leads to more accurate predictions than sequential closure. The accuracy of the predictions obtained for pairs of loops in the size range of 5-7 residues each is comparable to that obtained by other methods, when predicting the structures of single loops: the RMS deviations from the native conformations of various test cases modeled are approximately 0.6-1.7 A for backbone atoms and 1.1-3.3 A for all-atoms.     

CONFOLD: Residue‐residue contact‐guided ab initio protein folding

Predicted protein residue–residue contacts can be used to build three‐dimensional models and consequently to predict protein folds from scratch. A considerable amount of effort is currently being spent to improve contact prediction accuracy, whereas few methods are available to construct protein tertiary structures from predicted contacts. Here, we present an ab initio protein folding method to build three‐dimensional models using predicted contacts and secondary structures. Our method first translates contacts and secondary structures into distance, dihedral angle, and hydrogen bond restraints according to a set of new conversion rules, and then provides these restraints as input for a distance geometry algorithm to build tertiary structure models. The initially reconstructed models are used to regenerate a set of physically realistic contact restraints and detect secondary structure patterns, which are then used to reconstruct final structural models. This unique two‐stage modeling approach of integrating contacts and secondary structures improves the quality and accuracy of structural models and in particular generates better β‐sheets than other algorithms. We validate our method on two standard benchmark datasets using true contacts and secondary structures. Our method improves TM‐score of reconstructed protein models by 45% and 42% over the existing method on the two datasets, respectively. On the dataset for benchmarking reconstructions methods with predicted contacts and secondary structures, the average TM‐score of best models reconstructed by our method is 0.59, 5.5% higher than the existing method. The CONFOLD web server is available at http://protein.rnet.missouri.edu/confold/ . Proteins 2015; 83:1436–1449. © 2015 Wiley Periodicals, Inc.     

RNA folding with soft constraints: reconciliation of probing data and thermodynamic secondary structure prediction

Thermodynamic folding algorithms and structure probing experiments are commonly used to determine the secondary structure of RNAs. Here we propose a formal framework to reconcile information from both prediction algorithms and probing experiments. The thermodynamic energy parameters are adjusted using 'pseudo-energies' to minimize the discrepancy between prediction and experiment. Our framework differs from related approaches that used pseudo-energies in several key aspects. (i) The energy model is only changed when necessary and no adjustments are made if prediction and experiment are consistent. (ii) Pseudo-energies remain biophysically interpretable and hold positional information where experiment and model disagree. (iii) The whole thermodynamic ensemble of structures is considered thus allowing to reconstruct mixtures of suboptimal structures from seemingly contradicting data. (iv) The noise of the energy model and the experimental data is explicitly modeled leading to an intuitive weighting factor through which the problem can be seen as folding with 'soft' constraints of different strength. We present an efficient algorithm to iteratively calculate pseudo-energies within this framework and demonstrate how this approach can be used in combination with SHAPE chemical probing data to improve secondary structure prediction. We further demonstrate that the pseudo-energies correlate with biophysical effects that are known to affect RNA folding such as chemical nucleotide modifications and protein binding.     

Mechanism of protein folding II. Lysozyme and phospholipase

Refolding of hen egg-white lysozyme assuming the formation of secondary structures (-helices and β-sheets) is carried out by the method presented in the previous paper (N. Saitô et al., Proteins; Struct. Funct. Genet. 3 (1988) 199–208). To do this, the hydrophobic interactions between the hydrophobic residues which are located at the key positions for folding and can be identified without te knowledge of the native structure, and the nonbonded interactions between every pair of atoms (except hydrogen) or groups are introduced successively from short-to medium-distance pairs. The search for the energy minimum by these interactions can afford a conformation of especially the mutual arrangements between neighboring secondary structures. When these local structures are accomplished, some of the long-distance amino-acid pairs come close together and then the possible interactions (hydrophobic, nonbonded) are introduced. The three-dimensional structure of lysozyme thus obtained is shown to have locally correct arrangements of the secondary structures, but mutual relations between long-distance parts of the chain are not similar to the native structure. The introduction of disulfide bonds between appropriate cysteine residues is necessary to reach the native structure. The choice of cysteine pairs for disulfide bonding is made by the criterion given in the paper to follow (K. Watanabe, A. Nakamura, Y. Fukuda and N. Saitô, Biophys. Chem. 40 (1991) 293). The same treatment is applied to bovine pancreatic phospholipase with 7 disulfide bonds. The formation of the antiparallel β-structures from neighboring β-strands and the problem of the folding order are also discussed.     

Contact order and ab initio protein structure prediction

Although much of the motivation for experimental studies of protein folding is to obtain insights for improving protein structure prediction, there has been relatively little connection between experimental protein folding studies and computational structural prediction work in recent years. In the present study, we show that the relationship between protein folding rates and the contact order (CO) of the native structure has implications for ab initio protein structure prediction. Rosetta ab initio folding simulations produce a dearth of high CO structures and an excess of low CO structures, as expected if the computer simulations mimic to some extent the actual folding process. Consistent with this, the majority of failures in ab initio prediction in the CASP4 (critical assessment of structure prediction) experiment involved high CO structures likely to fold much more slowly than the lower CO structures for which reasonable predictions were made. This bias against high CO structures can be partially alleviated by performing large numbers of additional simulations, selecting out the higher CO structures, and eliminating the very low CO structures; this leads to a modest improvement in prediction quality. More significant improvements in predictions for proteins with complex topologies may be possible following significant increases in high-performance computing power, which will be required for thoroughly sampling high CO conformations (high CO proteins can take six orders of magnitude longer to fold than low CO proteins). Importantly for such a strategy, simulations performed for high CO structures converge much less strongly than those for low CO structures, and hence, lack of simulation convergence can indicate the need for improved sampling of high CO conformations. The parallels between Rosetta simulations and folding in vivo may extend to misfolding: The very low CO structures that accumulate in Rosetta simulations consist primarily of local up-down beta-sheets that may resemble precursors to amyloid formation.     

Comparing folding codes for proteins and polymers

Proteins fold to unique compact native structures. Perhaps other polymers could be designed to fold in similar ways. The chemical nature of the monomer “alphabet” determines the “energy matrix” of monomer interactions—which defines the folding code, the relationship between sequence and structure. We study two properties of energy matrices using two-dimensional lattice models: uniqueness, the number of sequences that fold to only one structure, and encodability, the number of folds that are unique lowest-energy structures of certain monomer sequences. For the simplest model folding code, involving binary sequences of H (hydrophobic) and P (polar) monomers, only a small fraction of sequences fold uniquely, and not all structures can be encoded. Adding strong repulsive interactions results in a folding code with more sequences folding uniquely and more designable folds. Some theories suggest that the quality of a folding code depends only on the number of letters in the monomer alphabet, but we find that the energy matrix itself can be at least as important as the size of the alphabet. Certain multi-letter codes, including some with 20 letters, may be less physical or protein-like than codes with smaller numbers of letters because they neglect correlations among inter-residue interactions, treat only maximally compact conformations, or add arbitrary energies to the energy matrix.     

Constraining local structure can speed up folding by promoting structural polarization of the folding pathway

The pathway which proteins take to fold can be influenced from the earliest events of structure formation. In this light, it was both predicted and confirmed that increasing the stiffness of a beta hairpin turn decreased the size of the transition state ensemble (TSE), while increasing the folding rate. Thus, there appears to be a relationship between conformationally restricting the TSE and increasing the folding rate, at least for beta hairpin turns. In this study, we hypothesize that the enormous sampling necessary to fold even two-state folding proteins in silico could be reduced if local structure constraints were used to restrict structural heterogeneity by polarizing folding pathways or forcing folding into preferred routes. Using a Gō model, we fold Chymotrypsin Inhibitor 2 (CI-2) and the src SH3 domain after constraining local sequence windows to their native structure by rigid body dynamics (RBD). Trajectories were monitored for any changes to the folding pathway and differences in the kinetics compared with unconstrained simulations. Constraining local structure decreases folding time two-fold for 41% of src SH3 windows and 45% of CI-2 windows. For both proteins, folding times are never significantly increased after constraining any window. Structural polarization of the folding pathway appears to explain these rate increases. Folding rate enhancements are consistent with the goal to reduce sampling time necessary to reach native structures during folding simulations. As anticipated, not all constrained windows showed an equal decrease in folding time. We conclude by analyzing these differences and explain why RBD may be the preferred way to constrain structure.     

Influence of protein structure databases on the predictive power of statistical pair potentials

A long standing goal in protein structure studies is the development of reliable energy functions that can be used both to verify protein models derived from experimental constraints as well as for theoretical protein folding and inverse folding computer experiments. In that respect, knowledge-based statistical pair potentials have attracted considerable interests recently mainly because they include the essential features of protein structures as well as solvent effects at a low computing cost. However, the basis on which statistical potentials are derived have been questioned. In this paper, we investigate statistical pair potentials derived from protein three-dimensional structures, addressing in particular questions related to the form of these potentials, as well as to the content of the database from which they are derived. We have shown that statistical pair potentials depend on the size of the proteins included in the database, and that this dependence can be reduced by considering only pairs of residue close in space (i.e., with a cutoff of 8 Å). We have shown also that statistical potentials carry a memory of the quality of the database in terms of the amount and diversity of secondary structure it contains. We find, for example, that potentials derived from a database containing α-proteins will only perform best on α-proteins in fold recognition computer experiments. We believe that this is an overall weakness of these potentials, which must be kept in mind when constructing a database. Proteins 31:139–149, 1998. © 1998 Wiley-Liss, Inc.     

Secondary structure prediction and folding of globular protein: refolding of ferredoxin

The physicochemical mechanism of protein folding has been elucidated by the island model, describing a growth type of folding. The folding pathway is closely related with nucleation on the polypeptide chain and thus the formation of small local structures or secondary structures at the earliest stage of folding is essential to all following steps. The island model is applicable to any protein, but a high precision of secondary structure prediction is indispensable to folding simulation. The secondary structures formed at the earliest stage of folding are supposed to be of standard form, but they are usually deformed during the folding process, especially at the last stage, although the degree of deformation is different for each protein. Ferredoxin is an example of a protein having this property. According to X-ray investigation (1FDX), ferredoxin is not supposed to have secondary structures. However, if we assumed that in ferredoxin all the residues are in a coil state, we could not attain the correct structure similar to the native one. Further, we found that some parts of the chain are not flexible, suggesting the presence of secondary structures, in agreement with the recent PDB data (1DUR). Assuming standard secondary structures (-helices and -strands) at the nonflexible parts at the early stage of folding, and deforming these at the final stage, a structure similar to the native one was obtained. Another peculiarity of ferredoxin is the absence of disulfide bonds, in spite of its having eight cysteines. The reason cysteines do not form disulfide bonds became clear by applying the lampshade criterion, but more importantly, the two groups of cysteines are ready to make iron complexes, respectively, at a rather later stage of folding. The reason for poor prediction accuracy of secondary structure with conventional methods is discussed.     

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.     

How do potentials derived from structural databases relate to “true” potentials?

Knowledge-based potentials are used widely in protein folding and inverse folding algorithms. Two kinds of derivation methods are used. (1) The interactions in a database of known protein structures are assumed to obey a Boltzmann distribution. (2) The stability of the native folds relative to a manifold of misfolded structures is optimized. Here, a set of previously derived contact and secondary structure propensity potentials, taken as the "true" potentials, are employed to construct an artificial protein structural database from protein fragments. Then, new sets of potentials are derived to see how they are related to the true potentials. Using the Boltzmann distribution method, when the stability of the structures in the database lies within a certain range, both contact potentials and secondary structure propensities can be derived separately with remarkable accuracy. In general, the optimization method was found to be less accurate due to errors in the "excess energy" contribution. When the excess energy terms are kept as a constraint, the true potentials are recovered exactly.     

Reversible unfolding and refolding behavior of a monomeric aldolase from Staphylococcus aureus.

Thermal and GdmCl-induced unfolding transitions of aldolase from Staphylococcus aureus are reversible under a variety of solvent conditions. Analysis of the transitions reveals that no partially folded intermediates can be detected under equilibrium conditions. The stability of the enzyme is very low with a delta G0 value of -9 +/- 2 kJ/mol at 20 degrees C. The kinetics of unfolding and refolding of aldolase are complex and comprise at least one fast and two slow reactions. This complexity arises from prolyl isomerization reactions in the unfolded chain, which are kinetically coupled to the actual folding reaction. Comparison with model calculations shows that at least two prolyl peptide bonds give rise to the observed slow folding reactions of aldolase and that all of the involved bonds are presumably in the trans conformation in the native state. The rate constant of the actual folding reaction is fast with a relaxation time of about 15 s at the midpoint of the folding transition at 15 degrees C. The data presented on the folding and stability of aldolase are comparable to the properties of much smaller proteins. This might be connected with the simple and highly repetitive tertiary structure pattern of the enzyme, which belongs to the group of alpha/beta barrel proteins.     

Folding small proteins via annealing stochastic approximation Monte Carlo

Recently, the stochastic approximation Monte Carlo algorithm has been proposed by Liang et al. (2007) as a general-purpose stochastic optimization and simulation algorithm. An annealing version of this algorithm was developed for real small protein folding problems. The numerical results indicate that it outperforms simulated annealing and conventional Monte Carlo algorithms as a stochastic optimization algorithm. We also propose one method for the use of secondary structures in protein folding. The predicted protein structures are rather close to the true structures.     

Small angle X-ray scattering-assisted protein structure prediction in CASP13 and emergence of solution structure differences

Small angle X-ray scattering (SAXS) measures comprehensive distance information on a protein's structure, which can constrain and guide computational structure prediction algorithms. Here, we evaluate structure predictions of 11 monomeric and oligomeric proteins for which SAXS data were collected and provided to predictors in the 13th round of the Critical Assessment of protein Structure Prediction (CASP13). The category for SAXS-assisted predictions made gains in certain areas for CASP13 compared to CASP12. Improvements included higher quality data with size exclusion chromatography-SAXS (SEC-SAXS) and better selection of targets and communication of results by CASP organizers. In several cases, we can track improvements in model accuracy with use of SAXS data. For hard multimeric targets where regular folding algorithms were unsuccessful, SAXS data helped predictors to build models better resembling the global shape of the target. For most models, however, no significant improvement in model accuracy at the domain level was registered from use of SAXS data, when rigorously comparing SAXS-assisted models to the best regular server predictions. To promote future progress in this category, we identify successes, challenges, and opportunities for improved strategies in prediction, assessment, and communication of SAXS data to predictors. An important observation is that, for many targets, SAXS data were inconsistent with crystal structures, suggesting that these proteins adopt different conformation(s) in solution. This CASP13 result, if representative of PDB structures and future CASP targets, may have substantive implications for the structure training databases used for machine learning, CASP, and use of prediction models for biology.     

Mimicking the action of GroEL in molecular dynamics simulations: application to the refinement of protein structures

Bacterial chaperonin, GroEL, together with its co-chaperonin, GroES, facilitates the folding of a variety of polypeptides. Experiments suggest that GroEL stimulates protein folding by multiple cycles of binding and release. Misfolded proteins first bind to an exposed hydrophobic surface on GroEL. GroES then encapsulates the substrate and triggers its release into the central cavity of the GroEL/ES complex for folding. In this work, we investigate the possibility to facilitate protein folding in molecular dynamics simulations by mimicking the effects of GroEL/ES namely, repeated binding and release, together with spatial confinement. During the binding stage, the (metastable) partially folded proteins are allowed to attach spontaneously to a hydrophobic surface within the simulation box. This destabilizes the structures, which are then transferred into a spatially confined cavity for folding. The approach has been tested by attempting to refine protein structural models generated using the ROSETTA procedure for ab initio structure prediction. Dramatic improvements in regard to the deviation of protein models from the corresponding experimental structures were observed. The results suggest that the primary effects of the GroEL/ES system can be mimicked in a simple coarse-grained manner and be used to facilitate protein folding in molecular dynamics simulations. Furthermore, the results support the assumption that the spatial confinement in GroEL/ES assists the folding of encapsulated proteins.