An approximation of loop free energy values of RNA H-pseudoknots

A database of flavivirus RNA structures with a search algorithm for pseudoknots and triple base interactions

Motivation

The Flavivirus genus includes several important pathogens, such as Zika, dengue and yellow fever virus. Flavivirus RNA genomes contain a number of functionally important structures in their 3′ untranslated regions (3′UTRs). Due to the diversity of sequences and topologies of these structures, their identification is often difficult. In contrast, predictions of such structures are important for understanding of flavivirus replication cycles and development of antiviral strategies.

Results

We have developed an algorithm for structured pattern search in RNA sequences, including secondary structures, pseudoknots and triple base interactions. Using the data on known conserved flavivirus 3′UTR structures, we constructed structural descriptors which covered the diversity of patterns in these motifs. The descriptors and the search algorithm were used for the construction of a database of flavivirus 3′UTR structures. Validating this approach, we identified a number of domains matching a general pattern of exoribonuclease Xrn1-resistant RNAs in the growing group of insect-specific flaviviruses.

Availability and implementation

The Leiden Flavivirus RNA Structure Database is available at https://rna.liacs.nl. The search algorithm is available at https://github.com/LeidenRNA/SRHS.

Supplementary information

Supplementary data are available at Bioinformatics online.

A Polymer Physics Framework for the Entropy of Arbitrary Pseudoknots

The accurate prediction of RNA secondary structure from primary sequence has had enormous impact on research from the past 40 years. Although many algorithms are available to make these predictions, the inclusion of non-nested loops, termed pseudoknots, still poses challenges arising from two main factors: 1) no physical model exists to estimate the loop entropies of complex intramolecular pseudoknots, and 2) their NP-complete enumeration has impeded their study. Here, we address both challenges. First, we develop a polymer physics model that can address arbitrarily complex pseudoknots using only two parameters corresponding to concrete physical quantities-over an order of magnitude fewer than the sparsest state-of-the-art phenomenological methods. Second, by coupling this model to exhaustive enumeration of the set of possible structures, we compute the entire free energy landscape of secondary structures resulting from a primary RNA sequence. We demonstrate that for RNA structures of ∼80 nucleotides, with minimal heuristics, the complete enumeration of possible secondary structures can be accomplished quickly despite the NP-complete nature of the problem. We further show that despite our loop entropy model's parametric sparsity, it performs better than or on par with previously published methods in predicting both pseudoknotted and non-pseudoknotted structures on a benchmark data set of RNA structures of ≤80 nucleotides. We suggest ways in which the accuracy of the model can be further improved.

The free-energy cost of interaction between DNA loops

From the viewpoint of thermodynamics, the formation of DNA loops and the interaction between them, which are all non-equilibrium processes, result in the change of free energy, affecting gene expression and further cell-to-cell variability as observed experimentally. However, how these processes dissipate free energy remains largely unclear. Here, by analyzing a mechanic model that maps three fundamental topologies of two interacting DNA loops into a 4-state model of gene transcription, we first show that a longer DNA loop needs more mean free energy consumption. Then, independent of the type of interacting two DNA loops (nested, side-by-side or alternating), the promotion between them always consumes less mean free energy whereas the suppression dissipates more mean free energy. More interestingly, we find that in contrast to the mechanism of direct looping between promoter and enhancer, the facilitated-tracking mechanism dissipates less mean free energy but enhances the mean mRNA expression, justifying the facilitated-tracking hypothesis, a long-standing debate in biology. Based on minimal energy principle, we thus speculate that organisms would utilize the mechanisms of loop-loop promotion and facilitated tracking to survive in complex environments. Our studies provide insights into the understanding of gene expression regulation mechanism from the view of energy consumption.

RNA structural constraints in the evolution of the influenza A virus genome NP segment

Conserved RNA secondary structures were predicted in the nucleoprotein (NP) segment of the influenza A virus genome using comparative sequence and structure analysis. A number of structural elements exhibiting nucleotide covariations were identified over the whole segment length, including protein-coding regions. Calculations of mutual information values at the paired nucleotide positions demonstrate that these structures impose considerable constraints on the virus genome evolution. Functional importance of a pseudoknot structure, predicted in the NP packaging signal region, was confirmed by plaque assays of the mutant viruses with disrupted structure and those with restored folding using compensatory substitutions. Possible functions of the conserved RNA folding patterns in the influenza A virus genome are discussed.

The determination of RNA folding nearest neighbor parameters

The stability of RNA secondary structure can be predicted using a set of nearest neighbor parameters. These parameters are widely used by algorithms that predict secondary structure. This contribution introduces the UV optical melting experiments that are used to determine the folding stability of short RNA strands. It explains how the nearest neighbor parameters are chosen and how the values are fit to the data. A sample nearest neighbor calculation is provided. The contribution concludes with new methods that use the database of sequences with known structures to determine parameter values.

Thermodynamic characterization of the Saccharomyces cerevisiae telomerase RNA pseudoknot domain in vitro

Recent structural and functional characterization of the pseudoknot in the Saccharomyces cerevisiae telomerase RNA (TLC1) has demonstrated that tertiary structure is present, similar to that previously described for the human and Kluyveromyces lactis telomerase RNAs. In order to biophysically characterize the identified pseudoknot secondary and tertiary structures, UV-monitored thermal denaturation experiments, nuclear magnetic resonance spectroscopy, and native gel electrophoresis were used to investigate various potential conformations in the pseudoknot domain in vitro, in the absence of the telomerase protein. Here, we demonstrate that alternative secondary structures are not mutually exclusive in the S. cerevisiae telomerase RNA, tertiary structure contributes 1.5 kcal mol(-1) to the stability of the pseudoknot (≈ half the stability observed for the human telomerase pseudoknot), and identify additional base pairs in the 3' pseudoknot stem near the helical junction. In addition, sequence conservation in an adjacent overlapping hairpin appears to prevent dimerization and alternative conformations in the context of the entire pseudoknot-containing region. Thus, this work provides a detailed in vitro characterization of the thermodynamic features of the S. cerevisiae TLC1 pseudoknot region for comparison with other telomerase RNA pseudoknots.

