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.     

Identifying complete RNA structural ensembles including pseudoknots

The close relationship between RNA structure and function underlines the significance of accurately predicting RNA structures from sequence information. Structural topologies such as pseudoknots are of particular interest due to their ubiquity and direct involvement in RNA function, but identifying pseudoknots is a computationally challenging problem and existing heuristic approaches usually perform poorly for RNA sequences of even a few hundred bases. We survey the performance of pseudoknot prediction methods on a data set of full-length RNA sequences representing varied sequence lengths, and biological RNA classes such as RNase P RNA, Group I Intron, tmRNA and tRNA. Pseudoknot prediction methods are compared with minimum free energy and suboptimal secondary structure prediction methods in terms of correct base-pairs, stems and pseudoknots and we find that the ensemble of suboptimal structure predictions succeeds in identifying correct structural elements in RNA that are usually missed in MFE and pseudoknot predictions. We propose a strategy to identify a comprehensive set of non-redundant stems in the suboptimal structure space of a RNA molecule by applying heuristics that reduce the structural redundancy of the predicted suboptimal structures by merging slightly varying stems that are predicted to form in local sequence regions. This reduced-redundancy set of structural elements consistently outperforms more specialized approaches.in data sets. Thus, the suboptimal folding space can be used to represent the structural diversity of an RNA molecule more comprehensively than optimal structure prediction approaches alone.     

Thermodynamic heuristics with case-based reasoning: combined insights for RNA pseudoknot secondary structure

The secondary structure of RNA pseudoknots has been extensively inferred and scrutinized by computational approaches. Experimental methods for determining RNA structure are time consuming and tedious; therefore, predictive computational approaches are required. Predicting the most accurate and energy-stable pseudoknot RNA secondary structure has been proven to be an NP-hard problem. In this paper, a new RNA folding approach, termed MSeeker, is presented; it includes KnotSeeker (a heuristic method) and Mfold (a thermodynamic algorithm). The global optimization of this thermodynamic heuristic approach was further enhanced by using a case-based reasoning technique as a local optimization method. MSeeker is a proposed algorithm for predicting RNA pseudoknot structure from individual sequences, especially long ones. This research demonstrates that MSeeker improves the sensitivity and specificity of existing RNA pseudoknot structure predictions. The performance and structural results from this proposed method were evaluated against seven other state-of-the-art pseudoknot prediction methods. The MSeeker method had better sensitivity than the DotKnot, FlexStem, HotKnots, pknotsRG, ILM, NUPACK and pknotsRE methods, with 79% of the predicted pseudoknot base-pairs being correct.     

Characterization of the mechanical unfolding of RNA pseudoknots

The pseudoknot is an important RNA structural element that provides an excellent model system for studying the contributions of tertiary interactions to RNA stability and to folding kinetics. RNA pseudoknots are also of interest because of their key role in the control of ribosomal frameshifting by viral RNAs. Their mechanical properties are directly relevant to their unfolding by ribosomes during translation. We have used optical tweezers to study the kinetics and thermodynamics of mechanical unfolding and refolding of single RNA molecules. Here we describe the unfolding of the frameshifting pseudoknot from infectious bronchitis virus (IBV), three constituent hairpins, and three mutants of the IBV pseudoknot. All four pseudoknots cause −1 programmed ribosomal frameshifting. We have measured the free energies and rates of mechanical unfolding and refolding of the four frameshifting pseudoknots. Our results show that the IBV pseudoknot requires a higher force than its corresponding hairpins to unfold. Furthermore, its rate of unfolding changes little with increasing force, in contrast with the rate of hairpin unfolding. The presence of Mg²⁺ significantly increases the kinetic barriers to unfolding the IBV pseudoknot, but has only a minor effect on the hairpin unfolding. The greater mechanical stability of pseudoknots compared to hairpins, and their kinetic insensitivity to force supports the hypothesis that −1 frameshifting depends on the difficulty of unfolding the mRNA.     

Pair stochastic tree adjoining grammars for aligning and predicting pseudoknot RNA structures

