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.     

Programmed ribosomal frameshifting in SIV is induced by a highly structured RNA stem-loop

Simian immunodeficiency virus (SIV), like its human homologues (HIV-1, HIV-2), requires a -1 translational frameshift event to properly synthesize all of the proteins required for viral replication. The frameshift mechanism is dependent upon a seven-nucleotide slippery sequence and a downstream RNA structure. In SIV, the downstream RNA structure has been proposed to be either a stem-loop or a pseudoknot. Here, we report the functional, structural and thermodynamic characterization of the SIV frameshift site RNA. Translational frameshift assays indicate that a stem-loop structure is sufficient to promote efficient frameshifting in vitro. NMR and thermodynamic studies of SIV RNA constructs of varying length further support the absence of any pseudoknot interaction and indicate the presence of a stable stem-loop structure. We determined the structure of the SIV frameshift-inducing RNA by NMR. The structure reveals a highly ordered 12 nucleotide loop containing a sheared G-A pair, cross-strand adenine stacking, two G-C base-pairs, and a novel CCC triloop turn. The loop structure and its high thermostability preclude pseudoknot formation. Sequence conservation and modeling studies suggest that HIV-2 RNA forms the same structure. We conclude that, like the main sub-groups of HIV-1, SIV and HIV-2 utilize stable stem-loop structures to function as a thermodynamic barrier to translation, thereby inducing ribosomal pausing and frameshifting.     

Structural and functional studies of retroviral RNA pseudoknots involved in ribosomal frameshifting: nucleotides at the junction of the two stems are important for efficient ribosomal frameshifting.

Ribosomal frameshifting, a translational mechanism used during retroviral replication, involves a directed change in reading frame at a specific site at a defined frequency. Such programmed frameshifting at the mouse mammary tumor virus (MMTV) gag-pro shift site requires two mRNA signals: a heptanucleotide shifty sequence and a pseudoknot structure positioned downstream. Using in vitro translation assays and enzymatic and chemical probes for RNA structure, we have defined features of the pseudoknot that promote efficient frameshifting. Heterologous RNA structures, e.g. a hairpin, a tRNA or a synthetic pseudoknot, substituted downstream of the shifty site fail to promote frameshifting, suggesting that specific features of the MMTV pseudoknot are important for function. Site-directed mutations of the MMTV pseudoknot indicate that the pseudoknot junction, including an unpaired adenine nucleotide between the two stems, provides a specific structural determinant for efficient frameshifting. Pseudoknots derived from other retroviruses (i.e. the feline immunodeficiency virus and the simian retrovirus type 1) also promote frameshifting at the MMTV gag-pro shift site, dependent on the same structure at the junction of the two stems.     

Molecular dissection of the pseudoknot governing the translational regulation of Escherichia coli ribosomal protein S15.

The ribosomal protein S15 controls its own translation by binding to a mRNA region overlapping the ribosome binding site. That region of the mRNA can fold in two mutually exclusive conformations that are in dynamic equilibrium: a structure with two hairpins and a pseudoknot. A mutational analysis provided evidence for the existence and requirement of the pseudoknot for translational control in vivo and S15 recognition in vitro. In this study, we used chemical probing to analyze the structural consequences of mutations and their effect on the stem-loop/pseudoknot equilibrium. Interactions between S15 and the pseudoknot structure were further investigated by footprinting experiments. These data, combined with computer modelling and the previously published data on S15 binding and in vivo control, provide important clues on pseudoknot formation and S15 recognition. An unexpected result is that the relevant control element, here the pseudoknot form, can exist in a variety of topologically equivalent structures recognizable and shapable by S15. S15 sits on the deep groove of the co-axial stack and makes contacts with both stems, shielding the bridging adenine. The only specific sequence determinants are found in the helix common to the pseudoknot and the hairpin structures.     

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.     

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.     

PSEUDOVIEWER2: Visualization of RNA pseudoknots of any type

