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

A database of protein structure families with common folding motifs.

The availability of fast and robust algorithms for protein structure comparison provides an opportunity to produce a database of three-dimensional comparisons, called families of structurally similar proteins (FSSP). The database currently contains an extended structural family for each of 154 representative (below 30% sequence identity) protein chains. Each data set contains: the search structure; all its relatives with 70-30% sequence identity, aligned structurally; and all other proteins from the representative set that contain substructures significantly similar to the search structure. Very close relatives (above 70% sequence identity) rarely have significant structural differences and are excluded. The alignments of remote relatives are the result of pairwise all-against-all structural comparisons in the set of 154 representative protein chains. The comparisons were carried out with each of three novel automatic algorithms that cover different aspects of protein structure similarity. The user of the database has the choice between strict rigid-body comparisons and comparisons that take into account interdomain motion or geometrical distortions; and, between comparisons that require strictly sequential ordering of segments and comparisons, which allow altered topology of loop connections or chain reversals. The data sets report the structurally equivalent residues in the form of a multiple alignment and as a list of matching fragments to facilitate inspection by three-dimensional graphics. If substructures are ignored, the result is a database of structure alignments of full-length proteins, including those in the twilight zone of sequence similarity.(ABSTRACT TRUNCATED AT 250 WORDS)     

Asymptotic distribution of motifs in a stochastic context-free grammar model of RNA folding

We analyze the distribution of RNA secondary structures given by the Knudsen–Hein stochastic context-free grammar used in the prediction program Pfold. Our main theorem gives relations between the expected number of these motifs—independent of the grammar probabilities. These relations are a consequence of proving that the distribution of base pairs, of helices, and of different types of loops is asymptotically Gaussian in this model of RNA folding. Proof techniques use singularity analysis of probability generating functions. We also demonstrate that these asymptotic results capture well the expected number of RNA base pairs in native ribosomal structures, and certain other aspects of their predicted secondary structures. In particular, we find that the predicted structures largely satisfy the expected relations, although the native structures do not.     

Using motion planning to study RNA folding kinetics.

We propose a novel, motion planning based approach to approximately map the energy landscape of an RNA molecule. A key feature of our method is that it provides a sparse map that captures the main features of the energy landscape which can be analyzed to compute folding kinetics. Our method is based on probabilistic roadmap motion planners that we have previously successfully applied to protein folding. In this paper, we provide evidence that this approach is also well suited to RNA. We compute population kinetics and transition rates on our roadmaps using the master equation for a few moderately sized RNA and show that our results compare favorably with results of other existing methods.     

A kinetic model of RNA folding

The RNA folding process is represented as a Markov process with states corresponding to RNA secondary structures and transition probabilities corresponding to transformations of a secondary structure caused by formation or disintegration of a helix. Transition probabilities (kinetic constants) are determined. A notion of a group of structures is introduced, and it allows to reduce the state space. Energetic and kinetic parameters of pseudoknots are estimated. Algorithms for computation of a kinetic ensemble for structures and groups of structures are presented, as well as their modifications that take into account pseudoknots. The described algorithms are implemented as a procedure for prediction of RNA secondary structure that is included in the package DNA-SUN.     

A comparison of RNA folding measures

Background  

In the last few decades there has been a great deal of discussion concerning whether or not noncoding RNA sequences (ncRNAs) fold in a more well-defined manner than random sequences. In this paper, we investigate several existing measures for how well an RNA sequence folds, and compare the behaviour of these measures over a large range of Rfam ncRNA families. Such measures can be useful in, for example, identifying novel ncRNAs, and indicating the presence of alternate RNA foldings.     

A contact-waiting-time metric and RNA folding rates

Metrics for indirectly predicting the folding rates of RNA sequences are of interest. In this letter, we introduce a simple metric of RNA structural complexity, which accounts for differences in the energetic contributions of RNA base contacts toward RNA structure formation. We apply the metric to RNA sequences whose folding rates were previously determined experimentally. We find that the metric has good correlation (correlation coefficient: −0.95, p?0.01) with the logarithmically transformed folding rates of those RNA sequences. This suggests that the metric can be useful for predicting RNA folding rates. We use the metric to predict the folding rates of bacterial and eukaryotic group II introns. Future applications of the metric (e.g., to predict structural RNAs) could prove fruitful.     

A collapsed non-native RNA folding state

At physiological Mg2+ concentrations, the catalytic core of the bI5 group I intron does not fold into its native structure. In contrast, as judged by the global size, this RNA undergoes structural collapse at Mg 2+ concentrations much lower than required to drive folding of the RNA completely to the native state. The bI5 RNA therefore exists in equilibrium between expanded and collapsed non-native states. The activation energy of RNA folding from the collapsed state to the native state is negligible and the reaction is not accelerated by the addition of urea. This collapsed state is thus distinct from the kinetic traps observed during folding of other large RNAs. The collapsed non-native state forms readily in the case of bI5 RNA and may exist generically prior to assembly of other ribonucleoprotein holoenzymes, such as the ribosome.     

