From structure prediction to genomic screens for novel non-coding RNAs

Non-coding RNAs (ncRNAs) are receiving more and more attention not only as an abundant class of genes, but also as regulatory structural elements (some located in mRNAs). A key feature of RNA function is its structure. Computational methods were developed early for folding and prediction of RNA structure with the aim of assisting in functional analysis. With the discovery of more and more ncRNAs, it has become clear that a large fraction of these are highly structured. Interestingly, a large part of the structure is comprised of regular Watson-Crick and GU wobble base pairs. This and the increased amount of available genomes have made it possible to employ structure-based methods for genomic screens. The field has moved from folding prediction of single sequences to computational screens for ncRNAs in genomic sequence using the RNA structure as the main characteristic feature. Whereas early methods focused on energy-directed folding of single sequences, comparative analysis based on structure preserving changes of base pairs has been efficient in improving accuracy, and today this constitutes a key component in genomic screens. Here, we cover the basic principles of RNA folding and touch upon some of the concepts in current methods that have been applied in genomic screens for de novo RNA structures in searches for novel ncRNA genes and regulatory RNA structure on mRNAs. We discuss the strengths and weaknesses of the different strategies and how they can complement each other.     

Common structures of the 5' non-coding RNA in enteroviruses and rhinoviruses. Thermodynamical stability and statistical significance

A total of 4051 suboptimal secondary structures are predicted by folding the 5' non-coding region of ten polioviruses, five human rhinoviruses and three coxsackieviruses using our new suboptimal folding algorithm for the prediction of both optimal and suboptimal RNA secondary structures. A comparative analysis of these RNA secondary structures reveals the conservation of common secondary structure that can be supported by phylogenetic data. The thermodynamic stability and statistical significance of these predicted, conserved helical elements are assessed and significant structure motifs in the 5' non-coding region are proposed. The possible roles of these structure motifs in the virus life cycle are discussed.     

A Boltzmann filter improves the prediction of RNA folding pathways in a massively parallel genetic algorithm

RNA folding using the massively parallel genetic algorithm (GA) has been enhanced by the addition of a Boltzmann filter. The filter uses the Boltzmann probability distribution in conjunction with Metropolis' relaxation algorithm. The combination of these two concepts within the GA's massively parallel computational environment helps guide the genetic algorithm to more accurately reflect RNA folding pathways and thus final solution structures. Helical regions (base-paired stems) now form in the structures based upon the stochastic properties of the thermodynamic parameters that have been determined from experiments. Thus, structural changes occur based upon the relative energetic impact that the change causes rather than just geometric conflicts alone. As a result, when comparing the predictions to phylogenetically determined structures, over multiple runs, fewer false-positive stems (predicted incorrectly) and more true-positive stems (predicted correctly) are generated, and the total number of predicted stems representing a solution is diminished. In addition, the significance (rate of occurrence) of the true-positive stems is increased. Thus, the predicted results more accurately reflect phylogenetically determined structures.     

Transient RNA structure features are evolutionarily conserved and can be computationally predicted

Functional RNA structures tend to be conserved during evolution. This finding is, for example, exploited by comparative methods for RNA secondary structure prediction that currently provide the state-of-art in terms of prediction accuracy. We here provide strong evidence that homologous RNA genes not only fold into similar final RNA structures, but that their folding pathways also share common transient structural features that have been evolutionarily conserved. For this, we compile and investigate a non-redundant data set of 32 sequences with known transient and final RNA secondary structures and devise a dedicated computational analysis pipeline.     

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.     

Prediction of Protein Structure by Simulating Coarse-grained Folding Pathways: A Preliminary Report

Abstract

A set of software tools designed to study protein structure and kinetics has been developed. The core of these tools is a program called Folding Machine (FM) which is able to generate low resolution folding pathways using modest computational resources. The FM is based on a coarse-grained kinetic ab initio Monte-Carlo sampler that can optionally use information extracted from secondary structure prediction servers or from fragment libraries of local structure. The model underpinning this algorithm contains two novel elements: (a) the conformational space is discretized using the Ramachandran basins defined in the local φ-ψ energy maps; and (b) the solvent is treated implicitly by rescaling the pairwise terms of the non-bonded energy function according to the local solvent environments. The purpose of this hybrid ab initio/knowledge-based approach is threefold: to cover the long time scales of folding, to generate useful 3-dimensional models of protein structures, and to gain insight on the protein folding kinetics. Even though the algorithm is not yet fully developed, it has been used in a recent blind test of protein structure prediction (CASP5). The FM generated models within 6 Å backbone rmsd for fragments of about 60–70 residues of a-helical proteins. For a CASP5 target that turned out to be natively unfolded, the trajectory obtained for this sequence uniquely failed to converge. Also, a new measure to evaluate structure predictions is presented and used along the standard CASP assessment methods. Finally, recent improvements in the prediction of β-sheet structures are briefly described.     

