Fast tree search for a triangular lattice model of protein folding

Using a triangular lattice model to study the designability of protein folding, we overcame the parity problem of previous cubic lattice model and enumerated all the sequences and compact structures on a simple two-dimensional triangular lattice model of size 4 5 6 5 4. We used two types of amino acids, hydrophobic and polar, to make up the sequences, and achieved 223W212 different sequences excluding the reverse symmetry sequences. The total string number of distinct compact structures was 219,093, excluding reflection symmetry in the self-avoiding path of length 24 triangular lattice model. Based on this model, we applied a fast search algorithm by constructing a cluster tree. The algorithm decreased the computation by computing the objective energy of non-leaf nodes. The parallel experiments proved that the fast tree search algorithm yielded an exponential speed-up in the model of size 4 5 6 5 4. Designability analysis was performed to understand the search result.     

An effective evolutionary algorithm for protein folding on 3D FCC HP model by lattice rotation and generalized move sets

Background

Proteins are essential biological molecules which play vital roles in nearly all biological processes. It is the tertiary structure of a protein that determines its functions. Therefore the prediction of a protein's tertiary structure based on its primary amino acid sequence has long been the most important and challenging subject in biochemistry, molecular biology and biophysics. In the past, the HP lattice model was one of the ab initio methods that many researchers used to forecast the protein structure. Although these kinds of simplified methods could not achieve high resolution, they provided a macrocosm-optimized protein structure. The model has been employed to investigate general principles of protein folding, and plays an important role in the prediction of protein structures.

Methods

In this paper, we present an improved evolutionary algorithm for the protein folding problem. We study the problem on the 3D FCC lattice HP model which has been widely used in previous research. Our focus is to develop evolutionary algorithms (EA) which are robust, easy to implement and can handle various energy functions. We propose to combine three different local search methods, including lattice rotation for crossover, K-site move for mutation, and generalized pull move; these form our key components to improve previous EA-based approaches.

Results

We have carried out experiments over several data sets which were used in previous research. The results of the experiments show that our approach is able to find optimal conformations which were not found by previous EA-based approaches.

Conclusions

We have investigated the geometric properties of the 3D FCC lattice and developed several local search techniques to improve traditional EA-based approaches to the protein folding problem. It is known that EA-based approaches are robust and can handle arbitrary energy functions. Our results further show that by extensive development of local searches, EA can also be very effective for finding optimal conformations on the 3D FCC HP model. Furthermore, the local searches developed in this paper can be integrated with other approaches such as the Monte Carlo and Tabu searches to improve their performance.

     

Protein folding on the hexagonal lattice in the HP model

In this paper, we introduce the 2D hexagonal lattice as a biologically meaningful alternative to the standard square lattice for the study of protein folding in the HP model. We show that the hexagonal lattice alleviates the "sharp turn" problem and models certain aspects of the protein secondary structure more realistically. We present a 1/6-approximation and a clustering heuristic for protein folding on the hexagonal lattice. In addition to these two algorithms, we also implement a Monte Carlo Metropolis algorithm and a branch-and-bound partial enumeration algorithm, and conduct experiments to compare their effectiveness.     

Automated classification of RNA 3D motifs and the RNA 3D Motif Atlas