Statistical mechanical modeling of RNA folding: from free energy landscape to tertiary structural prediction

In spite of the success of computational methods for predicting RNA secondary structure, the problem of predicting RNA tertiary structure folding remains. Low-resolution structural models show promise as they allow for rigorous statistical mechanical computation for the conformational entropies, free energies, and the coarse-grained structures of tertiary folds. Molecular dynamics refinement of coarse-grained structures leads to all-atom 3D structures. Modeling based on statistical mechanics principles also has the unique advantage of predicting the full free energy landscape, including local minima and the global free energy minimum. The energy landscapes combined with the 3D structures form the basis for quantitative predictions of RNA functions. In this chapter, we present an overview of statistical mechanical models for RNA folding and then focus on a recently developed RNA statistical mechanical model -- the Vfold model. The main emphasis is placed on the physics underpinning the models, the computational strategies, and the connections to RNA biology.

RNA fragment modeling with a nucleobase discrete-state model

In this work we develop an approach for predicting the tertiary structures of RNA fragments by combining an RNA nucleobase discrete state (RNAnbds) model, a sequential Monte Carlo method, and a statistical potential. The RNAnbds model is designed for optimizing the configuration of nucleobases with respect to their preceding ones along the sequence and their spatial neighbors, in contrast to previous works that focus on RNA backbones. The tests of our approach with the fragments taken from a small RNA pseudoknot and a 23S ribosome RNA show that for short fragments (<10 nucleotides), the root mean square deviations (RMSDs) between the predicted and the experimental ones are generally smaller than 3 Å; for slightly longer fragments (10-15 nucleotides), most RMSDs are smaller than 4 Å. The comparison of our method with another physics-based predictor with a testing set containing nine loops shows that ours is superior in both accuracy and efficiency. Our approach is useful in facilitating RNA three-dimensional structure prediction as well as loop modeling. It also holds the promise of providing insight into the structural ensembles of RNA loops.

A domain-based model for predicting large and complex pseudoknotted structures

Pseudoknotted structures play important structural and functional roles in RNA cellular functions at the level of transcription, splicing and translation. However, the problem of computational prediction for large pseudoknotted folds remains. Here we develop a domain-based method for predicting complex and large pseudoknotted structures from RNA sequences. The model is based on the observation that large RNAs can be separated into different structural domains. The basic idea is to first identify the domains and then predict the structures for each domain. Assembly of the domain structures gives the full structure. The use of the domain-based approach leads to a reduction of computational time by a factor of about ~N ( 2) for an N-nt sequence. As applications of the model, we predict structures for a variety of RNA systems, such as regions in human telomerase RNA (hTR), internal ribosome entry site (IRES) and HIV genome. The lengths of these sequences range from 200-nt to 400-nt. The results show good agreements with the experiments.

Fast folding of RNA pseudoknots initiated by laser temperature-jump

RNA pseudoknots are examples of minimal structural motifs in RNA with tertiary interactions that stabilize the structures of many ribozymes. They also play an essential role in a variety of biological functions that are modulated by their structure, stability, and dynamics. Therefore, understanding the global principles that determine the thermodynamics and folding pathways of RNA pseudoknots is an important problem in biology, both for elucidating the folding mechanisms of larger ribozymes as well as addressing issues of possible kinetic control of the biological functions of pseudoknots. We report on the folding/unfolding kinetics of a hairpin-type pseudoknot obtained with microsecond time-resolution in response to a laser temperature-jump perturbation. The kinetics are monitored using UV absorbance as well as fluorescence of extrinsically attached labels as spectroscopic probes of the transiently populated RNA conformations. We measure folding times of 1-6 ms at 37 °C, which are at least 100-fold faster than previous observations of very slow folding pseudoknots that were trapped in misfolded conformations. The measured relaxation times are remarkably similar to predictions of a computational study by Thirumalai and co-workers (Cho, S. S.; Pincus, D.L.; Thirumalai, D. Proc. Natl. Acad. Sci. U. S. A. 2009, 106, 17349-17354). Thus, these studies provide the first observation of a fast-folding pseudoknot and present a benchmark against which computational models can be refined.

Computing the conformational entropy for RNA folds

We develop a polymer physics-based method to compute the conformational entropy for RNA tertiary folds, namely, conformations consisting of multiple helices connected through (cross-linked) loops. The theory is based on a virtual bond conformational model for the nucleotide chain. A key issue in the calculation of the entropy is how to treat the excluded volume interactions. The weak excluded volume interference between the different loops leads to the decomposition of the whole structure into a number of three-body building blocks, each consisting of a loop and two helices connected to the two ends of the loop. The simple construct of the three-body system allows an accurate computation for the conformational entropy for each building block. The assembly of the building blocks gives the entropy of the whole structure. This approach enables treatment of molten globule-like folds (partially unfolded tertiary structures) for RNAs. Extensive tests against experiments and exact computer enumerations indicate that the method can give accurate results for the entropy. The method developed here provides a solid first step toward a systematic development of a theory for the entropy and free energy landscape for complex tertiary folds for RNAs and proteins.

ProbKnot: fast prediction of RNA secondary structure including pseudoknots

