Improved free energy parameters for RNA pseudoknotted secondary structure prediction

mRNA vaccine sequence and structure design and optimization: Advances and challenges

Messenger RNA (mRNA) vaccines have emerged as a powerful tool against communicable diseases and cancers, as demonstrated by their huge success during the coronavirus disease 2019 (COVID-19) pandemic. Despite the outstanding achievements, mRNA vaccines still face challenges such as stringent storage requirements, insufficient antigen expression, and unexpected immune responses. Since the intrinsic properties of mRNA molecules significantly impact vaccine performance, optimizing mRNA design is crucial in preclinical development. In this review, we outline four key principles for optimal mRNA sequence design: enhancing ribosome loading and translation efficiency through untranslated region (UTR) optimization, improving translation efficiency via codon optimization, increasing structural stability by refining global RNA sequence and extending in-cell lifetime and expression fidelity by adjusting local RNA structures. We also explore recent advancements in computational models for designing and optimizing mRNA vaccine sequences following these principles. By integrating current mRNA knowledge, addressing challenges, and examining advanced computational methods, this review aims to promote the application of computational approaches in mRNA vaccine development and inspire novel solutions to existing obstacles.

CParty: hierarchically constrained partition function of RNA pseudoknots

MOTIVATION

Biologically relevant RNA secondary structures are routinely predicted by efficient dynamic programming algorithms that minimize their free energy. Starting from such algorithms, one can devise partition function algorithms, which enable stochastic perspectives on RNA structure ensembles. As the most prominent example, McCaskill's partition function algorithm is derived from pseudoknot-free energy minimization. While this algorithm became hugely successful for the analysis of pseudoknot-free RNA structure ensembles, as of yet there exists only one pseudoknotted partition function implementation, which covers only simple pseudoknots and comes with a borderline-prohibitive complexity of O(n5) in the RNA length n.

RESULTS

Here, we develop a partition function algorithm corresponding to the hierarchical pseudoknot prediction of HFold, which performs exact optimization in a realistic pseudoknot energy model. In consequence, our algorithm CParty carries over HFold's advantages over classical pseudoknot prediction in characterizing the Boltzmann ensemble at equilibrium. Given an RNA sequence S and a pseudoknot-free structure G, CParty computes the partition function over all possibly pseudoknotted density-2 structures G∪G' of S that extend the fixed G by a disjoint pseudoknot-free structure G'. Thus, CParty follows the common hypothesis of hierarchical pseudoknot formation, where pseudoknots form as tertiary contacts only after a first pseudoknot-free "core" G and we call the computed partition function hierarchically constrained (by G). Like HFold, the dynamic programming algorithm CParty is very efficient, achieving the low complexity of the pseudoknot-free algorithm, i.e. cubic time and quadratic space. Finally, by computing pseudoknotted ensemble energies, we unveil kinetics features of a therapeutic target in SARS-CoV-2.

AVAILABILITY AND IMPLEMENTATION

CParty is available at https://github.com/HosnaJabbari/CParty.

Possible involvement of three-stemmed pseudoknots in regulating translational initiation in human mRNAs

RNA pseudoknots play a crucial role in various cellular functions. Established pseudoknots show significant variation in both size and structural complexity. Specifically, three-stemmed pseudoknots are characterized by an additional stem-loop embedded in their structure. Recent findings highlight these pseudoknots as bacterial riboswitches and potent stimulators for programmed ribosomal frameshifting in RNA viruses like SARS-CoV2. To investigate the possible presence of functional three-stemmed pseudoknots in human mRNAs, we employed in-house developed computational methods to detect such structures within a dataset comprising 21,780 full-length human mRNA sequences. Numerous three-stemmed pseudoknots were identified. A selected set of 14 potential instances are presented, in which the start codon of the mRNA is found in close proximity either upstream, downstream, or within the identified three-stemmed pseudoknot. These pseudoknots likely play a role in translational initiation regulation. The probability of their existence gains support from their ranking as the most stable pseudoknot identified in the entire mRNA sequence, structural conservation across homologous mRNAs, stereochemical feasibility as demonstrated by structural modeling, and classification as members of the CPK-1 pseudoknot family, which includes many well-established pseudoknots. Furthermore, in four of the mRNAs, two or three closely spaced or tandem three-stemmed pseudoknots were identified. These findings suggest the frequent occurrence of three-stemmed pseudoknots in human mRNAs. A stepwise co-transcriptional folding mechanism is proposed for the formation of a three-stemmed pseudoknot structure. Our results not only provide fresh insights into the structures and functions of pseudoknots but also unveil the potential to target pseudoknots for treating human diseases.

Tying the knot: Unraveling the intricacies of the coronavirus frameshift pseudoknot

Understanding and targeting functional RNA structures towards treatment of coronavirus infection can help us to prepare for novel variants of SARS-CoV-2 (the virus causing COVID-19), and any other coronaviruses that could emerge via human-to-human transmission or potential zoonotic (inter-species) events. Leveraging the fact that all coronaviruses use a mechanism known as -1 programmed ribosomal frameshifting (-1 PRF) to replicate, we apply algorithms to predict the most energetically favourable secondary structures (each nucleotide involved in at most one pairing) that may be involved in regulating the -1 PRF event in coronaviruses, especially SARS-CoV-2. We compute previously unknown most stable structure predictions for the frameshift site of coronaviruses via hierarchical folding, a biologically motivated framework where initial non-crossing structure folds first, followed by subsequent, possibly crossing (pseudoknotted), structures. Using mutual information from 181 coronavirus sequences, in conjunction with the algorithm KnotAli, we compute secondary structure predictions for the frameshift site of different coronaviruses. We then utilize the Shapify algorithm to obtain most stable SARS-CoV-2 secondary structure predictions guided by frameshift sequence-specific and genome-wide experimental data. We build on our previous secondary structure investigation of the singular SARS-CoV-2 68 nt frameshift element sequence, by using Shapify to obtain predictions for 132 extended sequences and including covariation information. Previous investigations have not applied hierarchical folding to extended length SARS-CoV-2 frameshift sequences. By doing so, we simulate the effects of ribosome interaction with the frameshift site, providing insight to biological function. We contribute in-depth discussion to contextualize secondary structure dual-graph motifs for SARS-CoV-2, highlighting the energetic stability of the previously identified 3_8 motif alongside the known dominant 3_3 and 3_6 (native-type) -1 PRF structures. Using a combination of thermodynamic methods and sequence covariation, our novel predictions suggest function of the attenuator hairpin via previously unknown pseudoknotted base pairing. While certain initial RNA folding is consistent, other pseudoknotted base pairs form which indicate potential conformational switching between the two structures.