Prediction of RNA pseudoknots using heuristic modeling with mapping and sequential folding

Predicting RNA secondary structure is often the first step to determining the structure of RNA. Prediction approaches have historically avoided searching for pseudoknots because of the extreme combinatorial and time complexity of the problem. Yet neglecting pseudoknots limits the utility of such approaches. Here, an algorithm utilizing structure mapping and thermodynamics is introduced for RNA pseudoknot prediction that finds the minimum free energy and identifies information about the flexibility of the RNA. The heuristic approach takes advantage of the 5' to 3' folding direction of many biological RNA molecules and is consistent with the hierarchical folding hypothesis and the contact order model. Mapping methods are used to build and analyze the folded structure for pseudoknots and to add important 3D structural considerations. The program can predict some well known pseudoknot structures correctly. The results of this study suggest that many functional RNA sequences are optimized for proper folding. They also suggest directions we can proceed in the future to achieve even better results.     

INFO-RNA--a fast approach to inverse RNA folding

MOTIVATION: The structure of RNA molecules is often crucial for their function. Therefore, secondary structure prediction has gained much interest. Here, we consider the inverse RNA folding problem, which means designing RNA sequences that fold into a given structure. RESULTS: We introduce a new algorithm for the inverse folding problem (INFO-RNA) that consists of two parts; a dynamic programming method for good initial sequences and a following improved stochastic local search that uses an effective neighbor selection method. During the initialization, we design a sequence that among all sequences adopts the given structure with the lowest possible energy. For the selection of neighbors during the search, we use a kind of look-ahead of one selection step applying an additional energy-based criterion. Afterwards, the pre-ordered neighbors are tested using the actual optimization criterion of minimizing the structure distance between the target structure and the mfe structure of the considered neighbor. We compared our algorithm to RNAinverse and RNA-SSD for artificial and biological test sets. Using INFO-RNA, we performed better than RNAinverse and in most cases, we gained better results than RNA-SSD, the probably best inverse RNA folding tool on the market. AVAILABILITY: www.bioinf.uni-freiburg.de?Subpages/software.html.     

ESSA: an integrated and interactive computer tool for analysing RNA secondary structure.

With ESSA, we propose an approach of RNA secondary structure analysis based on extensive viewing within a friendly graphical interface. This computer program is organized around the display of folding models produced by two complementary methods suitable to draw long RNA molecules. Any feature of interest can be managed directly on the display and highlighted by a rich combination of colours and symbols with emphasis given to structural probe accessibilities. ESSA also includes a word searching procedure allowing easy visual identification of structural features even complex and degenerated. Analysis functions make it possible to calculate the thermodynamic stability of any part of a folding using several models and compare homologous aligned RNA both in primary and secondary structure. The predictive capacities of ESSA which brings together the experimental, thermodynamic and comparative methods, are increased by coupling it with a program dedicated to RNA folding prediction based on constraints management and propagation. The potentialities of ESSA are illustrated by the identification of a possible tertiary motif in the LSU rRNA and the visualization of a pseudoknot in S15 mRNA.     

Folding kinetics of designer proteins. Application of the diffusion-collision model to a de novo designed four-helix bundle.

A folding algorithm is described, based on the diffusion-collision model, combining static and dynamic calculational methods. The algorithm is applied to predict the basic structure and schematic folding pathways of an artificial four-helix bundle.     

Prediction of protein structure by simulating coarse-grained folding pathways: a preliminary report