MOTIVATION: Since the whole genome sequences of many species have been determined, computational prediction of RNA secondary structures and computational identification of those non-coding RNA regions by comparative genomics become important. Therefore, more advanced alignment methods are required. Recently, an approach of structural alignment for RNA sequences has been introduced to solve these problems. Pair hidden Markov models on tree structures (PHMMTSs) proposed by Sakakibara are efficient automata-theoretic models for structural alignment of RNA secondary structures, although PHMMTSs are incapable of handling pseudoknots. On the other hand, tree adjoining grammars (TAGs), a subclass of context-sensitive grammars, are suitable for modeling pseudoknots. Our goal is to extend PHMMTSs by incorporating TAGs to be able to handle pseudoknots. RESULTS: We propose pair stochastic TAGs (PSTAGs) for aligning and predicting RNA secondary structures including a simple type of pseudoknot which can represent most known pseudoknot structures. First, we extend PHMMTSs defined on alignment of 'trees' to PSTAGs defined on alignment of 'TAG trees' which represent derivation processes of TAGs and are functionally equivalent to derived trees of TAGs. Then, we develop an efficient dynamic programming algorithm of PSTAGs for obtaining an optimal structural alignment including pseudoknots. We implement the PSTAG algorithm and demonstrate the properties of the algorithm by using it to align and predict several small pseudoknot structures. We believe that our implemented program based on PSTAGs is the first grammar-based and practically executable software for comparative analyses of RNA pseudoknot structures, and, further, non-coding RNAs.     

An NMR and mutational study of the pseudoknot within the gene 32 mRNA of bacteriophage T2: insights into a family of structurally related RNA pseudoknots.

NMR methods were used to investigate a series of mutants of the pseudoknot within the gene 32 messenger RNA of bacteriophage T2, for the purpose of investigating the range of sequences, stem and loop lengths that can form a similar pseudoknot structure. This information is of particular relevance since the T2 pseudoknot has been considered a representative of a large family of RNA pseudoknots related by a common structural motif, previously referred to as 'common pseudoknot motif 1' or CPK1. In the work presented here, a mutated sequence with the potential to form a pseudoknot with a 6 bp stem2 was shown to adopt a pseudoknot structure similar to that of the wild-type sequence. This result is significant in that it demonstrates that pseudoknots with 6 bp in stem2 and a single nucleotide in loop1 are indeed feasible. Mutated sequences with the potential to form pseudoknots with either 5 or 8 bp in stem2 yielded NMR spectra that could not confirm the formation of a pseudoknot structure. Replacing the adenosine nucleotide in loop1 of the wild-type pseudoknot with any one of G, C or U did not significantly alter the pseudoknot structure. Taken together, the results of this study provide support for the existence of a family of similarly structured pseudoknots with two coaxially stacked stems, either 6 or 7 bp in stem2, and a single nucleotide in loop1. This family includes many of the pseudoknots predicted to occur downstream of the frameshift or readthrough sites in a significant number of viral RNAs.     

RNA pseudoknots. Stability and loop size requirements.

The effects of ionic conditions, loop size and loop sequence on the formation of pseudoknots by RNA oligonucleotides have been investigated using biochemical and biophysical methods. An oligonucleotide with the sequence 5' GCGAUUUCUGACCGCUUUUUUGUCAG 3' and oligonucleotides with variations in the sequences of the two loop regions, denoted by bold face type, were studied. Each sequence with the potential to form a pseudoknot can also form two stable hairpins. The pseudoknot structure is stabilized relative to the hairpins by addition of Mg2+. Even in the presence of Mg2+, the pseudoknots formed by the sequences investigated are only marginally more stable (1.5 to 2 kcal mol-1 in free energy at 37 degrees C) than either of the constituent hairpins. The pseudoknot structure is the stable conformation in the presence of Mg2+ when the first loop region is at least three nucleotides and the second is at least four nucleotides. Further deletion of nucleotides from the loop regions stabilizes possible hairpin structures relative to the pseudoknot and equilibria among secondary and tertiary structures result.     

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.     

Crystal structure of a luteoviral RNA pseudoknot and model for a minimal ribosomal frameshifting motif

To understand the role of structural elements of RNA pseudoknots in controlling the extent of -1-type ribosomal frameshifting, we determined the crystal structure of a high-efficiency frameshifting mutant of the pseudoknot from potato leaf roll virus (PLRV). Correlations of the structure with available in vitro frameshifting data for PLRV pseudoknot mutants implicate sequence and length of a stem-loop linker as modulators of frameshifting efficiency. Although the sequences and overall structures of the RNA pseudoknots from PLRV and beet western yellow virus (BWYV) are similar, nucleotide deletions in the linker and adjacent minor groove loop abolish frameshifting only with the latter. Conversely, mutant PLRV pseudoknots with up to four nucleotides deleted in this region exhibit nearly wild-type frameshifting efficiencies. The crystal structure helps rationalize the different tolerances for deletions in the PLRV and BWYV RNAs, and we have used it to build a three-dimensional model of the PRLV pseudoknot with a four-nucleotide deletion. The resulting structure defines a minimal RNA pseudoknot motif composed of 22 nucleotides capable of stimulating -1-type ribosomal frameshifts.     

A procedure for RNA pseudoknot prediction