Estimating RNA Secondary Structure Folding Free Energy Changes with efn2

A number of analyses require estimates of the folding free energy changes of specific RNA secondary structures. These predictions are often based on a set of nearest neighbor parameters that models the folding stability of a RNA secondary structure as the sum of folding stabilities of the structural elements that comprise the secondary structure. In the software suite RNAstructure, the free energy change calculation is implemented in the program efn2. The efn2 program estimates the folding free energy change and the experimental uncertainty in the folding free energy change. It can be run through the graphical user interface for RNAstructure, from the command line, or a web server. This chapter provides detailed protocols for using efn2.

Recent trends in RNA informatics: a review of machine learning and deep learning for RNA secondary structure prediction and RNA drug discovery

Computational analysis of RNA sequences constitutes a crucial step in the field of RNA biology. As in other domains of the life sciences, the incorporation of artificial intelligence and machine learning techniques into RNA sequence analysis has gained significant traction in recent years. Historically, thermodynamics-based methods were widely employed for the prediction of RNA secondary structures; however, machine learning-based approaches have demonstrated remarkable advancements in recent years, enabling more accurate predictions. Consequently, the precision of sequence analysis pertaining to RNA secondary structures, such as RNA-protein interactions, has also been enhanced, making a substantial contribution to the field of RNA biology. Additionally, artificial intelligence and machine learning are also introducing technical innovations in the analysis of RNA-small molecule interactions for RNA-targeted drug discovery and in the design of RNA aptamers, where RNA serves as its own ligand. This review will highlight recent trends in the prediction of RNA secondary structure, RNA aptamers and RNA drug discovery using machine learning, deep learning and related technologies, and will also discuss potential future avenues in the field of RNA informatics.

Modelling the structures of frameshift-stimulatory pseudoknots from representative bat coronaviruses

Coronaviruses (CoVs) use -1 programmed ribosomal frameshifting stimulated by RNA pseudoknots in the viral genome to control expression of enzymes essential for replication, making CoV pseudoknots a promising target for anti-coronaviral drugs. Bats represent one of the largest reservoirs of CoVs and are the ultimate source of most CoVs infecting humans, including those causing SARS, MERS, and COVID-19. However, the structures of bat-CoV frameshift-stimulatory pseudoknots remain largely unexplored. Here we use a combination of blind structure prediction followed by all-atom molecular dynamics simulations to model the structures of eight pseudoknots that, together with the SARS-CoV-2 pseudoknot, are representative of the range of pseudoknot sequences in bat CoVs. We find that they all share some key qualitative features with the pseudoknot from SARS-CoV-2, notably the presence of conformers with two distinct fold topologies differing in whether or not the 5' end of the RNA is threaded through a junction, and similar conformations for stem 1. However, they differed in the number of helices present, with half sharing the 3-helix architecture of the SARS-CoV-2 pseudoknot but two containing 4 helices and two others only 2. These structure models should be helpful for future work studying bat-CoV pseudoknots as potential therapeutic targets.

Shapify: Paths to SARS-CoV-2 frameshifting pseudoknot

Multiple coronaviruses including MERS-CoV causing Middle East Respiratory Syndrome, SARS-CoV causing SARS, and SARS-CoV-2 causing COVID-19, use a mechanism known as -1 programmed ribosomal frameshifting (-1 PRF) to replicate. SARS-CoV-2 possesses a unique RNA pseudoknotted structure that stimulates -1 PRF. Targeting -1 PRF in SARS-CoV-2 to impair viral replication can improve patients' prognoses. Crucial to developing these therapies is understanding the structure of the SARS-CoV-2 -1 PRF pseudoknot. Our goal is to expand knowledge of -1 PRF structural conformations. Following a structural alignment approach, we identify similarities in -1 PRF pseudoknots of SARS-CoV-2, SARS-CoV, and MERS-CoV. We provide in-depth analysis of the SARS-CoV-2 and MERS-CoV -1 PRF pseudoknots, including reference and noteworthy mutated sequences. To better understand the impact of mutations, we provide insight on -1 PRF pseudoknot sequence mutations and their effect on resulting structures. We introduce Shapify, a novel algorithm that given an RNA sequence incorporates structural reactivity (SHAPE) data and partial structure information to output an RNA secondary structure prediction within a biologically sound hierarchical folding approach. Shapify enhances our understanding of SARS-CoV-2 -1 PRF pseudoknot conformations by providing energetically favourable predictions that are relevant to structure-function and may correlate with -1 PRF efficiency. Applied to the SARS-CoV-2 -1 PRF pseudoknot, Shapify unveils previously unknown paths from initial stems to pseudoknotted structures. By contextualizing our work with available experimental data, our structure predictions motivate future RNA structure-function research and can aid 3-D modeling of pseudoknots.

Rtools: A Web Server for Various Secondary Structural Analyses on Single RNA Sequences

Predicting the secondary structures of RNA molecules is an essential step to characterize their functions, but the thermodynamic probability of any prediction is generally small. On the other hand, there are a few tools for calculating and visualizing various secondary structural information from RNA sequences. We implemented a web server that calculates in parallel various features of secondary structures: different types of secondary structure predictions, the marginal probabilities for local structural contexts, accessibilities of the subsequences, the energy changes by arbitrary base mutations, and the measures for validations of the predicted secondary structures. The web server is available at http://rtools.cbrc.jp , which integrates software tools, CentroidFold, CentroidHomfold, IPknot, CapR, Raccess, Rchange, RintD, and RintW.