It is a significant challenge to predict RNA secondary structures including pseudoknots. Here, a new algorithm capable of predicting pseudoknots of any topology, ProbKnot, is reported. ProbKnot assembles maximum expected accuracy structures from computed base-pairing probabilities in O(N(2)) time, where N is the length of the sequence. The performance of ProbKnot was measured by comparing predicted structures with known structures for a large database of RNA sequences with fewer than 700 nucleotides. The percentage of known pairs correctly predicted was 69.3%. Additionally, the percentage of predicted pairs in the known structure was 61.3%. This performance is the highest of four tested algorithms that are capable of pseudoknot prediction. The program is available for download at: http://rna.urmc.rochester.edu/RNAstructure.html.

Prediction of RNA multiloop and pseudoknot conformations from a lattice-based, coarse-grain tertiary structure model

We present a semiquantitative lattice model of RNA folding, which is able to reproduce complex folded structures such as multiloops and pseudoknots without relying on the frequently employed ad hoc generalization of the Jacobson-Stockmayer loop entropy. We derive the model parameters from the Turner description of simple secondary structural elements and pay particular attention to the unification of mismatch and coaxial stacking parameters as well as of border and nonlocal loop parameters, resulting in a reduced, unified parameter set for simple loops of arbitrary type and size. For elementary structures, the predictive power of the model is comparable to the standard secondary structure approaches, from which its parameters are derived. For complex structures, our approach offers a systematic treatment of generic effects of chain connectivity as well as of excluded volume or attractive interactions between and within all elements of the secondary structure. We reproduce the native structures of tRNA multiloops and of viral frameshift signal pseudoknots.

Fluorescence competition assay measurements of free energy changes for RNA pseudoknots

RNA pseudoknots have important functions, and thermodynamic stability is a key to predicting pseudoknots in RNA sequences and to understanding their functions. Traditional methods, such as UV melting and differential scanning calorimetry, for measuring RNA thermodynamics are restricted to temperature ranges around the melting temperature for a pseudoknot. Here, we report RNA pseudoknot free energy changes at 37 °C measured by fluorescence competition assays. Sequence-dependent studies for the loop 1−stem 2 region reveal (1) the individual nearest-neighbor hydrogen bonding (INN-HB) model provides a reasonable estimate for the free energy change when a Watson−Crick base pair in stem 2 is changed, (2) the loop entropy can be estimated by a statistical polymer model, although some penalty for certain loop sequences is necessary, and (3) tertiary interactions can significantly stabilize pseudoknots and extending the length of stem 2 may alter tertiary interactions such that the INN-HB model does not predict the net effect of adding a base pair. The results can inform writing of algorithms for predicting and/or designing RNA secondary structures.

DotKnot: pseudoknot prediction using the probability dot plot under a refined energy model

RNA pseudoknots are functional structure elements with key roles in viral and cellular processes. Prediction of a pseudoknotted minimum free energy structure is an NP-complete problem. Practical algorithms for RNA structure prediction including restricted classes of pseudoknots suffer from high runtime and poor accuracy for longer sequences. A heuristic approach is to search for promising pseudoknot candidates in a sequence and verify those. Afterwards, the detected pseudoknots can be further analysed using bioinformatics or laboratory techniques. We present a novel pseudoknot detection method called DotKnot that extracts stem regions from the secondary structure probability dot plot and assembles pseudoknot candidates in a constructive fashion. We evaluate pseudoknot free energies using novel parameters, which have recently become available. We show that the conventional probability dot plot makes a wide class of pseudoknots including those with bulged stems manageable in an explicit fashion. The energy parameters now become the limiting factor in pseudoknot prediction. DotKnot is an efficient method for long sequences, which finds pseudoknots with higher accuracy compared to other known prediction algorithms. DotKnot is accessible as a web server at http://dotknot.csse.uwa.edu.au.

Prediction of geometrically feasible three-dimensional structures of pseudoknotted RNA through free energy estimation

Accurate free energy estimation is essential for RNA structure prediction. The widely used Turner's energy model works well for nested structures. For pseudoknotted RNAs, however, there is no effective rule for estimation of loop entropy and free energy. In this work we present a new free energy estimation method, termed the pseudoknot predictor in three-dimensional space (pk3D), which goes beyond Turner's model. Our approach treats nested and pseudoknotted structures alike in one unifying physical framework, regardless of how complex the RNA structures are. We first test the ability of pk3D in selecting native structures from a large number of decoys for a set of 43 pseudoknotted RNA molecules, with lengths ranging from 23 to 113. We find that pk3D performs slightly better than the Dirks and Pierce extension of Turner's rule. We then test pk3D for blind secondary structure prediction, and find that pk3D gives the best sensitivity and comparable positive predictive value (related to specificity) in predicting pseudoknotted RNA secondary structures, when compared with other methods. A unique strength of pk3D is that it also generates spatial arrangement of structural elements of the RNA molecule. Comparison of three-dimensional structures predicted by pk3D with the native structure measured by nuclear magnetic resonance or X-ray experiments shows that the predicted spatial arrangement of stems and loops is often similar to that found in the native structure. These close-to-native structures can be used as starting points for further refinement to derive accurate three-dimensional structures of RNA molecules, including those with pseudoknots.

In vitro and in vivo studies of the RNA conformational switch in Alfalfa mosaic virus