Visualizing RNA pseudoknot structures is computationally more difficult than depicting RNA secondary structures, because a drawing of a pseudoknot structure is a graph (and possibly a nonplanar graph) with inner cycles within the pseudoknot, and possibly outer cycles formed between the pseudoknot and other structural elements. We previously developed PSEUDOVIEWER for visualizing H-type pseudoknots. PSEUDOVIEWER2 improves on the first version in many ways: (i) PSEUDOVIEWER2 is more general because it can visualize a pseudoknot of any type, including H-type pseudoknots, as a planar graph; (ii) PSEUDOVIEWER2 computes a drawing of RNA structures much more efficiently and is an order of magnitude faster in actual running time; and (iii) PSEUDOVIEWER2 is a web-based application program. Experimental results demonstrate that PSEUDOVIEWER2 generates an aesthetically pleasing drawing of pseudoknots of any type and that the new representation offered by PSEUDOVIEWER2 ensures uniform and clear drawings, with no edge crossing, for all types of pseudoknots. The PSEUDOVIEWER2 algorithm is the first developed for the automatic drawing of RNA secondary structures, including pseudoknots of any type. PSEUDOVIEWER2 is accessible at http://wilab.inha.ac.kr/pseudoviewer2/.     

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.     

Structural studies of the RNA pseudoknot required for readthrough of the gag-termination codon of murine leukemia virus.

Retroviruses, such as murine leukemia virus (MuLV), whose gag and pol genes are in the same reading frame but separated by a UAG stop codon, require that 5-10 % of ribosomes decode the UAG as an amino acid and continue translation to synthesize the Gag-Pol fusion polyprotein. A specific pseudoknot located eight nucleotides 3' of the UAG is required for this redefinition of the UAG stop codon. The structural probing and mutagenic analyses presented here provide evidence that loop I of the pseudoknot is one nucleotide, stem II has seven base-pairs, and the nucleotides 3' of stem II are important for function. Stem II is more resistant to single-strand-specific probes than stem I. Sequences upstream of the UAG codon allow formation of two competing structures, a stem-loop and the pseudoknot.     

Mutational analysis of the pseudoknot in the tRNA-like structure of turnip yellow mosaic virus RNA. Aminoacylation efficiency and RNA pseudoknot stability.

Site-directed mutations were introduced in the connecting loops and one of the two stem regions of the RNA pseudoknot in the tRNA-like structure of turnip yellow mosaic virus RNA. The kinetic parameters of valylation for each mutated RNA were determined in a cell-free extract from wheat germ. Structure mapping was performed on most mutants with enzymic probes, like RNase T1, nuclease S1 and cobra venom ribonuclease. An insertion of four A residues in the four-membered connecting loop L1 that crosses the deep groove of the pseudoknot reduces aminoacylation efficiency. Deletions up to three nucleotides do not affect aminoacylation or RNA pseudoknot formation. Deletion of the entire loop abolishes aminoacylation. Although elimination of the pseudoknot is presumed, this could not be demonstrated. Unlike the mutations in loop L1, all mutations in the three-membered connecting loop L2 that crosses the shallow groove of the RNA pseudoknot decrease the aminoacylation efficiency considerably. Nonetheless, the RNA pseudoknot is still present in most mutated RNAs. These results indicate that a number of mutations can be introduced in both loops without abolishing aminoacylation. Results obtained with the introduction of mismatches and A.U base-pairs in stem S1 of the pseudoknot, containing three G.C base-pairs in wild-type RNA, indicate that the pseudoknot is only marginally stable. Our estimation of the gain of free energy due to the pseudoknot formation is at most 2.0 kcal/mol. The pseudoknot structure can, however, be stabilized upon binding the valyl-tRNA synthetase.     

Solution structure of a luteoviral P1-P2 frameshifting mRNA pseudoknot

