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.     

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.     

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.     

RNA pseudoknot prediction in energy-based models.

RNA molecules are sequences of nucleotides that serve as more than mere intermediaries between DNA and proteins, e.g., as catalytic molecules. Computational prediction of RNA secondary structure is among the few structure prediction problems that can be solved satisfactorily in polynomial time. Most work has been done to predict structures that do not contain pseudoknots. Allowing pseudoknots introduces modeling and computational problems. In this paper we consider the problem of predicting RNA secondary structures with pseudoknots based on free energy minimization. We first give a brief comparison of energy-based methods for predicting RNA secondary structures with pseudoknots. We then prove that the general problem of predicting RNA secondary structures containing pseudoknots is NP complete for a large class of reasonable models of pseudoknots.     

A heuristic approach for detecting RNA H-type pseudoknots

MOTIVATION: RNA H-type pseudoknots are ubiquitous pseudoknots that are found in almost all classes of RNA and thought to play very important roles in a variety of biological processes. Detection of these RNA H-type pseudoknots can improve our understanding of RNA structures and their associated functions. However, the currently existing programs for detecting such RNA H-type pseudoknots are still time consuming and sometimes even ineffective. Therefore, efficient and effective tools for detecting the RNA H-type pseudoknots are needed. RESULTS: In this paper, we have adopted a heuristic approach to develop a novel tool, called HPknotter, for efficiently and accurately detecting H-type pseudoknots in an RNA sequence. In addition, we have demonstrated the applicability and effectiveness of HPknotter by testing on some sequences with known H-type pseudoknots. Our approach can be easily extended and applied to other classes of more general pseudoknots. AVAILABILITY: The web server of our HPknotter is available for online analysis at http://bioalgorithm.life.nctu.edu.tw/HPKNOTTER/ CONTACT: cllu@mail.nctu.edu.tw, chiu@cc.nctu.edu.tw     

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

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

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.     

RNA aptamers that bind the nucleocapsid protein contain pseudoknots

We screened two independent RNA libraries consisting of molecules of 50 nucleotides of random sequence, one of which had additional viral psi-sequences to isolate RNA aptamers that bound to the mature form of the nucleocapsid (NC) protein of Human Immunodeficiency Virus Type-1 (HIV-1). Surface Plasmon Resonance measurements and gel shift assays showed that the RNA aptamers bound with high affinity and specificity. We employed RNase footprinting to characterize the RNA structures and to map their protein binding sites. Most of the selected RNA aptamers contained a plausible pseudoknot in addition to the characteristic stem-loop structure. Moreover, the pseudoknots were part of the NC binding sites. We propose that higher order structures such as pseudoknots may constitute binding motifs for nucleic acid binding proteins, especially for NC protein, which is a nucleic acid chaperone.     

G-ribo motif favors the formation of pseudoknots in ribosomal RNA

Analysis of the pseudoknots existing in the ribosomal RNA showed that four of them are formed with the help of G-ribo, a recently identified RNA recurrent motif. The analysis of these pseudoknots revealed two major aspects in the G-ribo motif structure, which together provide the structural context favoring the formation of two different types of pseudoknots. The first aspect pertains to a particular side-by-side juxtaposition of two double helices that facilitates switches of the polynucleotide chain between different strands. The second aspect deals with the presence of an adenosine at a specific place where it can stabilize a particular arrangement of two quasicoaxial helices required for the pseudoknot formation. Additional analysis shows that the latter aspect is also present in other pseudoknots not related to the G-ribo motif or the ribosome, and thus represents a general structural element favoring the formation of pseudoknots.     

基于启发式算法预测含假结RNA二级结构的研究进展

RNA二级结构的预测算法研究已有近40年的发展历程,研究假结也将近30年的历史。在此期间,RNA二级结构的预测算法取得了很大进步,但假结预测的正确率依然偏低。其中启发式算法能较好地处理复杂假结,使其成为率先解决假结预测难题可能性最大的算法。迄今为止,未见系统地专门总结预测假结的各种启发式算法及其优点与缺点的报道。本文详细介绍了近年来国际上流行的贪婪算法、遗传算法、ILM算法、HotKnots算法以及FlexStem算法等五种算法,并总结分析了每种算法的优点与不足,最后提出在未来一段时期内,利用启发式算法提高假结预测准确度应从建立更完善的假结模型、加入更多影响因素、借鉴不同算法的优势等方面入手。为含假结RNA二级结构预测的研究提供参考。     

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.     

Predicting RNA secondary structures with arbitrary pseudoknots by maximizing the number of stacking pairs.