The analysis of atomic-resolution RNA three-dimensional (3D) structures reveals that many internal and hairpin loops are modular, recurrent, and structured by conserved non-Watson–Crick base pairs. Structurally similar loops define RNA 3D motifs that are conserved in homologous RNA molecules, but can also occur at nonhomologous sites in diverse RNAs, and which often vary in sequence. To further our understanding of RNA motif structure and sequence variability and to provide a useful resource for structure modeling and prediction, we present a new method for automated classification of internal and hairpin loop RNA 3D motifs and a new online database called the RNA 3D Motif Atlas. To classify the motif instances, a representative set of internal and hairpin loops is automatically extracted from a nonredundant list of RNA-containing PDB files. Their structures are compared geometrically, all-against-all, using the FR3D program suite. The loops are clustered into motif groups, taking into account geometric similarity and structural annotations and making allowance for a variable number of bulged bases. The automated procedure that we have implemented identifies all hairpin and internal loop motifs previously described in the literature. All motif instances and motif groups are assigned unique and stable identifiers and are made available in the RNA 3D Motif Atlas (http://rna.bgsu.edu/motifs), which is automatically updated every four weeks. The RNA 3D Motif Atlas provides an interactive user interface for exploring motif diversity and tools for programmatic data access.     

Navigating the RNA folding landscape

Analysis of individual RNA folding reactions reveals that, as in proteins, cooperative interactions selectively drive RNA toward its biologically active, native conformation. This new work establishes a platform for future investigations of the physical principles underlying the assembly of large RNA enzymes.     

RNA folding and catalysis

Catalysis in RNA is intimately connected to the folding. The small nucleolytic ribozymes function by a nucleophilic attack of the 2-oxygen on the 3-phosphate, in an S_N2 mechanism. This requires an alignment of the 2-O, 3-P and 5-O, that does not occur in normal A-form RNA. It is therefore likely that structural distortion plays a major role in the enhancement of the reaction rate, facilitating the trajectory into the in-line transition state. Given the polyelectrolyte nature of nucleic acids, metal ions are critical to folding processes in RNA. We have shown that two small nucleolytic ribozymes, the hammerhead and hairpin ribozymes, undergo metal ion-induced folding processes. The hammerhead ribozyme folds in two stages, each of which is induced by the binding of a single structural ion. The first corresponds to the formation of the ribozyme scaffold, while the second is the formation of the catalytic core of the ribozyme. By contrast, the hairpin ribozyme undergoes a single folding event induced by the binding of at least two metal ions, and involves the close interaction between two internal loops to form the active ribozyme.This revised version was published online in October 2005 with corrections to the Cover Date.     

RNA folding and unfolding

Single-molecule studies of RNA folding and unfolding are providing impressive details of the intermediates that occur and their rates of interconversion. The folding and unfolding of RNA are controlled by varying the concentration of magnesium ions and measuring fluorescence energy transfer, or by applying force to the RNA and measuring the end-to-end distance. The hierarchical nature of RNA folding - first secondary structure, then tertiary structure - makes the process susceptible to analysis and prediction.     

RNA 3D Modules in Genome-Wide Predictions of RNA 2D Structure

Recent experimental and computational progress has revealed a large potential for RNA structure in the genome. This has been driven by computational strategies that exploit multiple genomes of related organisms to identify common sequences and secondary structures. However, these computational approaches have two main challenges: they are computationally expensive and they have a relatively high false discovery rate (FDR). Simultaneously, RNA 3D structure analysis has revealed modules composed of non-canonical base pairs which occur in non-homologous positions, apparently by independent evolution. These modules can, for example, occur inside structural elements which in RNA 2D predictions appear as internal loops. Hence one question is if the use of such RNA 3D information can improve the prediction accuracy of RNA secondary structure at a genome-wide level. Here, we use RNAz in combination with 3D module prediction tools and apply them on a 13-way vertebrate sequence-based alignment. We find that RNA 3D modules predicted by metaRNAmodules and JAR3D are significantly enriched in the screened windows compared to their shuffled counterparts. The initially estimated FDR of 47.0% is lowered to below 25% when certain 3D module predictions are present in the window of the 2D prediction. We discuss the implications and prospects for further development of computational strategies for detection of RNA 2D structure in genomic sequence.     

Topological constraints: using RNA secondary structure to model 3D conformation, folding pathways, and dynamic adaptation

Accompanying recent advances in determining RNA secondary structure is the growing appreciation for the importance of relatively simple topological constraints, encoded at the secondary structure level, in defining the overall architecture, folding pathways, and dynamic adaptability of RNA. A new view is emerging in which tertiary interactions do not define RNA 3D structure, but rather, help select specific conformers from an already narrow, topologically pre-defined conformational distribution. Studies are providing fundamental insights into the nature of these topological constraints, how they are encoded by the RNA secondary structure, and how they interplay with other interactions, breathing new meaning to RNA secondary structure. New approaches have been developed that take advantage of topological constraints in determining RNA backbone conformation based on secondary structure, and a limited set of other, easily accessible constraints. Topological constraints are also providing a much-needed framework for rationalizing and describing RNA dynamics and structural adaptation. Finally, studies suggest that topological constraints may play important roles in steering RNA folding pathways. Here, we review recent advances in our understanding of topological constraints encoded by the RNA secondary structure.     

RNA folding and ribosome assembly

Ribosome synthesis is a tightly regulated process that is crucial for cell survival. Chemical footprinting, mass spectrometry, and cryo-electron microscopy are revealing how these complex cellular machines are assembled. Rapid folding of the rRNA provides a platform for protein-induced assembly of the bacterial 30S ribosome. Multiple assembly pathways increase the flexibility of the assembly process, while accessory factors and modification enzymes chaperone the late stages of assembly and control the quality of the mature subunits.     

RNA folding using quantum computers

The 3-dimensional fold of an RNA molecule is largely determined by patterns of intramolecular hydrogen bonds between bases. Predicting the base pairing network from the sequence, also referred to as RNA secondary structure prediction or RNA folding, is a nondeterministic polynomial-time (NP)-complete computational problem. The structure of the molecule is strongly predictive of its functions and biochemical properties, and therefore the ability to accurately predict the structure is a crucial tool for biochemists. Many methods have been proposed to efficiently sample possible secondary structure patterns. Classic approaches employ dynamic programming, and recent studies have explored approaches inspired by evolutionary and machine learning algorithms. This work demonstrates leveraging quantum computing hardware to predict the secondary structure of RNA. A Hamiltonian written in the form of a Binary Quadratic Model (BQM) is derived to drive the system toward maximizing the number of consecutive base pairs while jointly maximizing the average length of the stems. A Quantum Annealer (QA) is compared to a Replica Exchange Monte Carlo (REMC) algorithm programmed with the same objective function, with the QA being shown to be highly competitive at rapidly identifying low energy solutions. The method proposed in this study was compared to three algorithms from literature and, despite its simplicity, was found to be competitive on a test set containing known structures with pseudoknots.     

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.     

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.     

RNA folding and misfolding of the hammerhead ribozyme

The hammerhead ribozyme undergoes a well-defined two-stage folding process induced by the sequential binding of two magnesium ions. These probably correspond to the formation of domain 2 (0-500 microM magnesium ions) and domain 1 (1-20 mM magnesium ions), respectively. In this study we have used fluorescence resonance energy transfer (FRET) to analyze the ion-induced folding of a number of variants of the hammerhead ribozyme. We find that both A14G and G8U mutations are highly destabilizing, such that these species are essentially unfolded under all conditions. Thus they appear to be blocked in the first stage of the folding process, and using uranyl-induced photocleavage we show that the core is completely accessible to this probe under these conditions. Changes at G5 do not affect the first transition but appear to provide a blockage at the second stage of folding; this is true of changes in the sugar (removal of the 2'-hydroxyl group) and base (G5C mutation, previously studied by comparative gel electrophoresis). Arrest of folding at this intermediate stage leads to a pattern of uranyl-induced photocleavage that is changed from the wild-type, but suggests a structure less open than the A14G mutant. Specific photocleavage at G5 is found only in the wild-type sequence, suggesting that this ion-binding site is formed late in the folding process. In addition to folding that is blocked at selected stages, we have also observed misfolding. Thus the A13G mutation appears to result in the ion-induced formation of a novel tertiary structure.     

Structure of the 3''-hairpin of the TYMV pseudoknot: preformation in RNA folding.

The solution structure of an RNA-hairpin present in the pseudoknot, which is found at the 3'-terminus of turnip yellow mosaic virus genomic RNA, has been solved by nuclear magnetic resonance spectroscopy. The loop, which contains the sequence 5'-GGGUCA-3', was found to be highly structured and, contrary to expectations, does not attain its stability through GA or GC base pair formation but by triple interactions between the tilted adenosine and the minor groove sides of the first two guanosines. Interestingly, a very similar conformation was found for the cognate pseudoknot, implying that the 3'-hairpin is preformed for folding into a pseudoknotted structure. These findings suggest a mechanism of 'predetermined-fit' as a principle in RNA folding.