A hairpin-type messenger RNA pseudoknot from pea enation mosaic virus RNA1 (PEMV-1) regulates the efficiency of programmed -1 ribosomal frameshifting. The solution structure and 15N relaxation rates reveal that the PEMV-1 pseudoknot is a compact-folded structure composed almost entirely of RNA triple helix. A three nucleotide reverse turn in loop 1 positions a protonated cytidine, C(10), in the correct orientation to form an A((n-1)).C(+).G-C(n) major groove base quadruple, like that found in the beet western yellows virus pseudoknot and the hepatitis delta virus ribozyme, despite distinct structural contexts. A novel loop 2-loop 1 A.U Hoogsteen base-pair stacks on the C(10)(+).G(28) base-pair of the A(12).C(10)(+).G(28)-C(13) quadruple and forms a wedge between the pseudoknot stems stabilizing a bent and over-rotated global conformation. Substitution of key nucleotides that stabilize the unique conformation of the PEMV-1 pseudoknot greatly reduces ribosomal frameshifting efficacy.     

An examination of coaxial stacking of helical stems in a pseudoknot motif: the gene 32 messenger RNA pseudoknot of bacteriophage T2

The RNA pseudoknot located at the 5' end of the gene 32 messenger RNA of bacteriophage T2 contains two A-form helical stems connected by two loops, in an H-type pseudoknot topology. A combination of multidimensional NMR methods and isotope labeling were used to investigate the pseudoknot structure, resulting in a more detailed structural model than provided by earlier homonuclear NMR studies. Of particular significance, the interface between the stacked helical stems within the pseudoknot motif is described in detail. The two stems are stacked in a coaxial manner, with an approximately 18 degrees rotation of stem1 relative to stem2 about an axis that is parallel to the helical axis. This rotation serves to relieve what would otherwise be a relatively close phosphate-phosphate contact at the junction of the two stems, while preserving the stabilizing effects of base stacking. The ability of the NMR data to determine pseudoknot bending was critically assessed. The data were found to be a modestly precise indicator of pseudoknot bending, with the angle between the helical axes of stem1 and stem2 being in the range of 15+/-15 degrees. Pseudoknot models with bend angles within this range are equally consistent with the data, since they differ by only small amounts in the relatively short-range interproton distances from which the structure was derived. The gene 32 messenger RNA pseudoknot was compared with other RNA structures with coaxial or near-coaxial stacked helical stems.     

Three-dimensional structure of a flavivirus dumbbell RNA reveals molecular details of an RNA regulator of replication

Mosquito-borne flaviviruses (MBFVs) including dengue, West Nile, yellow fever, and Zika viruses have an RNA genome encoding one open reading frame flanked by 5′ and 3′ untranslated regions (UTRs). The 3′ UTRs of MBFVs contain regions of high sequence conservation in structured RNA elements known as dumbbells (DBs). DBs regulate translation and replication of the viral RNA genome, functions proposed to depend on the formation of an RNA pseudoknot. To understand how DB structure provides this function, we solved the x-ray crystal structure of the Donggang virus DB to 2.1Å resolution and used structural modeling to reveal the details of its three-dimensional fold. The structure confirmed the predicted pseudoknot and molecular modeling revealed how conserved sequences form a four-way junction that appears to stabilize the pseudoknot. Single-molecule FRET suggests that the DB pseudoknot is a stable element that can regulate the switch between translation and replication during the viral lifecycle by modulating long-range RNA conformational changes.     

A three-stemmed mRNA pseudoknot in the SARS coronavirus frameshift signal

A wide range of RNA viruses use programmed −1 ribosomal frameshifting for the production of viral fusion proteins. Inspection of the overlap regions between ORF1a and ORF1b of the SARS-CoV genome revealed that, similar to all coronaviruses, a programmed −1 ribosomal frameshift could be used by the virus to produce a fusion protein. Computational analyses of the frameshift signal predicted the presence of an mRNA pseudoknot containing three double-stranded RNA stem structures rather than two. Phylogenetic analyses showed the conservation of potential three-stemmed pseudoknots in the frameshift signals of all other coronaviruses in the GenBank database. Though the presence of the three-stemmed structure is supported by nuclease mapping and two-dimensional nuclear magnetic resonance studies, our findings suggest that interactions between the stem structures may result in local distortions in the A-form RNA. These distortions are particularly evident in the vicinity of predicted A-bulges in stems 2 and 3. In vitro and in vivo frameshifting assays showed that the SARS-CoV frameshift signal is functionally similar to other viral frameshift signals: it promotes efficient frameshifting in all of the standard assay systems, and it is sensitive to a drug and a genetic mutation that are known to affect frameshifting efficiency of a yeast virus. Mutagenesis studies reveal that both the specific sequences and structures of stems 2 and 3 are important for efficient frameshifting. We have identified a new RNA structural motif that is capable of promoting efficient programmed ribosomal frameshifting. The high degree of conservation of three-stemmed mRNA pseudoknot structures among the coronaviruses suggests that this presents a novel target for antiviral therapeutics.     