The paper investigates the computational problem of predicting RNA secondary structures. The general belief is that allowing pseudoknots makes the problem hard. Existing polynomial-time algorithms are heuristic algorithms with no performance guarantee and can handle only limited types of pseudoknots. In this paper, we initiate the study of predicting RNA secondary structures with a maximum number of stacking pairs while allowing arbitrary pseudoknots. We obtain two approximation algorithms with worst-case approximation ratios of 1/2 and 1/3 for planar and general secondary structures, respectively. For an RNA sequence of n bases, the approximation algorithm for planar secondary structures runs in O(n(3)) time while that for the general case runs in linear time. Furthermore, we prove that allowing pseudoknots makes it NP-hard to maximize the number of stacking pairs in a planar secondary structure. This result is in contrast with the recent NP-hard results on psuedoknots which are based on optimizing some general and complicated energy functions.     

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.     

A phylogenetically conserved sequence within viral 3'' untranslated RNA pseudoknots regulates translation.

Both the 68-base 5' leader (omega) and the 205-base 3' untranslated region (UTR) of tobacco mosaic virus (TMV) promote efficient translation. A 35-base region within omega is necessary and sufficient for the regulation. Within the 3' UTR, a 52-base region, composed of two RNA pseudoknots, is required for regulation. These pseudoknots are phylogenetically conserved among seven viruses from two different viral groups and one satellite virus. The pseudoknots contained significant conservation at the secondary and tertiary levels and at several positions at the primary sequence level. Mutational analysis of the sequences determined that the primary sequence in several conserved positions, particularly within the third pseudoknot, was essential for function. The higher-order structure of the pseudoknots was also required. Both the leader and the pseudoknot region were specifically recognized by, and competed for, the same proteins in extracts made from carrot cell suspension cells and wheat germ. Binding of the proteins is much stronger to omega than the pseudoknot region. Synergism was observed between the TMV 3' UTR and the cap and to a lesser extent between omega and the 3' UTR. The functional synergism and the protein binding data suggest that the cap, TMV 5' leader, and 3' UTR interact to establish an efficient level of translation.     

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.     

Tandem mengovirus 5' pseudoknots are linked to viral RNA synthesis, not poly(C)-mediated virulence.

The RNA genomes from the cardioviruses, hepatoviruses, and aphthoviruses encode two to five tandem pseudoknots within their 5' untranslated regions. These pseudoknots lie adjacent to a pyrimidine-rich sequence, which in cardio- and aphthoviruses takes the form of a homopolymeric poly(C) tract. Seven deletion mutations within mengovirus pseudoknots PK(B) and PK(C) were created and characterized. tested in tissue culture, mengovirus genomes with alterations in PK(C) were viable but had small plaque phenotypes. Larger plaque revertants were isolated and partially characterized, and each proved to be a second-site pseudorevertant with (unmapped) changes elsewhere in the genome. The infectious PK(C) mutant viruses were highly lethal to mice, and deletions in this motif did not affect mengovirus virulence in the same manner as deletions in the adjacent poly(C) tract. In contrast, deletions in PK(B), or deletions which spanned PK(B) + PK(C), produced nonviable genomes. Cell-free translations directed by any of the altered PK sequences gave normal polyprotein amounts relative to wild-type mengovirus. But viral RNA accumulation during HeLa cell infection was dramatically impaired, even with the least disruptive of the PK(C) changes, suggesting the pseudoknots play an essential though undefined role in RNA synthesis and moreover that an intact PK(B) structure is critical to this function.     

Targeting pseudoknots in H5N1 hemagglutinin using designed aptamers

Influenza A virus subtype H5N1 is highly contagious among birds, causing high mortality among domestic poultry. The viral genome is contained on eight single RNA strands of which HA encode the antigenic glycoprotein called hemagglutinin. Hemagglutinin found on the surface of the influenza viruses and is responsible for binding the virus to the cell that is being infected. Among the most prevalent RNA structures the pseudoknot motif represents an important piece of RNA architecture, as it provides a means for a single RNA strand to fold upon itself to produce a globular structure capable of performing important biological functions. In this analysis we have identified the pseudoknot motifs in the hemagglutinin gene of HPAI A (H5N1) Asian strains. Specific aptamers have been designed against these pseudoknots. These in-silico aptamers can be used to hinder the ability of pseudoknots to facilitate ribosomal frameshifting. This may ultimately lead to reduce the coding efficiency of the HA that encodes hemagglutinin and might be used as molecular medicine for H5N1.     

Predicting RNA secondary structures with pseudoknots by MCMC sampling

The most probable secondary structure of an RNA molecule, given the nucleotide sequence, can be computed efficiently if a stochastic context-free grammar (SCFG) is used as the prior distribution of the secondary structure. The structures of some RNA molecules contain so-called pseudoknots. Allowing all possible configurations of pseudoknots is not compatible with context-free grammar models and makes the search for an optimal secondary structure NP-complete. We suggest a probabilistic model for RNA secondary structures with pseudoknots and present a Markov-chain Monte-Carlo Method for sampling RNA structures according to their posterior distribution for a given sequence. We favor Bayesian sampling over optimization methods in this context, because it makes the uncertainty of RNA structure predictions assessable. We demonstrate the benefit of our method in examples with tmRNA and also with simulated data. McQFold, an implementation of our method, is freely available from http://www.cs.uni-frankfurt.de/~metzler/McQFold.     

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.