A set of software tools designed to study protein structure and kinetics has been developed. The core of these tools is a program called Folding Machine (FM) which is able to generate low resolution folding pathways using modest computational resources. The FM is based on a coarse-grained kinetic ab initio Monte-Carlo sampler that can optionally use information extracted from secondary structure prediction servers or from fragment libraries of local structure. The model underpinning this algorithm contains two novel elements: (a) the conformational space is discretized using the Ramachandran basins defined in the local phi-psi energy maps; and (b) the solvent is treated implicitly by rescaling the pairwise terms of the non-bonded energy function according to the local solvent environments. The purpose of this hybrid ab initio/knowledge-based approach is threefold: to cover the long time scales of folding, to generate useful 3-dimensional models of protein structures, and to gain insight on the protein folding kinetics. Even though the algorithm is not yet fully developed, it has been used in a recent blind test of protein structure prediction (CASP5). The FM generated models within 6 A backbone rmsd for fragments of about 60-70 residues of alpha-helical proteins. For a CASP5 target that turned out to be natively unfolded, the trajectory obtained for this sequence uniquely failed to converge. Also, a new measure to evaluate structure predictions is presented and used along the standard CASP assessment methods. Finally, recent improvements in the prediction of beta-sheet structures are briefly described.     

Rich parameterization improves RNA structure prediction

Current approaches to RNA structure prediction range from physics-based methods, which rely on thousands of experimentally measured thermodynamic parameters, to machine-learning (ML) techniques. While the methods for parameter estimation are successfully shifting toward ML-based approaches, the model parameterizations so far remained fairly constant. We study the potential contribution of increasing the amount of information utilized by RNA folding prediction models to the improvement of their prediction quality. This is achieved by proposing novel models, which refine previous ones by examining more types of structural elements, and larger sequential contexts for these elements. Our proposed fine-grained models are made practical thanks to the availability of large training sets, advances in machine-learning, and recent accelerations to RNA folding algorithms. We show that the application of more detailed models indeed improves prediction quality, while the corresponding running time of the folding algorithm remains fast. An additional important outcome of this experiment is a new RNA folding prediction model (coupled with a freely available implementation), which results in a significantly higher prediction quality than that of previous models. This final model has about 70,000 free parameters, several orders of magnitude more than previous models. Being trained and tested over the same comprehensive data sets, our model achieves a score of 84% according to the F?-measure over correctly-predicted base-pairs (i.e., 16% error rate), compared to the previously best reported score of 70% (i.e., 30% error rate). That is, the new model yields an error reduction of about 50%. Trained models and source code are available at www.cs.bgu.ac.il/?negevcb/contextfold.     

基于最小自由能和协变信息预测带伪结RNA二级结构的迭代化方法

多数RNA分子的结构在进化中是高度保守的, 其中很多包含伪结。而RNA伪结的预测一直是一个棘手问题, 很多RNA 二级结构预测算法都不能预测伪结。文章提出一种基于迭代法预测带伪结RNA 二级结构的新方法。该方法在给潜在碱基对打分时综合了热力学和协变信息, 通过基于最小自由能RNA折叠算法的多次迭代选出所有的碱基对。测试结果表明: 此方法几乎能预测到所有的伪结。与其他方法相比, 敏感度接近最优, 而特异性达到最优。     

Mapping nucleic acid structure by hydroxyl radical cleavage

Hydroxyl radical footprinting is a widely used method for following the folding of RNA molecules in solution. This method has the unique ability to provide experimental information on the solvent accessibility of each nucleotide in an RNA molecule, so that the folding of all domains of the RNA species can be followed simultaneously at single-nucleotide resolution. In recent work, hydroxyl radical footprinting has been used, often in combination with other global measures of structure, to work out detailed folding pathways and three-dimensional structures for increasingly large and complicated RNA molecules. These include synthetic ribozymes, and group I and group II ribozymes, from yeast, the Azoarcus cyanobacterium and Tetrahymena thermophila. Advances have been made in methods for analysis of hydroxyl radical data, so that the large datasets that result from kinetic folding experiments can be analyzed in a semi-automated and quantitative manner.     

Beyond Mfold: recent advances in RNA bioinformatics

Computational analysis of RNA secondary structure is a classical field of biosequence analysis, which has recently gained momentum due to the manyfold regulatory functions of RNA that have become apparent. We present five recent computational approaches that address the problems of synoptic folding space analysis, pseudoknot prediction, structure alignment, comparative structure prediction, and miRNA target prediction. All these programs are in current use and are available via the Bielefeld Bioinformatics Server at .