Possible involvement of coaxially stacked double pseudoknots in the regulation of −1 programmed ribosomal frameshifting in RNA viruses

?1 programmed ribosomal frameshifting (PRF) in viruses is often stimulated by a pseudoknot downstream from the slippery sequence. At the PRF junction of HIV-1, transmissible gastroenteritis virus (TGEV), Barmah Forest virus (BFV), Fort Morgan virus (FMV), and Equine arteritis virus (EAV), we identified potential double pseudoknots in either a tandem mode or embedded mode. In viruses with tandem pseudoknots (5′PK & 3′PK), the slippery sequence is encompassed in the 5′PK. The ribosome needs to unwind the 5′PK to get to the slippery sequence. In HIV-1, the 3′PK and several alternative structures are mutually exclusive. Disruption of the tandem pseudoknots may enable one of the alternative structures to form as the effective frameshift stimulator. In TGEV/BFV/FMV, the 3′PK is a conventional frameshift stimulator. In all cases, the tandem pseudoknots may slow down the ribosome before it reaches the conventional PRF signals. In EAV, a compact pseudoknot is embedded within loop2 of the otherwise conventional frameshift-stimulating pseudoknot. All double pseudoknots have the potential to stack their stems coaxially. We built structural models of the HIV-1 and EAV double pseudoknots to show that both the tandem and embedded modes are feasible and reasonable. We hypothesize that the fundamental reason for the viruses to utilize coaxially stacked double pseudoknots is to increase the overall stability of the frameshift regulating structure, and avoid an ultra-stable single pseudoknot which may become a ribosomal roadblock. Our results significantly expand the repertoire of RNA structures and dynamics that may potentially involve in ?1 PRF regulation.     

Structure-altering mutations of the SARS-CoV-2 frameshifting RNA element

With the rapid rate of COVID-19 infections and deaths, treatments and cures besides hand washing, social distancing, masks, isolation, and quarantines are urgently needed. The treatments and vaccines rely on the basic biophysics of the complex viral apparatus. Although proteins are serving as main drug and vaccine targets, therapeutic approaches targeting the 30,000 nucleotide RNA viral genome form important complementary approaches. Indeed, the high conservation of the viral genome, its close evolutionary relationship to other viruses, and the rise of gene editing and RNA-based vaccines all argue for a focus on the RNA agent itself. One of the key steps in the viral replication cycle inside host cells is the ribosomal frameshifting required for translation of overlapping open reading frames. The RNA frameshifting element (FSE), one of three highly conserved regions of coronaviruses, is believed to include a pseudoknot considered essential for this ribosomal switching. In this work, we apply our graph-theory-based framework for representing RNA secondary structures, “RAG (or RNA-As-Graphs),” to alter key structural features of the FSE of the SARS-CoV-2 virus. Specifically, using RAG machinery of genetic algorithms for inverse folding adapted for RNA structures with pseudoknots, we computationally predict minimal mutations that destroy a structurally important stem and/or the pseudoknot of the FSE, potentially dismantling the virus against translation of the polyproteins. Our microsecond molecular dynamics simulations of mutant structures indicate relatively stable secondary structures. These findings not only advance our computational design of RNAs containing pseudoknots, they pinpoint key residues of the SARS-CoV-2 virus as targets for antiviral drugs and gene editing approaches.