KnotAli: informed energy minimization through the use of evolutionary information

BACKGROUND

Improving the prediction of structures, especially those containing pseudoknots (structures with crossing base pairs) is an ongoing challenge. Homology-based methods utilize structural similarities within a family to predict the structure. However, their prediction is limited to the consensus structure, and by the quality of the alignment. Minimum free energy (MFE) based methods, on the other hand, do not rely on familial information and can predict structures of novel RNA molecules. Their prediction normally suffers from inaccuracies due to their underlying energy parameters.

RESULTS

We present a new method for prediction of RNA pseudoknotted secondary structures that combines the strengths of MFE prediction and alignment-based methods. KnotAli takes a multiple RNA sequence alignment as input and uses covariation and thermodynamic energy minimization to predict possibly pseudoknotted secondary structures for each individual sequence in the alignment. We compared KnotAli's performance to that of three other alignment-based programs, two that can handle pseudoknotted structures and one control, on a large data set of 3034 RNA sequences with varying lengths and levels of sequence conservation from 10 families with pseudoknotted and pseudoknot-free reference structures. We produced sequence alignments for each family using two well-known sequence aligners (MUSCLE and MAFFT).

CONCLUSIONS

We found KnotAli's performance to be superior in 6 of the 10 families for MUSCLE and 7 of the 10 for MAFFT. While both KnotAli and Cacofold use background noise correction strategies, we found KnotAli's predictions to be less dependent on the alignment quality. KnotAli can be found online at the Zenodo image: https://doi.org/10.5281/zenodo.5794719.

Identifying Inhibitors of −1 Programmed Ribosomal Frameshifting in a Broad Spectrum of Coronaviruses

Recurrent outbreaks of novel zoonotic coronavirus (CoV) diseases in recent years have highlighted the importance of developing therapeutics with broad-spectrum activity against CoVs. Because all CoVs use −1 programmed ribosomal frameshifting (−1 PRF) to control expression of key viral proteins, the frameshift signal in viral mRNA that stimulates −1 PRF provides a promising potential target for such therapeutics. To test the viability of this strategy, we explored whether small-molecule inhibitors of −1 PRF in SARS-CoV-2 also inhibited −1 PRF in a range of bat CoVs—the most likely source of future zoonoses. Six inhibitors identified in new and previous screens against SARS-CoV-2 were evaluated against the frameshift signals from a panel of representative bat CoVs as well as MERS-CoV. Some drugs had strong activity against subsets of these CoV-derived frameshift signals, while having limited to no effect on −1 PRF caused by frameshift signals from other viruses used as negative controls. Notably, the serine protease inhibitor nafamostat suppressed −1 PRF significantly for multiple CoV-derived frameshift signals. These results suggest it is possible to find small-molecule ligands that inhibit −1 PRF specifically in a broad spectrum of CoVs, establishing frameshift signals as a viable target for developing pan-coronaviral therapeutics.

RNA Structure Prediction, Analysis, and Design: An Introduction to Web-Based Tools

Understanding RNA structure has become critical in the study of RNA in their roles as mediators of biological processes. To aid in these studies, computational algorithms that utilize thermodynamics have been developed to predict RNA secondary structure. Due to the importance of intermolecular interactions, the algorithms have been expanded to determine and predict RNA-RNA hybridization. This chapter discusses popular webservers with the tools for RNA secondary structure prediction, RNA-RNA hybridization, and design. We address key features that distinguish common-functioning programs and their purposes for the interests of the user. Ultimately, we hope this review elucidates web-based tools researchers may take advantage of in their investigations of RNA structure and function.

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.

RNA Secondary Structure Prediction with Pseudoknots Using Chemical Reaction Optimization Algorithm

RNA molecules play a significant role in cell function especially including pseudoknots. In past decades, several methods have been developed to predict RNA secondary structure with pseudoknots and the most popular one uses minimum free energy. It is a nondeterministic polynomial-time hard (NP-hard) problem. We have proposed an approach based on a metaheuristic algorithm named Chemical Reaction Optimization (CRO) to solve the RNA pseudoknotted structure prediction problem. The reaction operators of CRO algorithm have been redesigned and used on the generated population to find the structure with the minimum free energy. Besides, we have developed an additional operator called Repair operator which has a great influence on our algorithm in increasing accuracy. It helps to increase the true positive base pairs while decreasing the false positive and false negative base pairs. Four energy models have been applied to calculate the energy. To evaluate the performance, we have used four datasets containing RNA pseudoknotted sequences taken from the RNA STRAND and Pseudobase++ database. We have compared the proposed approach with some existing algorithms and shown that our CRO based model is a better prediction method in terms of accuracy and speed.

Cotranscriptional Kinetic Folding of RNA Secondary Structures Including Pseudoknots

Computational prediction of ribonucleic acid (RNA) structures is an important problem in computational structural biology. Studies of RNA structure formation often assume that the process starts from a fully synthesized sequence. Experimental evidence, however, has shown that RNA folds concurrently with its elongation. We investigate RNA secondary structure formation, including pseudoknots, that takes into account the cotranscriptional effects. We propose a single-nucleotide resolution kinetic model of the folding process of RNA molecules, where the polymerase-driven elongation of an RNA strand by a new nucleotide is included as a primitive operation, together with a stochastic simulation method that implements this folding concurrently with the transcriptional synthesis. Numerical case studies show that our cotranscriptional RNA folding model can predict the formation of conformations that are favored in actual biological systems. Our new computational tool can thus provide quantitative predictions and offer useful insights into the kinetics of RNA folding.

A combinatorial method to isolate short ribozymes from complex ribozyme libraries