A new principle of RNA folding based on pseudoknotting.

Tertiary interactions involving hairpin or interior loops of RNA can lead to extended quasi-continuous double helical stem regions, consisting of coaxially stacked segments of duplex RNA, bridged by single-stranded connections. This type of compact folding plays a role in various strategic regions of RNA molecules. Their role in ribosome functioning, RNA splicing and recognition of tRNA-like structures is discussed.     

A continuous analog for RNA folding

A linear segment in which a number of pairs of intervals of equal length are identified as potential stems is the subject of a folding problem analogous to inference of RNA secondary structure. A quantity of free energy (or equivalently, energy per unit length) is associated with each stem, and the various types of loops are assigned energy costs as a function of their lengths. Inference of stable structures can then be carried out in the same way as in RNA folding. More important, perturbation of stem lengths and energy densities (modelling various mutational processes affecting nucleotide sequences) allows the delineation of domains of stability of various foldings, through the explicit calculation of their boundaries, in a low-dimensional parameter space.     

Taming the complexity of protein folding

Protein folding is an important problem in structural biology with significant medical implications, particularly for misfolding disorders like Alzheimer's disease. Solving the folding problem will ultimately require a combination of theory and experiment, with theoretical models providing a comprehensive view of folding and experiments grounding these models in reality. Here we review progress towards this goal over the past decade, with an emphasis on recent theoretical advances that are empowering chemically detailed models of folding and the new results these technologies are providing. In particular, we discuss new insights made possible by Markov state models (MSMs), including the role of non-native contacts and the hub-like character of protein folded states.     

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.     

Analysis of RNA motifs

RNA motifs are directed and ordered stacked arrays of non-Watson-Crick base pairs forming distinctive foldings of the phosphodiester backbones of the interacting RNA strands. They correspond to the 'loops' - hairpin, internal and junction - that intersperse the Watson-Crick two-dimensional helices as seen in two-dimensional representations of RNA structure. RNA motifs mediate the specific interactions that induce the compact folding of complex RNAs. RNA motifs also constitute specific protein or ligand binding sites. A given motif is characterized by all the sequences that fold into essentially identical three-dimensional structures with the same ordered array of isosteric non-Watson-Crick base pairs. It is therefore crucial, when analyzing a three-dimensional RNA structure in order to identify and compare motifs, to first classify its non-Watson-Crick base pairs geometrically.     

A structural database for k-turn motifs in RNA

The kink-turn (k-turn) is a common structural motif in RNA that introduces a tight kink into the helical axis. k-turns play an important architectural role in RNA structures and serve as binding sites for a number of proteins. We have created a database of known and postulated k-turn sequences and three-dimensional (3D) structures, available via the internet. This site provides (1) a database of sequence and structure, as a resource for the RNA community, and (2) a tool to enable the manipulation and comparison of 3D structures where known.     

The annotation of RNA motifs

The recent deluge of new RNA structures, including complete atomic-resolution views of both subunits of the ribosome, has on the one hand literally overwhelmed our individual abilities to comprehend the diversity of RNA structure, and on the other hand presented us with new opportunities for comprehensive use of RNA sequences for comparative genetic, evolutionary and phylogenetic studies. Two concepts are key to understanding RNA structure: hierarchical organization of global structure and isostericity of local interactions. Global structure changes extremely slowly, as it relies on conserved long-range tertiary interactions. Tertiary RNA-RNA and quaternary RNA-protein interactions are mediated by RNA motifs, defined as recurrent and ordered arrays of non-Watson-Crick base-pairs. A single RNA motif comprises a family of sequences, all of which can fold into the same three-dimensional structure and can mediate the same interaction(s). The chemistry and geometry of base pairing constrain the evolution of motifs in such a way that random mutations that occur within motifs are accepted or rejected insofar as they can mediate a similar ordered array of interactions. The steps involved in the analysis and annotation of RNA motifs in 3D structures are: (a) decomposition of each motif into non-Watson-Crick base-pairs; (b) geometric classification of each basepair; (c) identification of isosteric substitutions for each basepair by comparison to isostericity matrices; (d) alignment of homologous sequences using the isostericity matrices to identify corresponding positions in the crystal structure; (e) acceptance or rejection of the null hypothesis that the motif is conserved.     

Beyond kinetic traps in RNA folding.

Large RNAs often have rugged folding energy landscapes that result in severe misfolding and slow folding kinetics. Several interdependent parameters that contribute to misfolding are now well understood and examples of large RNAs and ribonucleoproteins that avoid kinetic traps have been reported. These advances have facilitated the exploration of fundamental RNA folding processes that were previously inaccessible.     

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.