The RNA pseudoknot has been proposed as a significant structuralmotif in a wide range of biological processes of RNAs. A pseudoknotinvolves intramolecular pairing of bases in a hairpin loop withbases outside the stem of the loop to form a second stem andloop region. In this study, we propose a method for searchingand predicting pseudoknots that are likely to have functionalmeaning. In our procedure, the orthodox hairpin structure involvedin the pseudoknot is required to be both statistically significantand relatively stable to the others in the sequence. The basesoutside the stem of the hairpin loop in the predicted pseudoknotare not entangled with any formation of a highly stable secondarystructure in the sequence. Also, the predicted pseudoknot issignificantly more stable than those that can be formed froma large set of scrambled sequences under the assumption thatthe energy contribution from a pseudoknot is proportional tothe size of second loop region and planar energy contributionfrom second stem region. A number of functional pseudoknotsthat have been reported before can be identified and predictedfrom their sequences by our method.     

Heuristic RNA pseudoknot prediction including intramolecular kissing hairpins

Pseudoknots are an essential feature of RNA tertiary structures. Simple H-type pseudoknots have been studied extensively in terms of biological functions, computational prediction, and energy models. Intramolecular kissing hairpins are a more complex and biologically important type of pseudoknot in which two hairpin loops form base pairs. They are hard to predict using free energy minimization due to high computational requirements. Heuristic methods that allow arbitrary pseudoknots strongly depend on the quality of energy parameters, which are not yet available for complex pseudoknots. We present an extension of the heuristic pseudoknot prediction algorithm DotKnot, which covers H-type pseudoknots and intramolecular kissing hairpins. Our framework allows for easy integration of advanced H-type pseudoknot energy models. For a test set of RNA sequences containing kissing hairpins and other types of pseudoknot structures, DotKnot outperforms competing methods from the literature. DotKnot is available as a web server under http://dotknot.csse.uwa.edu.au.     

A Characteristic Bent Conformation of RNA Pseudoknots Promotes –1 Frameshifting during Translation of Retroviral RNA

The structures of four different RNA pseudoknots that provide one of the signals required for ribosomal frameshifting in mouse mammary tumor virus have been determined by NMR. The RNA pseudoknots have similar sequences and assume similar secondary structures, but show significantly different frameshifting efficiencies. The three-dimensional structures of one frameshifting and one non-frameshifting RNA pseudoknot had been determined previously by our group. Here we determine the structures of two new RNA pseudoknots, and relate the structures of all four pseudoknots to their frameshifting abilities. The two efficient frameshifting pseudoknots adopt characteristic bent conformations with stem 1 bending towards the major groove of stem 2. In contrast, the two poor frameshifting pseudoknots have structures very different from each other and from the efficient frameshifters. One has linear, coaxially stacked stems, the other has stems twisted and bent, but in the opposite direction to the efficient frameshifters. Changes in loop size that favor bending (shorter loops) increase frameshifting efficiency; longer loops that allow linear arrangement of the stems decrease frameshifting. Frameshifting pseudoknots in feline immunodeficiency virus and simian retrovirus have different loop sequences, but the sequences at their stem junctions imply the same bent conformation as in the mouse mammary tumor viral RNA. The requirement for a precise pseudoknot conformation for efficient frameshifting strongly implies that a specific interaction occurs between the viral RNA pseudoknot and the host protein-synthesizing machinery.     

Telomerase Activity Is Sensitive to Subtle Perturbations of the TLC1 Pseudoknot 3′ Stem and Tertiary Structure

Pseudoknot formation in the core region of the telomerase RNA has been demonstrated to be important for telomerase activity in vertebrates, ciliates, and yeast. Characterization of the Saccharomyces cerevisiae telomerase RNA (TLC1) pseudoknot identified tertiary structural interactions that are also important for telomerase activity, as previously observed for the Kluyveromyces lactis and human telomerase RNA pseudoknots. In addition, the contributions of backbone ribose 2′-OH groups in the pseudoknot to telomerase catalysis were investigated previously, using 2′-OH (ribose) to 2′-H (deoxyribose) or 2′-O-methyl substitutions in the stem 2 helix, and it was proposed that one or more 2′-OH groups from the stem 2 sequences at or near the triple helix participate in telomerase catalysis. Based on these studies and investigations of the structural and thermodynamic properties of the TLC1 RNA pseudoknot region, we have examined the structural and thermodynamic perturbations of the 2′-O-methyl and 2′-H substituted pseudoknots, using UV-monitored thermal denaturation, native gel electrophoresis, and circular dichroism spectroscopy. Our results demonstrate the presence of A-form helical geometry perturbations in the backbone sugar substituted pseudoknots, show a correlation between thermodynamic stability and telomerase activity, and are consistent with the identification of the U809 ribose 2′-OH as a potential contributor to telomerase activity.     

PseudoViewer: automatic visualization of RNA pseudoknots