In vitro selections are the only known methods to generate catalytic RNAs (ribozymes) that do not exist in nature. Such new ribozymes are used as biochemical tools, or to address questions on early stages of life. In both cases, it is helpful to identify the shortest possible ribozymes since they are easier to deploy as a tool, and because they are more likely to have emerged in a prebiotic environment. One of our previous selection experiments led to a library containing hundreds of different ribozyme clusters that catalyze the triphosphorylation of their 5'-terminus. This selection showed that RNA systems can use the prebiotically plausible molecule cyclic trimetaphosphate as an energy source. From this selected ribozyme library, the shortest ribozyme that was previously identified had a length of 67 nucleotides. Here we describe a combinatorial method to identify short ribozymes from libraries containing many ribozymes. Using this protocol on the library of triphosphorylation ribozymes, we identified a 17-nucleotide sequence motif embedded in a 44-nucleotide pseudoknot structure. The described combinatorial approach can be used to analyze libraries obtained by different in vitro selection experiments.

An RNA pseudoknot is essential for standby-mediated translation of the tisB toxin mRNA in Escherichia coli

In response to DNA damage, Escherichia coli cells activate the expression of the toxin gene tisB of the toxin-antitoxin system tisB-istR1. Of three isoforms, only the processed, highly structured +42 tisB mRNA is active. Translation requires a standby site, composed of two essential elements: a single-stranded region located 100 nucleotides upstream of the sequestered RBS, and a structure near the 5'-end of the active mRNA. Here, we propose that this 5'-structure is an RNA pseudoknot which is required for 30S and protein S1-alone binding to the mRNA. Point mutations that prevent formation of this pseudoknot inhibit formation of translation initiation complexes, impair S1 and 30S binding to the mRNA, and render the tisB mRNA non-toxic in vivo. A set of mutations created in either the left or right arm of stem 2 of the pseudoknot entailed loss of toxicity upon overexpression of the corresponding mRNA variants. Combining the matching right-left arm mutations entirely restored toxicity levels to that of the wild-type, active mRNA. Finally, since many pseudoknots have high affinity for S1, we predicted similar pseudoknots in non-homologous type I toxin-antitoxin systems that exhibit features similar to that of tisB-IstR1, suggesting a shared requirement for standby acting at great distances.

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.

Structure-Altering Mutations of the SARS-CoV-2 Frame Shifting 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. While 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 frameshifting element (FSE), one of three highly conserved regions of coronaviruses, includes an RNA pseudoknot considered essential for this ribosomal switching. In this work, we apply our graph-theory-based framework for representing RNA secondary structures, "RAG" (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. Additionally, 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 to key residues of the SARS-CoV-2 virus as targets for anti-viral drugs and gene editing approaches.

Knotty: efficient and accurate prediction of complex RNA pseudoknot structures

Motivation

The computational prediction of RNA secondary structure by free energy minimization has become an important tool in RNA research. However in practice, energy minimization is mostly limited to pseudoknot-free structures or rather simple pseudoknots, not covering many biologically important structures such as kissing hairpins. Algorithms capable of predicting sufficiently complex pseudoknots (for sequences of length n) used to have extreme complexities, e.g. Pknots has O(n6) time and O(n4) space complexity. The algorithm CCJ dramatically improves the asymptotic run time for predicting complex pseudoknots (handling almost all relevant pseudoknots, while being slightly less general than Pknots), but this came at the cost of large constant factors in space and time, which strongly limited its practical application (∼200 bases already require 256 GB space).

Results

We present a CCJ-type algorithm, Knotty, that handles the same comprehensive pseudoknot class of structures as CCJ with improved space complexity of Θ(n3+Z)-due to the applied technique of sparsification, the number of 'candidates', Z, appears to grow significantly slower than n4 on our benchmark set (which include pseudoknotted RNAs up to 400 nt). In terms of run time over this benchmark, Knotty clearly outperforms Pknots and the original CCJ implementation, CCJ 1.0; Knotty's space consumption fundamentally improves over CCJ 1.0, being on a par with the space-economic Pknots. By comparing to CCJ 2.0, our unsparsified Knotty variant, we demonstrate the isolated effect of sparsification. Moreover, Knotty employs the state-of-the-art energy model of 'HotKnots DP09', which results in superior prediction accuracy over Pknots.

Availability and implementation

Our software is available at https://github.com/HosnaJabbari/Knotty.

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.

Age-dependent methylation in epigenetic clock CpGs is associated with G-quadruplex, co-transcriptionally formed RNA structures and tentative splice sites

Horvath's epigenetic clock consists of 353 CpGs whose methylation levels can accurately predict the age of individuals. Using bioinformatics analysis, we investigated the conformation, energy characteristics and presence of tentative splice sites of the sequences surrounding the epigenetic clock CpGs, in relation to the median methylation changes in different ages, the presence of CpG islands and their position in genes. Common characteristics in the 100 nt sequences surrounding the epigenetic clock CpGs are G-quadruplexes and/or tentative splice site motifs. Median methylation increases significantly in sequences which adopt less stable structures during transcription. Methylation is higher when CpGs overlap with G-quadruplexes than when they precede them. Median methylation in epigenetic clock CpGs is higher in sequences expressed as single products rather than in multiple products and those containing single donors and multiple acceptors. Age-related methylation variation is significant in sequences without G-quadruplexes, particularly those producing low stability nascent RNA and those with splice sites. CpGs in sequences close to transcription start sites and those which are possibly never expressed (hypothetical proteins) undergo similar extent of age-related median methylation decrease and increase. Preservation of methylation is observed in CpG islands without G-quadruplexes, contrary to CpGs far from CpG islands (open sea). Sequences containing G-quadruplexes and RNA pseudoknots, determining the recognition by H3K27 histone methyltransferase, are hypomethylated. The presented structural DNA and co-transcriptional RNA analysis of epigenetic clock sequences, foreshadows the association of age-related methylation changes with the principle biological processes of DNA and histone methylation, splicing and chromatin silencing.

Modification of betanodavirus virulence by substitutions in the 3' terminal region of RNA2

Betanodaviruses have bi-segmented positive-sense RNA genomes, consisting of RNAs 1 and 2. For some members of the related genus alphanodavirus, the 3' terminal 50 nucleotides (nt) of RNA2, including a predicted stem-loop structure (3'SL), are essential for replication. We investigate the possible existence and role of a similar structure in a reassortant betanodavirus strain (RGNNV/SJNNV). In this study, we developed three recombinant strains containing nucleotide changes at positions 1408 and 1412. Predictive models showed stem-loop structures involving nt 1398-1421 of the natural reassortant whereas this structure is modified in the recombinant viruses harbouring point mutations r1408 and r1408-1412, but not in r1412. Results obtained from infectivity assays showed differences between the reference strains and the mutants in both RNA1 and RNA2 synthesis. Moreover, an imbalance between the synthesis of both segments was demonstrated, mainly with the double mutant. All these results suggest an interaction between RNA1 and the 3' non-coding regions (3'NCR) of RNA2. In addition, the significant attenuation of the virulence for Senegalese sole and the delayed replication of r1408-1412 in brain tissues may point to an interaction of RNA2 with host cellular proteins.