The 3' termini of Alfalfa mosaic virus (AMV) RNAs adopt two mutually exclusive conformations, a coat protein binding (CPB) and a tRNA-like (TL) conformer, which consist of a linear array of stem-loop structures and a pseudoknot structure, respectively. Previously, switching between CPB and TL conformers has been proposed as a mechanism to regulate the competing processes of translation and replication of the viral RNA (R. C. L. Olsthoorn et al., EMBO J. 18:4856-4864, 1999). In the present study, the switch between CPB and TL conformers was further investigated. First, we showed that recognition of the AMV 3' untranslated region (UTR) by a tRNA-specific enzyme (CCA-adding enzyme) in vitro is more efficient when the distribution is shifted toward the TL conformation. Second, the recognition of the 3' UTR by the viral replicase was similarly dependent on the ratio of CBP and TL conformers. Furthermore, the addition of CP, which is expected to shift the distribution toward the CPB conformer, inhibited recognition by the CCA-adding enzyme and the replicase. Finally, we monitored how the binding affinity to CP is affected by this conformational switch in the yeast three-hybrid system. Here, disruption of the pseudoknot enhanced the binding affinity to CP by shifting the balance in favor of the CPB conformer, whereas stabilizing the pseudoknot did the reverse. Together, the in vitro and in vivo data clearly demonstrate the existence of the conformational switch in the 3' UTR of AMV RNAs.

NNDB: the nearest neighbor parameter database for predicting stability of nucleic acid secondary structure