MOTIVATION: Several algorithms have been developed for drawing RNA secondary structures, however none of these can be used to draw RNA pseudoknot structures. In the sense of graph theory, a drawing of RNA secondary structures is a tree, whereas a drawing of RNA pseudoknots is a graph with inner cycles within a pseudoknot as well as possible outer cycles formed between a pseudoknot and other structural elements. Thus, RNA pseudoknots are more difficult to visualize than RNA secondary structures. Since no automatic method for drawing RNA pseudoknots exists, visualizing RNA pseudoknots relies on significant amount of manual work and does not yield satisfactory results. The task of visualizing RNA pseudoknots by hand becomes more challenging as the size and complexity of the RNA pseudoknots increase. RESULTS: We have developed a new representation and an algorithm for drawing H-type pseudoknots with RNA secondary structures. Compared to existing representations of H-type pseudoknots, the new representation ensures uniform and clear drawings with no edge crossing for any H-type pseudoknots. To the best of our knowledge, this is the first algorithm for automatically drawing RNA pseudoknots with RNA secondary structures. The algorithm has been implemented in a Java program, which can be executed on any computing system. Experimental results demonstrate that the algorithm generates an aesthetically pleasing drawing of all H-type pseudoknots. The results have also shown that the drawing has high readability, enabling the user to quickly and easily recognize the whole RNA structure as well as the pseudoknots themselves.     

An iterated loop matching approach to the prediction of RNA secondary structures with pseudoknots

MOTIVATION: Pseudoknots have generally been excluded from the prediction of RNA secondary structures due to its difficulty in modeling. Although, several dynamic programming algorithms exist for the prediction of pseudoknots using thermodynamic approaches, they are neither reliable nor efficient. On the other hand, comparative methods are more reliable, but are often done in an ad hoc manner and require expert intervention. Maximum weighted matching, an algorithm for pseudoknot prediction with comparative analysis, suffers from low-prediction accuracy in many cases. RESULTS: Here we present an algorithm, iterated loop matching, for reliably and efficiently predicting RNA secondary structures including pseudoknots. The method can utilize either thermodynamic or comparative information or both, thus is able to predict pseudoknots for both aligned and individual sequences. We have tested the algorithm on a number of RNA families. Using 8-12 homologous sequences, the algorithm correctly identifies more than 90% of base-pairs for short sequences and 80% overall. It correctly predicts nearly all pseudoknots and produces very few spurious base-pairs for sequences without pseudoknots. Comparisons show that our algorithm is both more sensitive and more specific than the maximum weighted matching method. In addition, our algorithm has high-prediction accuracy on individual sequences, comparable with the PKNOTS algorithm, while using much less computational resources. AVAILABILITY: The program has been implemented in ANSI C and is freely available for academic use at http://www.cse.wustl.edu/~zhang/projects/rna/ilm/ Supplementary information: http://www.cse.wustl.edu/~zhang/projects/rna/ilm/     

Pseudoknots in prion protein mRNAs confirmed by comparative sequence analysis and pattern searching

The human prion gene contains five copies of a 24 nt repeat that is highly conserved among species. An analysis of folding free energies of the human prion mRNA, in particular in the repeat region, suggested biased codon selection and the presence of RNA patterns. In particular, pseudoknots, similar to the one predicted by Wills in the human prion mRNA, were identified in the repeat region of all available prion mRNAs available in GenBank, but not those of birds and the red slider turtle. An alignment of these mRNAs, which share low sequence homology, shows several co-variations that maintain the pseudoknot pattern. The presence of pseudoknots in yeast Sup35p and Rnq1 suggests acquisition in the prokaryotic era. Computer generated three-dimensional structures of the human prion pseudoknot highlight protein and RNA interaction domains, which suggest a possible effect in prion protein translation. The role of pseudoknots in prion diseases is discussed as individuals with extra copies of the 24 nt repeat develop the familial form of Creutzfeldt–Jakob disease.     

A pseudoknot-compatible universal site is located in the large ribosomal RNA in the peptidyltransferase center

The RNA secondary structure is not confined to a system of the hairpins and can contain pseudoknots as well as topologically equivalent slipped-loop structure (SLS) conformations. A specific primary structure that directs folding to the pseudoknot or SLS is called SL-palindrome (SLP). Using a computer program for searching the SLP in the genomic sequences, 419 primary structures of large ribosomal RNAs from different kingdoms (prokaryota, eukaryota, archaebacteria) as well as plastids and mitochondria were analyzed. A universal site was found in the peptidyltransferase center (PTC) capable of folding to a pseudoknot of 48 nucleotides in length. Phylogenetic conservation of its helices (concurrent replacements with no violation of base pairing, covariation) has been demonstrated. We suggest the reversible folding-unfolding of the pseudoknot for certain stages of the ribosome functioning.