RNA secondary structure prediction with pseudoknots: Contribution of algorithm versus energy model

Motivation

RNA is a biopolymer with various applications inside the cell and in biotechnology. Structure of an RNA molecule mainly determines its function and is essential to guide nanostructure design. Since experimental structure determination is time-consuming and expensive, accurate computational prediction of RNA structure is of great importance. Prediction of RNA secondary structure is relatively simpler than its tertiary structure and provides information about its tertiary structure, therefore, RNA secondary structure prediction has received attention in the past decades. Numerous methods with different folding approaches have been developed for RNA secondary structure prediction. While methods for prediction of RNA pseudoknot-free structure (structures with no crossing base pairs) have greatly improved in terms of their accuracy, methods for prediction of RNA pseudoknotted secondary structure (structures with crossing base pairs) still have room for improvement. A long-standing question for improving the prediction accuracy of RNA pseudoknotted secondary structure is whether to focus on the prediction algorithm or the underlying energy model, as there is a trade-off on computational cost of the prediction algorithm versus the generality of the method.

Results

The aim of this work is to argue when comparing different methods for RNA pseudoknotted structure prediction, the combination of algorithm and energy model should be considered and a method should not be considered superior or inferior to others if they do not use the same scoring model. We demonstrate that while the folding approach is important in structure prediction, it is not the only important factor in prediction accuracy of a given method as the underlying energy model is also as of great value. Therefore we encourage researchers to pay particular attention in comparing methods with different energy models.

Differentially expressed microRNAs in diapausing versus HCl-treated Bombyx embryos

Differentially expressed microRNAs were detected to explore the molecular mechanisms of diapause termination. The total small RNA of diapause-destined silkworm eggs and HCl-treated eggs was extracted and then sequenced using HiSeq high-throughput method. 44 novel miRNAs were discovered. Compared to those in the diapause-destined eggs, 61 miRNAs showed significant changes in the acid-treated eggs, with 23 being up-regulated and 38 being down-regulated. The potential target genes of differentially expressed miRNAs were predicted by miRanda. Gene Ontology and KEGG pathway enrichment analysis of these potential target genes revealed that they were mainly located within cells and organelles, involved in cellular and metabolic processes, and participated in protein production, processing and transportation. Two differentially expressed genes, Bombyx mori SDH and Bmo-miR-2761-3p, were further analyzed with qRT-PCR. BmSDH was significantly up-regulated in the HCl-treated eggs, while Bmo-miR-2761-3p was down-regulated. These results suggested that these two genes were well coordinated in silkworm eggs. Dual luciferase reporter assay demonstrated that Bmo-miR-2761-3p inhibited the expression of BmSDH.

Association of low race performance with mtDNA haplogroup L3b of Australian thoroughbred horses

Mitochondrial DNA (mtDNA) encodes the genes for respiratory chain sub-units that determine the efficiency of oxidative phosphorylation in mitochondria. The aim of this study was to determine if there were any haplogroups and variants in mtDNA that could be associated with athletic performance of Thoroughbred horses. The whole mitochondrial genomes of 53 maternally unrelated Australian Thoroughbred horses were sequenced and an association study was performed with the competition histories of 1123 horses within their maternal lineages. A horse mtDNA phylogenetic tree was constructed based on a total of 195 sequences (including 142 from previous reports). The association analysis showed that the sample groups with poor racing performance history were enriched in haplogroup L3b (p = .0003) and its sub-haplogroup L3b1a (p = .0007), while those that had elite performance appeared to be not significantly associated with haplogroups G2 and L3a1a1a (p > .05). Haplogroup L3b and L3b1a bear two and five specific variants of which variant T1458C (site 345 in 16s rRNA) is the only potential functional variant. Furthermore, secondary reconstruction of 16s RNA showed considerable differences between two types of 16s RNA molecules (with and without T1458C), indicating a potential functional effect. The results suggested that haplogroup L3b, could have a negative association with elite performance. The T1458C mutation harboured in haplogroup L3b could have a functional effect that is related to poor athletic performance.

Rtools: a web server for various secondary structural analyses on single RNA sequences

The secondary structures, as well as the nucleotide sequences, are the important features of RNA molecules to characterize their functions. According to the thermodynamic model, however, the probability of any secondary structure is very small. As a consequence, any tool to predict the secondary structures of RNAs has limited accuracy. On the other hand, there are a few tools to compensate the imperfect predictions by calculating and visualizing the secondary structural information from RNA sequences. It is desirable to obtain the rich information from those tools through a friendly interface. We implemented a web server of the tools to predict secondary structures and to calculate various structural features based on the energy models of secondary structures. By just giving an RNA sequence to the web server, the user can get the different types of solutions of the secondary structures, the marginal probabilities such as base-paring probabilities, loop probabilities and accessibilities of the local bases, the energy changes by arbitrary base mutations as well as the measures for validations of the predicted secondary structures. The web server is available at http://rtools.cbrc.jp, which integrates software tools, CentroidFold, CentroidHomfold, IPKnot, CapR, Raccess, Rchange and RintD.