The Nearest Neighbor Database (NNDB, http://rna.urmc.rochester.edu/NNDB) is a web-based resource for disseminating parameter sets for predicting nucleic acid secondary structure stabilities. For each set of parameters, the database includes the set of rules with descriptive text, sequence-dependent parameters in plain text and html, literature references to experiments and usage tutorials. The initial release covers parameters for predicting RNA folding free energy and enthalpy changes.

The jerky and knotty dynamics of RNA

RNA is known to exhibit a jerky dynamics, as intramolecular thermal motion, on <0.1 micros time scales, is punctuated by infrequent structural rearrangements on much longer time scales, i.e. from >10 micros up to a few minutes or even hours. These rare stochastic events correspond to the formation or dissociation of entire stems through cooperative base pairing/unpairing transitions. Such a clear separation of time scales in RNA dynamics has made it possible to implement coarse grained RNA simulations, which predict RNA folding and unfolding pathways including kinetically trapped structures on biologically relevant time scales of seconds to minutes. RNA folding simulations also enable to predict the formation of pseudoknots, that is, helices interior to loops, which mechanically restrain the relative orientations of other non-nested helices. But beyond static structural constraints, pseudoknots can also strongly affect the folding and unfolding dynamics of RNA, as the order by which successive helices are formed and dissociated can lead to topologically blocked transition intermediates. The resulting knotty dynamics can enhance the stability of RNA switches, improve the efficacy of co-transcriptional folding pathways and lead to unusual self-assembly properties of RNA.

Predicting structures and stabilities for H-type pseudoknots with interhelix loops

RNA pseudoknots play a critical role in RNA-related biology from the assembly of ribosome to the regulation of viral gene expression. A predictive model for pseudoknot structure and stability is essential for understanding and designing RNA structure and function. A previous statistical mechanical theory allows us to treat canonical H-type RNA pseudoknots that contain no intervening loop between the helices (see S. Cao and S.J. Chen [2006] in Nucleic Acids Research, Vol. 34; pp. 2634-2652). Biologically significant RNA pseudoknots often contain interhelix loops. Predicting the structure and stability for such more-general pseudoknots remains an unsolved problem. In the present study, we develop a predictive model for pseudoknots with interhelix loops. The model gives conformational entropy, stability, and the free-energy landscape from RNA sequences. The main features of this new model are the computation of the conformational entropy and folding free-energy base on the complete conformational ensemble and rigorous treatment for the excluded volume effects. Extensive tests for the structural predictions show overall good accuracy with average sensitivity and specificity equal to 0.91 and 0.91, respectively. The theory developed here may be a solid starting point for first-principles modeling of more complex, larger RNAs.

RNA folding: conformational statistics, folding kinetics, and ion electrostatics

RNA folding is a remarkably complex problem that involves ion-mediated electrostatic interaction, conformational entropy, base pairing and stacking, and noncanonical interactions. During the past decade, results from a variety of experimental and theoretical studies pointed to (a) the potential ion correlation effect in Mg2+-RNA interactions, (b) the rugged energy landscapes and multistate RNA folding kinetics even for small RNA systems such as hairpins and pseudoknots, (c) the intraloop interactions and sequence-dependent loop free energy, and (d) the strong nonadditivity of chain entropy in RNA pseudoknot and other tertiary folds. Several related issues, which have not been thoroughly resolved, require combined approaches with thermodynamic and kinetic experiments, statistical mechanical modeling, and all-atom computer simulations.

KnotSeeker: heuristic pseudoknot detection in long RNA sequences

Pseudoknots are folded structures in RNA molecules that perform essential functions as part of cellular transcription machinery and regulatory processes. The prediction of these structures in RNA molecules has important implications in antiviral drug design. It has been shown that the prediction of pseudoknots is an NP-complete problem. Practical structure prediction algorithms based on free energy minimization employ a restricted problem class and dynamic programming. However, these algorithms are computationally very expensive, and their accuracy deteriorates if the input sequence containing the pseudoknot is too long. Heuristic methods can be more efficient, but do not guarantee an optimal solution in regards to the minimum free energy model. We present KnotSeeker, a new heuristic algorithm for the detection of pseudoknots in RNA sequences as a preliminary step for structure prediction. Our method uses a hybrid sequence matching and free energy minimization approach to perform a screening of the primary sequence. We select short sequence fragments as possible candidates that may contain pseudoknots and verify them by using an existing dynamic programming algorithm and a minimum weight independent set calculation. KnotSeeker is significantly more accurate in detecting pseudoknots compared to other common methods as reported in the literature. It is very efficient and therefore a practical tool, especially for long sequences. The algorithm has been implemented in Python and it also uses C/C++ code from several other known techniques. The code is available from http://www.csse.uwa.edu.au/~datta/pseudoknot.

Folding thermodynamics of pseudoknotted chain conformations

We develop a statistical mechanical framework for the folding thermodynamics of pseudoknotted structures. As applications of the theory, we investigate the folding stability and the free energy landscapes for both the thermal and the mechanical unfolding of pseudoknotted chains. For the mechanical unfolding process, we predict the force-extension curves, from which we can obtain the information about structural transitions in the unfolding process. In general, a pseudoknotted structure unfolds through multiple structural transitions. The interplay between the helix stems and the loops plays an important role in the folding stability of pseudoknots. For instance, variations in loop sizes can lead to the destabilization of some intermediate states and change the (equilibrium) folding pathways (e.g., two helix stems unfold either cooperatively or sequentially). In both thermal and mechanical unfolding, depending on the nucleotide sequence, misfolded intermediate states can emerge in the folding process. In addition, thermal and mechanical unfoldings often have different (equilibrium) pathways. For example, for certain sequences, the misfolded intermediates, which generally have longer tails, can fold, unfold, and refold again in the pulling process, which means that these intermediates can switch between two different average end-end extensions.

A distinct group of hepacivirus/pestivirus-like internal ribosomal entry sites in members of diverse picornavirus genera: evidence for modular exchange of functional noncoding RNA elements by recombination

The 5' untranslated regions (UTRs) of the RNA genomes of Flaviviridae of the Hepacivirus and Pestivirus genera contain internal ribosomal entry sites (IRESs) that are unrelated to the two principal classes of IRESs of Picornaviridae. The mechanism of translation initiation on hepacivirus/pestivirus (HP) IRESs, which involves factor-independent binding to ribosomal 40S subunits, also differs fundamentally from initiation on these picornavirus IRESs. Ribosomal binding to HP IRESs requires conserved sequences that form a pseudoknot and the adjacent IIId and IIIe domains; analogous elements do not occur in the two principal groups of picornavirus IRESs. Here, comparative sequence analysis was used to identify a subset of picornaviruses from multiple genera that contain 5' UTR sequences with significant similarities to HP IRESs. They are avian encephalomyelitis virus, duck hepatitis virus 1, duck picornavirus, porcine teschovirus, porcine enterovirus 8, Seneca Valley virus, and simian picornavirus. Their 5' UTRs are predicted to form several structures, in some of which the peripheral elements differ from the corresponding HP IRES elements but in which the core pseudoknot, domain IIId, and domain IIIe elements are all closely related. These findings suggest that HP-like IRESs have been exchanged between unrelated virus families by recombination and support the hypothesis that RNA viruses consist of modular coding and noncoding elements that can exchange and evolve independently.

High sensitivity RNA pseudoknot prediction

Most ab initio pseudoknot predicting methods provide very few folding scenarios for a given RNA sequence and have low sensitivities. RNA researchers, in many cases, would rather sacrifice the specificity for a much higher sensitivity for pseudoknot detection. In this study, we introduce the Pseudoknot Local Motif Model and Dynamic Partner Sequence Stacking (PLMM_DPSS) algorithm which predicts all PLM model pseudoknots within an RNA sequence in a neighboring-region-interference-free fashion. The PLM model is derived from the existing Pseudobase entries. The innovative DPSS approach calculates the optimally lowest stacking energy between two partner sequences. Combined with the Mfold, PLMM_DPSS can also be used in predicting complicated pseudoknots. The test results of PLMM_DPSS, PKNOTS, iterated loop matching, pknotsRG and HotKnots with Pseudobase sequences have shown that PLMM_DPSS is the most sensitive among the five methods. PLMM_DPSS also provides manageable pseudoknot folding scenarios for further structure determination.

Pseudoknots in RNA secondary structures: representation, enumeration, and prevalence

A number of non-coding RNA are known to contain functionally important or conserved pseudoknots. However, pseudoknotted structures are more complex than orthodox, and most methods for analyzing secondary structures do not handle them. I present here a way to decompose and represent general secondary structures which extends the tree representation of the stem-loop structure, and use this to analyze the frequency of pseudoknots in known and in random secondary structures. This comparison shows that, though a number of pseudoknots exist, they are still relatively rare and mostly of the simpler kinds. In contrast, random secondary structures tend to be heavily knotted, and the number of available structures increases dramatically when allowing pseudoknots. Therefore, methods for structure prediction and non-coding RNA identification that allow pseudoknots are likely to be much less powerful than those that do not, unless they penalize pseudoknots appropriately.

Statistical thermodynamics for chain molecules with simple RNA tertiary contacts

A statistical thermodynamic model is developed for chain molecules with simple RNA tertiary contacts. The model, which accounts for the excluded volume effect and the nonadditivity in the free energy, enables reliable predictions for the conformational entropy and partition function for simple tertiary folds. Illustrative applications are made to conformational transitions involving simple tertiary contacts. The model can predict the interplay between the secondary and the tertiary interactions in the conformational changes. Though the present form of the theory is tested and validated in a two-dimensional lattice model, the methodology, which is developed based on a general graphical representation for chain conformations, is applicable to any off-lattice chain representations. Moreover, the analytical formulation of the method makes possible the systematic development of the theory for more complex tertiary structures.

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.

Conformational entropy of a pseudoknot polymer

The thermodynamics and kinetics of ABAB pseudoknot formation owing to reversible intrachain reactions are investigated for a flexible polymer based on the off-lattice Monte Carlo simulations. The polymer is made of N hard spheres tethered by inextensible bonds and consists of two reactive pairs AA and BB with binding energies -epsilon1 and -epsilon2, respectively, and three loop lengths (l1, l2, and l3). Although two intermediate states, loops A and B, may be formed, the folding path goes mainly through the intermediate loop whose free energy reduction associated with coil-to-loop crossover is greater. The conformational entropy loss is found to follow DeltaS=alpha ln N+G, where alpha approximately 2.48 for coil-loop crossover and alpha approximately 2.43 for loop-pseudoknot crossover. The constant G depends on the three loop lengths and the two end-to-reactive site lengths (L1 and L2). For a given total loop length, G is maximum when the three loop lengths are equal (l1=l2=l3). When l1=l3, the entropy loss is minimum if l2=0. However, the condition l1 not equal l3 makes G even smaller. This consequence indicates that asymmetry in loop lengths is thermodynamically favorable and this fact is consistent with observations of pseudoknotted RNA structures.

Asymmetry in RNA pseudoknots: observation and theory

RNA can fold into a topological structure called a pseudoknot, composed of non-nested double-stranded stems connected by single-stranded loops. Our examination of the PseudoBase database of pseudoknotted RNA structures reveals asymmetries in the stem and loop lengths and provocative composition differences between the loops. By taking into account differences between major and minor grooves of the RNA double helix, we explain much of the asymmetry with a simple polymer physics model and statistical mechanical theory, with only one adjustable parameter.

Design, implementation and evaluation of a practical pseudoknot folding algorithm based on thermodynamics

BACKGROUND

The general problem of RNA secondary structure prediction under the widely used thermodynamic model is known to be NP-complete when the structures considered include arbitrary pseudoknots. For restricted classes of pseudoknots, several polynomial time algorithms have been designed, where the O(n6)time and O(n4) space algorithm by Rivas and Eddy is currently the best available program.

RESULTS

We introduce the class of canonical simple recursive pseudoknots and present an algorithm that requires O(n4) time and O(n2) space to predict the energetically optimal structure of an RNA sequence, possible containing such pseudoknots. Evaluation against a large collection of known pseudoknotted structures shows the adequacy of the canonization approach and our algorithm.

CONCLUSIONS

RNA pseudoknots of medium size can now be predicted reliably as well as efficiently by the new algorithm.

Prediction of consensus RNA secondary structures including pseudoknots

Most functional RNA molecules have characteristic structures that are highly conserved in evolution. Many of them contain pseudoknots. Here, we present a method for computing the consensus structures including pseudoknots based on alignments of a few sequences. The algorithm combines thermodynamic and covariation information to assign scores to all possible base pairs, the base pairs are chosen with the help of the maximum weighted matching algorithm. We applied our algorithm to a number of different types of RNA known to contain pseudoknots. All pseudoknots were predicted correctly and more than 85 percent of the base pairs were identified.

Prediction and statistics of pseudoknots in RNA structures using exactly clustered stochastic simulations

Ab initio RNA secondary structure predictions have long dismissed helices interior to loops, so-called pseudoknots, despite their structural importance. Here we report that many pseudoknots can be predicted through long-time-scale RNA-folding simulations, which follow the stochastic closing and opening of individual RNA helices. The numerical efficacy of these stochastic simulations relies on an O(n2) clustering algorithm that computes time averages over a continuously updated set of n reference structures. Applying this exact stochastic clustering approach, we typically obtain a 5- to 100-fold simulation speed-up for RNA sequences up to 400 bases, while the effective acceleration can be as high as 105-fold for short, multistable molecules ( Collapse

Key Words Collapse

MESH Headings

• Algorithms
• Base Sequence
• Computer Simulation
• Molecular Sequence Data
• Nucleic Acid Conformation
• RNA/chemistry
• Stochastic Processes

Collapse

Grants Collapse

Affiliation(s)

A Xayaphoummine Laboratoire de Dynamique des Fluides Complexes, Centre National de la Recherche Scientifique-Université Louis Pasteur, Institut de Physique, 3 Rue de l'Université, 67000 Strasbourg, France
T Bucher
F Thalmann
H Isambert

Collapse

A partition function algorithm for nucleic acid secondary structure including pseudoknots

Nucleic acid secondary structure models usually exclude pseudoknots due to the difficulty of treating these nonnested structures efficiently in structure prediction and partition function algorithms. Here, the standard secondary structure energy model is extended to include the most physically relevant pseudoknots. We describe an O(N(5)) dynamic programming algorithm, where N is the length of the strand, for computing the partition function and minimum energy structure over this class of secondary structures. Hence, it is possible to determine the probability of sampling the lowest energy structure, or any other structure of particular interest. This capability motivates the use of the partition function for the design of DNA or RNA molecules for bioengineering applications.

Mutations linked to dyskeratosis congenita cause changes in the structural equilibrium in telomerase RNA

Autosomal dominant dyskeratosis congenita (DKC), as well as aplastic anemia, has been linked to mutations in the RNA component of telomerase, the ribonucleoprotein responsible for telomere maintenance. Here we examine the effect of the DKC mutations on the structure and stability of human telomerase RNA pseudoknot and CR7 domains by using NMR and thermal melting. The CR7 domain point mutation decreases stability and alters a conserved secondary structure thought to be involved in human telomerase RNA accumulation in vivo. We find that pseudoknot constructs containing the conserved elements of the pseudoknot domain are in equilibrium with a hairpin conformation. The solution structure of the wild-type hairpin reveals that it forms a continuous helix containing a novel run of three consecutive U.U and a U.C base pairs closed by a pentaloop. The six base pairs unique to the hairpin conformation are phylogenetically conserved in mammals, suggesting that this conformation is also functionally important. The DKC mutation in the pseudoknot domain results in a shift in the equilibrium toward the hairpin form, primarily due to destabilization of the pseudoknot. Our results provide insight into the effect of these mutations on telomerase structure and suggest that the catalytic cycle of telomerase involves a delicate interplay between RNA conformational states, alteration of which leads to the disease state.

Do mRNA and rRNA binding sites of E.coli ribosomal protein S15 share common structural determinants?

Escherichia coli ribosomal protein S15 recognizes two RNA targets: a three-way junction in 16S rRNA and a pseudoknot structure on its own mRNA. Binding to mRNA occurs when S15 is expressed in excess over its rRNA target, resulting in an inhibition of translation start. The sole apparent similarity between the rRNA and mRNA targets is the presence of a G-U/G-C motif that contributes only modestly to rRNA binding but is essential for mRNA. To get more information on the structural determinants used by S15 to bind its mRNA target as compared to its rRNA site, we used site-directed mutagenesis, substitution by nucleotide analogs, footprinting experiments on both RNA and protein, and graphic modeling. The size of the mRNA-binding site could be reduced to 45 nucleotides, without loss of affinity. This short RNA preferentially folds into a pseudoknot, the formation of which depends on magnesium concentration and temperature. The size of the loop L2 that bridges the two stems of the pseudoknot through the minor groove could not be reduced below nine nucleotides. Then we showed that the pseudoknot recognizes the same side of S15 as 16S rRNA, although shielding a smaller surface area. It turned out that the G-U/G-C motif is recognized from the minor groove in both cases, and that the G-C pair is recognized in a very similar manner. However, the wobble G-U pair of the mRNA is not directly contacted by S15, as in rRNA, but is most likely involved in building a precise conformation of the RNA, essential for binding. Otherwise, unique specific features are utilized, such as the three-way junction in the case of 16S rRNA and the looped out A(-46) for the mRNA pseudoknot.

The 5' and 3' extremities of the satellite tobacco necrosis virus translational enhancer domain contribute differentially to stimulation of translation

The translational enhancer domain (TED) of satellite tobacco necrosis virus (STNV) RNA stimulates translation of uncapped RNAs autonomously. Here we set out to identify the 5' and 3' extremities of TED and features of these sequences with respect to translation. We found that both in wheat germ extract and in tobacco protoplasts, the 5' border is confined to 3 nt. Mutational analysis revealed that the autonomous function of TED is sensitive to 5' flanking sequences. At the 3' end of TED, 23 nt have a cumulative, quantitative effect on translation in wheat germ extract, whereas in tobacco protoplasts, the most 3' 14 nt of these 23 nt do not enhance translation. The 5' and 3' sequence requirements triggered the development of a new secondary structure model. In this model, TED folds into a phylogenetically conserved stem-loop structure in which the essential 5' nucleotides base-pair with the 3' nucleotides that stimulate translation both in vitro and in vivo. Importantly, the 14 3' nucleotides in TED that stimulate translation in the wheat germ extract only do not require the predicted base-pairing in order to function. The discrepancy between in vitro and in vivo sequence requirements thus correlates with potential base-pairing requirements, opening the possibility that TED contains two functional domains.

Sequence comparison and secondary structure analysis of the 3' noncoding region of flavivirus genomes reveals multiple pseudoknots

Sequences of 191 flavivirus RNAs belonging to four sero-groups were used to predict the secondary structure of the 3' noncoding region (3' NCR) directly upstream of the conserved terminal hairpin. In mosquito-borne flavivirus RNAs (n = 164) a characteristic structure element was identified that includes a phylogenetically well-supported pseudoknot. This element is repeated in the dengue and Japanese encephalitis RNAs and centers around the conserved sequences CS2 and RCS2. In yellow fever virus RNAs that contain one CS2 motif, only one copy of this pseudoknotted structure was found. The conserved pseudoknotted element is absent from the 3' NCR of tick-borne virus RNAs, which altogether adopt a secondary structure that is very different from that of mosquito-borne virus RNAs. The strong conservation of the pseudoknot in mosquito-borne flavivirus RNAs implies a stronger relationship between these viruses than concluded from previous secondary structure analyses. The role of the (tandem) pseudoknots in flavivirus replication is discussed.

Modeling RNA folding paths with pseudoknots: application to hepatitis delta virus ribozyme

A quantitative understanding of nucleic acid hybridization is essential to many aspects of biotechnology, such as DNA microarrays, as well as to the structure and folding kinetics of RNA. However, predictions of nucleic acid secondary structures have long been impeded by the presence of helices interior to loops, so-called pseudoknots, which impose complex three-dimensional conformational constraints. In this paper we compute the pseudoknot free energies analytically in terms of known standard parameters, and we show how the results can be included in a kinetic Monte Carlo code to follow the succession of secondary structures during quenched or sequential folding. For the hepatitis delta virus ribozyme, we predict several nonnative stems on the folding path, characterize a kinetically trapped state, interpret several experimentally characterized mutations in terms of the folding path, and suggest how hybridization with other parts of the genome inactivates the newly formed ribozyme.

Calculating nucleic acid secondary structure

New results for calculating nucleic acid secondary structure by free energy minimization and phylogenetic comparisons have recently been reported. A complete set of DNA energy parameters is now available and the RNA parameters have been improved. Although databases of RNA secondary structures are still derived and expanded using computer-assisted, ad hoc comparative analysis, a number of new computer algorithms combine covariation analysis with energy methods.

Structure, stability and function of RNA pseudoknots involved in stimulating ribosomal frameshifting

Programmed -1 ribosomal frameshifting has become the subject of increasing interest over the last several years, due in part to the ubiquitous nature of this translational recoding mechanism in pathogenic animal and plant viruses. All cis-acting frameshift signals encoded in mRNAs are minimally composed of two functional elements: a heptanucleotide "slippery sequence" conforming to the general form X XXY YYZ, followed by an RNA structural element, usually an H-type RNA pseudoknot, positioned an optimal number of nucleotides (5 to 9) downstream. The slippery sequence itself promotes a low level ( approximately 1 %) of frameshifting; however, downstream pseudoknots stimulate this process significantly, in some cases up to 30 to 50 %. Although the precise molecular mechanism of stimulation of frameshifting remains poorly understood, significant advances have been made in our knowledge of the three-dimensional structures, thermodynamics of folding, and functional determinants of stimulatory RNA pseudoknots derived from the study of several well-characterized frameshift signals. These studies are summarized here and provide new insights into the structural requirements and mechanism of programmed -1 ribosomal frameshifting.

Contribution of the intercalated adenosine at the helical junction to the stability of the gag-pro frameshifting pseudoknot from mouse mammary tumor virus

The mouse mammary tumor virus (MMTV) gag-pro frameshifting pseudoknot is an H-type RNA pseudoknot that contains an unpaired adenosine (A14) at the junction of the two helical stems required for efficient frameshifting activity. The thermodynamics of folding of the MMTV vpk pseudoknot have been compared with a structurally homologous mutant RNA containing a G x U to G-C substitution at the helical junction (U13C RNA), and an A14 deletion mutation in that context (U13CdeltaA14 RNA). Dual wavelength optical melting and differential scanning calorimetry reveal that the unpaired adenosine contributes 0.7 (+/-0.2) kcal mol(-1) at low salt and 1.4 (+/-0.2) kcal mol(-1) to the stability (deltaG(0)37) at 1 M NaCl. This stability increment derives from a favorable enthalpy contribution to the stability deltadeltaH = 6.6 (+/-2.1) kcal mol(-1) with deltadeltaG(0)37 comparable to that predicted for the stacking of a dangling 3' unpaired adenosine on a G-C or G x U base pair. Group 1A monovalent ions, NH4+, Mg2+, and Co(NH3)6(3+) ions stabilize the A14 and deltaA14 pseudoknots to largely identical extents, revealing that the observed differences in stability in these molecules do not derive from a differential or specific accumulation of ions in the A14 versus deltaA14 pseudoknots. Knowledge of this free energy contribution may facilitate the prediction of RNA pseudoknot formation from primary nucleotide sequence (Gultyaev et al., 1999, RNA 5:609-617).

Energetics of a strongly pH dependent RNA tertiary structure in a frameshifting pseudoknot

Retroviruses employ -1 translational frameshifting to regulate the relative concentrations of structural and non-structural proteins critical to the viral life cycle. The 1.6 A crystal structure of the -1 frameshifting pseudoknot from beet western yellows virus reveals, in addition to Watson-Crick base-pairing, many loop-stem RNA tertiary structural interactions and a bound Na(+). Investigation of the thermodynamics of unfolding of the beet western yellows virus pseudoknot reveals strongly pH-dependent loop-stem tertiary structural interactions which stabilize the molecule, contributing a net of DeltaH approximately -30 kcal mol(-1) and DeltaG degrees (37) of -3.3 kcal mol(-1) to a total DeltaH and DeltaG degrees (37) of -121 and -16 kcal mol(-1), respectively, at pH 6.0, 0.5 M K(+) by DSC. Characterization of mutant RNAs supports the presence of a C8(+).G12-C26 loop 1-stem 2 base-triple (pK(a)=6.8), protonation of which contributes nearly -3.5 kcal mol(-1) in net stability in the presence of a wild-type loop 2. Substitution of the nucleotides in loop 2 with uridine bases, which would eliminate the minor groove triplex, destroys pseudoknot formation. An examination of the dependence of the monovalent ion and type on melting profiles suggests that tertiary structure unfolding occurs in a manner quantitatively consistent with previous studies on the stabilizing effects of K(+), NH(4)(+) and Na(+) on other simple duplex and pseudoknotted RNAs.

PseudoBase: a database with RNA pseudoknots

PseudoBase is a database containing structural, functional and sequence data related to RNA pseudo-knots. It can be reached at http://wwwbio. Leiden Univ.nl/ approximately Batenburg/PKB.html. This page will direct the user to a retrieval page from where a particular pseudoknot can be chosen, or to a submission page which enables the user to add pseudoknot information to the database or to an informative page that elaborates on the various aspects of the database. For each pseudoknot, 12 items are stored, e.g. the nucleotides of the region that contains the pseudoknot, the stem positions of the pseudoknot, the EMBL accession number of the sequence that contains this pseudoknot and the support that can be given regarding the reliability of the pseudoknot. Access is via a small number of steps, using 16 different categories. The development process was done by applying the evolutionary methodology for software development rather than by applying the methodology of the classical waterfall model or the more modern spiral model.

Expression of the human immunodeficiency virus frameshift signal in a bacterial cell-free system: influence of an interaction between the ribosome and a stem-loop structure downstream from the slippery site

A-1 frameshift event is required for expression of the pol gene when ribosomes translate the mRNA of human immunodeficiency virus type-1 (HIV-1). In this study, we inserted the frameshift region of HIV-1 (a slippery heptanucleotide motif followed by a stem-loop) in a reporter gene coding for firefly luciferase. The ability of the corresponding mRNA, generated by in vitro transcription, to be translated in an Escherichia coli cell-free extract is the first demonstration that the HIV-1 frameshift can be reproduced in a bacterial cell-free extract, providing a powerful approach for analysis of the frameshift mechanism. The responses of the frameshift signal to chloramphenicol, an inhibitor of peptide bond formation, and spectinomycin, an inhibitor of translocation, suggest that the frameshift complies with the same rules found in eukaryotic translation systems. Furthermore, when translation was performed in the presence of streptomycin and neamine, two error-inducing antibiotics, or with hyperaccurate ribosomes mutated in S12, the frameshift efficiency was increased or decreased, respectively, but only in the presence of the stem-loop, suggesting that the stem-loop can influence the frameshift through a functional interaction with the ribosomes.