A Method to Predict the Structure and Stability of RNA/RNA Complexes

RNA/RNA interactions are essential for genomic RNA dimerization and regulation of gene expression. Intermolecular loop-loop base pairing is a widespread and functionally important tertiary structure motif in RNA machinery. However, computational prediction of intermolecular loop-loop base pairing is challenged by the entropy and free energy calculation due to the conformational constraint and the intermolecular interactions. In this chapter, we describe a recently developed statistical mechanics-based method for the prediction of RNA/RNA complex structures and stabilities. The method is based on the virtual bond RNA folding model (Vfold). The main emphasis in the method is placed on the evaluation of the entropy and free energy for the loops, especially tertiary kissing loops. The method also uses recursive partition function calculations and two-step screening algorithm for large, complicated structures of RNA/RNA complexes. As case studies, we use the HIV-1 Mal dimer and the siRNA/HIV-1 mutant (T4) to illustrate the method.

Molecular knots in biology and chemistry

Knots and entanglements are ubiquitous. Beyond their aesthetic appeal, these fascinating topological entities can be either useful or cumbersome. In recent decades, the importance and prevalence of molecular knots have been increasingly recognised by scientists from different disciplines. In this review, we provide an overview on the various molecular knots found in naturally occurring biological systems (DNA, RNA and proteins), and those created by synthetic chemists. We discuss the current knowledge in these fields, including recent developments in experimental and, in some cases, computational studies which are beginning to shed light into the complex interplay between the structure, formation and properties of these topologically intricate molecules.

Physics-based RNA structure prediction

Despite the success of RNA secondary structure prediction for simple, short RNAs, the problem of predicting RNAs with long-range tertiary folds remains. Furthermore, RNA 3D structure prediction is hampered by the lack of the knowledge about the tertiary contacts and their thermodynamic parameters. Low-resolution structural modeling enables us to estimate the conformational entropies for a number of tertiary folds through rigorous statistical mechanical calculations. The models lead to 3D tertiary folds at coarse-grained level. The coarse-grained structures serve as the initial structures for all-atom molecular dynamics refinement to build the final all-atom 3D structures. In this paper, we present an overview of RNA computational models for secondary and tertiary structures’ predictions and then focus on a recently developed RNA statistical mechanical model—the Vfold model. The main emphasis is placed on the physics behind the models, including the treatment of the non-canonical interactions in secondary and tertiary structure modelings, and the correlations to RNA functions.

RNA secondary structure prediction from multi-aligned sequences

It has been well accepted that the RNA secondary structures of most functional non-coding RNAs (ncRNAs) are closely related to their functions and are conserved during evolution. Hence, prediction of conserved secondary structures from evolutionarily related sequences is one important task in RNA bioinformatics; the methods are useful not only to further functional analyses of ncRNAs but also to improve the accuracy of secondary structure predictions and to find novel functional RNAs from the genome. In this review, I focus on common secondary structure prediction from a given aligned RNA sequence, in which one secondary structure whose length is equal to that of the input alignment is predicted. I systematically review and classify existing tools and algorithms for the problem, by utilizing the information employed in the tools and by adopting a unified viewpoint based on maximum expected gain (MEG) estimators. I believe that this classification will allow a deeper understanding of each tool and provide users with useful information for selecting tools for common secondary structure predictions.

Vfold: a web server for RNA structure and folding thermodynamics prediction

BACKGROUND

The ever increasing discovery of non-coding RNAs leads to unprecedented demand for the accurate modeling of RNA folding, including the predictions of two-dimensional (base pair) and three-dimensional all-atom structures and folding stabilities. Accurate modeling of RNA structure and stability has far-reaching impact on our understanding of RNA functions in human health and our ability to design RNA-based therapeutic strategies.

RESULTS

The Vfold server offers a web interface to predict (a) RNA two-dimensional structure from the nucleotide sequence, (b) three-dimensional structure from the two-dimensional structure and the sequence, and (c) folding thermodynamics (heat capacity melting curve) from the sequence. To predict the two-dimensional structure (base pairs), the server generates an ensemble of structures, including loop structures with the different intra-loop mismatches, and evaluates the free energies using the experimental parameters for the base stacks and the loop entropy parameters given by a coarse-grained RNA folding model (the Vfold model) for the loops. To predict the three-dimensional structure, the server assembles the motif scaffolds using structure templates extracted from the known PDB structures and refines the structure using all-atom energy minimization.

CONCLUSIONS

The Vfold-based web server provides a user friendly tool for the prediction of RNA structure and stability. The web server and the source codes are freely accessible for public use at "http://rna.physics.missouri.edu".

Fine-grained parallelism accelerating for RNA secondary structure prediction with pseudoknots based on FPGA

PKNOTS is a most famous benchmark program and has been widely used to predict RNA secondary structure including pseudoknots. It adopts the standard four-dimensional (4D) dynamic programming (DP) method and is the basis of many variants and improved algorithms. Unfortunately, the O(N(6)) computing requirements and complicated data dependency greatly limits the usefulness of PKNOTS package with the explosion in gene database size. In this paper, we present a fine-grained parallel PKNOTS package and prototype system for accelerating RNA folding application based on FPGA chip. We adopted a series of storage optimization strategies to resolve the "Memory Wall" problem. We aggressively exploit parallel computing strategies to improve computational efficiency. We also propose several methods that collectively reduce the storage requirements for FPGA on-chip memory. To the best of our knowledge, our design is the first FPGA implementation for accelerating 4D DP problem for RNA folding application including pseudoknots. The experimental results show a factor of more than 50x average speedup over the PKNOTS-1.08 software running on a PC platform with Intel Core2 Q9400 Quad CPU for input RNA sequences. However, the power consumption of our FPGA accelerator is only about 50% of the general-purpose micro-processors.

Predicting structure and stability for RNA complexes with intermolecular loop-loop base-pairing

RNA loop-loop interactions are essential for genomic RNA dimerization and regulation of gene expression. In this article, a statistical mechanics-based computational method that predicts the structures and thermodynamic stabilities of RNA complexes with loop-loop kissing interactions is described. The method accounts for the entropy changes for the formation of loop-loop interactions, which is a notable advancement that other computational models have neglected. Benchmark tests with several experimentally validated systems show that the inclusion of the entropy parameters can indeed improve predictions for RNA complexes. Furthermore, the method can predict not only the native structures of RNA/RNA complexes but also alternative metastable structures. For instance, the model predicts that the SL1 domain of HIV-1 RNA can form two different dimer structures with similar stabilities. The prediction is consistent with experimental observation. In addition, the model predicts two different binding sites for hTR dimerization: One binding site has been experimentally proposed, and the other structure, which has a higher stability, is structurally feasible and needs further experimental validation.

A fast and robust iterative algorithm for prediction of RNA pseudoknotted secondary structures

Background

Improving accuracy and efficiency of computational methods that predict pseudoknotted RNA secondary structures is an ongoing challenge. Existing methods based on free energy minimization tend to be very slow and are limited in the types of pseudoknots that they can predict. Incorporating known structural information can improve prediction accuracy; however, there are not many methods for prediction of pseudoknotted structures that can incorporate structural information as input. There is even less understanding of the relative robustness of these methods with respect to partial information.

Results

We present a new method, Iterative HFold, for pseudoknotted RNA secondary structure prediction. Iterative HFold takes as input a pseudoknot-free structure, and produces a possibly pseudoknotted structure whose energy is at least as low as that of any (density-2) pseudoknotted structure containing the input structure. Iterative HFold leverages strengths of earlier methods, namely the fast running time of HFold, a method that is based on the hierarchical folding hypothesis, and the energy parameters of HotKnots V2.0.

Our experimental evaluation on a large data set shows that Iterative HFold is robust with respect to partial information, with average accuracy on pseudoknotted structures steadily increasing from roughly 54% to 79% as the user provides up to 40% of the input structure.

Iterative HFold is much faster than HotKnots V2.0, while having comparable accuracy. Iterative HFold also has significantly better accuracy than IPknot on our HK-PK and IP-pk168 data sets.

Conclusions

Iterative HFold is a robust method for prediction of pseudoknotted RNA secondary structures, whose accuracy with more than 5% information about true pseudoknot-free structures is better than that of IPknot, and with about 35% information about true pseudoknot-free structures compares well with that of HotKnots V2.0 while being significantly faster. Iterative HFold and all data used in this work are freely available at http://www.cs.ubc.ca/~hjabbari/software.php.

e-RNA: a collection of web servers for comparative RNA structure prediction and visualisation

e-RNA offers a free and open-access collection of five published RNA sequence analysis tools, each solving specific problems not readily addressed by other available tools. Given multiple sequence alignments, Transat detects all conserved helices, including those expected in a final structure, but also transient, alternative and pseudo-knotted helices. RNA-Decoder uses unique evolutionary models to detect conserved RNA secondary structure in alignments which may be partly protein-coding. SimulFold simultaneously co-estimates the potentially pseudo-knotted conserved structure, alignment and phylogenetic tree for a set of homologous input sequences. CoFold predicts the minimum-free energy structure for an input sequence while taking the effects of co-transcriptional folding into account, thereby greatly improving the prediction accuracy for long sequences. R-chie is a program to visualise RNA secondary structures as arc diagrams, allowing for easy comparison and analysis of conserved base-pairs and quantitative features. The web site server dispatches user jobs to a cluster, where up to 100 jobs can be processed in parallel. Upon job completion, users can retrieve their results via a bookmarked or emailed link. e-RNA is located at http://www.e-rna.org.

A stochastic model of translation with -1 programmed ribosomal frameshifting

Many viruses produce multiple proteins from a single mRNA sequence by encoding overlapping genes. One mechanism to decode both genes, which reside in alternate reading frames, is -1 programmed ribosomal frameshifting. Although recognized for over 25 years, the molecular and physical mechanism of -1 frameshifting remains poorly understood. We have developed a mathematical model that treats mRNA translation and associated -1 frameshifting as a stochastic process in which the transition probabilities are based on the energetics of local molecular interactions. The model predicts both the location and efficiency of -1 frameshift events in HIV-1. Moreover, we compute -1 frameshift efficiencies upon mutations in the viral mRNA sequence and variations in relative tRNA abundances, predictions that are directly testable in experiment.

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.

Secondary Structure Predictions for Long RNA Sequences Based on Inversion Excursions and MapReduce

Secondary structures of ribonucleic acid (RNA) molecules play important roles in many biological processes including gene expression and regulation. Experimental observations and computing limitations suggest that we can approach the secondary structure prediction problem for long RNA sequences by segmenting them into shorter chunks, predicting the secondary structures of each chunk individually using existing prediction programs, and then assembling the results to give the structure of the original sequence. The selection of cutting points is a crucial component of the segmenting step. Noting that stem-loops and pseudoknots always contain an inversion, i.e., a stretch of nucleotides followed closely by its inverse complementary sequence, we developed two cutting methods for segmenting long RNA sequences based on inversion excursions: the centered and optimized method. Each step of searching for inversions, chunking, and predictions can be performed in parallel. In this paper we use a MapReduce framework, i.e., Hadoop, to extensively explore meaningful inversion stem lengths and gap sizes for the segmentation and identify correlations between chunking methods and prediction accuracy. We show that for a set of long RNA sequences in the RFAM database, whose secondary structures are known to contain pseudoknots, our approach predicts secondary structures more accurately than methods that do not segment the sequence, when the latter predictions are possible computationally. We also show that, as sequences exceed certain lengths, some programs cannot computationally predict pseudoknots while our chunking methods can. Overall, our predicted structures still retain the accuracy level of the original prediction programs when compared with known experimental secondary structure.

Accurate SHAPE-directed RNA secondary structure modeling, including pseudoknots

A pseudoknot forms in an RNA when nucleotides in a loop pair with a region outside the helices that close the loop. Pseudoknots occur relatively rarely in RNA but are highly overrepresented in functionally critical motifs in large catalytic RNAs, in riboswitches, and in regulatory elements of viruses. Pseudoknots are usually excluded from RNA structure prediction algorithms. When included, these pairings are difficult to model accurately, especially in large RNAs, because allowing this structure dramatically increases the number of possible incorrect folds and because it is difficult to search the fold space for an optimal structure. We have developed a concise secondary structure modeling approach that combines SHAPE (selective 2'-hydroxyl acylation analyzed by primer extension) experimental chemical probing information and a simple, but robust, energy model for the entropic cost of single pseudoknot formation. Structures are predicted with iterative refinement, using a dynamic programming algorithm. This melded experimental and thermodynamic energy function predicted the secondary structures and the pseudoknots for a set of 21 challenging RNAs of known structure ranging in size from 34 to 530 nt. On average, 93% of known base pairs were predicted, and all pseudoknots in well-folded RNAs were identified.

Computational analysis of noncoding RNAs

Noncoding RNAs have emerged as important key players in the cell. Understanding their surprisingly diverse range of functions is challenging for experimental and computational biology. Here, we review computational methods to analyze noncoding RNAs. The topics covered include basic and advanced techniques to predict RNA structures, annotation of noncoding RNAs in genomic data, mining RNA-seq data for novel transcripts and prediction of transcript structures, computational aspects of microRNAs, and database resources.

Rtips: fast and accurate tools for RNA 2D structure prediction using integer programming

We present a web-based tool set Rtips for fast and accurate prediction of RNA 2D complex structures. Rtips comprises two computational tools based on integer programming, IPknot for predicting RNA secondary structures with pseudoknots and RactIP for predicting RNA–RNA interactions with kissing hairpins. Both servers can run much faster than existing services with the same purpose on large data sets as well as being at least comparable in prediction accuracy. The Rtips web server along with the stand-alone programs is freely accessible at http://rna.naist.jp/.

Predicting kissing interactions in microRNA-target complex and assessment of microRNA activity

MicroRNAs (miRNAs) are a class of short RNA molecules that play an important role in post-transcriptional gene regulation. Computational prediction of the miRNA target sites in mRNA is crucial for understanding the mechanism of miRNA-mRNA interactions. We here develop a new computational model that allows us to treat a variety of miRNA-mRNA kissing interactions, which have been ignored in the currently existing miRNA target prediction algorithms. By including all the different inter- and intra-molecular base pairs, this new model can predict both the structural accessibility of the target sites and the binding affinity (free energy). Applications of the model to a test set of 105 miRNA-gene systems show a notably improved success rate of 83/105. We found that although the binding affinity alone predicts the miRNA repression efficiency with a high success rate of 73/105, the structure in the seed region can significantly influence the miRNA activity. The method also allows us to efficiently search for the potent miRNA from a pool of miRNA candidates for any given gene target. Furthermore, extension of the method may enable predictions of the three-dimensional (3D) structures of miRNA/mRNA complexes.

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.

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.

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.

Structure and stability of RNA/RNA kissing complex: with application to HIV dimerization initiation signal

We develop a statistical mechanical model to predict the structure and folding stability of the RNA/RNA kissing-loop complex. One of the key ingredients of the theory is the conformational entropy for the RNA/RNA kissing complex. We employ the recently developed virtual bond-based RNA folding model (Vfold model) to evaluate the entropy parameters for the different types of kissing loops. A benchmark test against experiments suggests that the entropy calculation is reliable. As an application of the model, we apply the model to investigate the structure and folding thermodynamics for the kissing complex of the HIV-1 dimerization initiation signal. With the physics-based energetic parameters, we compute the free energy landscape for the HIV-1 dimer. From the energy landscape, we identify two minimal free energy structures, which correspond to the kissing-loop dimer and the extended-duplex dimer, respectively. The results support the two-step dimerization process for the HIV-1 replication cycle. Furthermore, based on the Vfold model and energy minimization, the theory can predict the native structure as well as the local minima in the free energy landscape. The root-mean-square deviations (RMSDs) for the predicted kissing-loop dimer and extended-duplex dimer are ~3.0 Å. The method developed here provides a new method to study the RNA/RNA kissing complex.

ViennaRNA Package 2.0

Background

Secondary structure forms an important intermediate level of description of nucleic acids that encapsulates the dominating part of the folding energy, is often well conserved in evolution, and is routinely used as a basis to explain experimental findings. Based on carefully measured thermodynamic parameters, exact dynamic programming algorithms can be used to compute ground states, base pairing probabilities, as well as thermodynamic properties.

Results

The ViennaRNA Package has been a widely used compilation of RNA secondary structure related computer programs for nearly two decades. Major changes in the structure of the standard energy model, the Turner 2004 parameters, the pervasive use of multi-core CPUs, and an increasing number of algorithmic variants prompted a major technical overhaul of both the underlying RNAlib and the interactive user programs. New features include an expanded repertoire of tools to assess RNA-RNA interactions and restricted ensembles of structures, additional output information such as centroid structures and maximum expected accuracy structures derived from base pairing probabilities, or z-scores for locally stable secondary structures, and support for input in fasta format. Updates were implemented without compromising the computational efficiency of the core algorithms and ensuring compatibility with earlier versions.

Conclusions

The ViennaRNA Package 2.0, supporting concurrent computations via OpenMP, can be downloaded from http://www.tbi.univie.ac.at/RNA.