Search

Previously, we have introduced an improved version of jViz.RNA which enabled faster and more stable RNA visualization by employing compressed tree graphs. However, the new RNA representation and visualization method required a sophisticated mechanism of pseudoknot visualization. In this work, we present our novel pseudoknot classification and implementation of pseudoknot visualization in the context of the new RNA graph model. We then compare our approach with other RNA visualization software, and demonstrate jViz.RNA 4.0's benefits compared to other software. Additionally, we introduce interactive editing functionality into jViz.RNA and demonstrate its benefits in exploring and building RNA structures. The results presented highlight the new high degree of utility jViz.RNA 4.0 now offers. Users are now able to visualize pseudoknotted RNA, manipulate the resulting automatic layouts to suit their individual needs, and change both positioning and connectivity of the RNA molecules examined. Care was taken to limit overlap between structural elements, particularly in the case of pseudoknots to ensure an intuitive and informative layout of the final RNA structure. Availability: The software is freely available at: https://jviz.cs.sfu.ca/.

RNA visualization is crucial in order to understand the relationship that exists between RNA structure and its function, as well as the development of better RNA structure prediction algorithms. However, in the context of RNA visualization, one key structure remains difficult to visualize: Pseudoknots. Pseudoknots occur in RNA folding when two secondary structural components form base-pairs between them. The three-dimensional nature of these components makes them challenging to visualize in two-dimensional media, such as print media or screens. In this review, we focus on the advancements that have been made in the field of RNA visualization in two-dimensional media in the past two decades. The review aims at presenting all relevant aspects of pseudoknot visualization. We start with an overview of several pseudoknotted structures and their relevance in RNA function. Next, we discuss the theoretical basis for RNA structural topology classification and present RNA classification systems for both pseudoknotted and non-pseudoknotted RNAs. Each description of RNA classification system is followed by a discussion of the software tools and algorithms developed to date to visualize RNA, comparing the different tools’ strengths and shortcomings.

Ribonucleic acid (RNA), a single-stranded linear molecule, is essential to all biological systems. Different regions of the same RNA strand will fold together via base pair interactions to make intricate secondary and tertiary structures that guide crucial homeostatic processes in living organisms. Since the structure of RNA molecules is the key to their function, algorithms for the prediction of RNA structure are of great value. In this article, we demonstrate the usefulness of SARNA{\hbox{-}}Predict, an RNA secondary structure prediction algorithm based on Simulated Annealing (SA). A performance evaluation of SARNA{\hbox{-}}Predict in terms of prediction accuracy is made via comparison with eight state-of-the-art RNA prediction algorithms: mfold, Pseudoknot (pknotsRE), NUPACK, pknotsRG{\hbox{-}}mfe, Sfold, HotKnots, ILM, and STAR. These algorithms are from three different classes: heuristic,dynamic programming, and statistical sampling techniques. An evaluation for the performance of SARNA{\hbox{-}}Predict in terms of prediction accuracy was verified with native structures. Experiments on 33 individual known structures from eleven RNA classes (tRNA, viral RNA, antigenomic HDV, telomerase RNA, tmRNA, rRNA, RNaseP, 5S rRNA, Group I intron 23S rRNA, Group I intron 16S rRNA, and 16S rRNA) were performed. The results presented in this paper demonstrate that SARNA{\hbox{-}}Predict can out-perform other state-of-the-art algorithms in terms of prediction accuracy. Furthermore, there is substantial improvement of prediction accuracy by incorporating a more sophisticated thermodynamic model (efn2).

Motivation: Ribonucleic acid is vital in numerous stages of protein synthesis; it also possesses important functional and structural roles within the cell. The function of an RNA molecule within a particular organic system is principally determined by its structure. The current physical methods available for structure determination are time-consuming and expensive. Hence, computational methods for structure prediction are sought after. The energies involved by the formation of secondary structure elements are significantly greater than those of tertiary elements. Therefore, RNA structure prediction focuses on secondary structure. Results: We present P-RnaPredict, a parallel evolutionary algorithm for RNA secondary structure prediction. The speedup provided by parallelization is investigated with five sequences, and a dramatic improvement in speedup is demonstrated, especially with longer sequences. An evaluation of the performance of P-RnaPredict in terms of prediction accuracy is made through comparison with 10 individual known structures from 3 RNA classes (5S rRNA, Group I intron 16S rRNA and 16S rRNA) and the mfold dynamic programming algorithm. P-RnaPredict is able to predict structures with higher true positive base pair counts and lower false positives than mfold on certain sequences. Availability: P-RnaPredict is available for non-commercial usage. Interested parties should contact Kay C. Wiese (wiese@cs.sfu.ca). Contact: wiese@cs.sfu.ca

Many tools have been developed for visualization of RNA secondary structures using a variety of techniques and output formats. However, each tool is typically limited to one or two of the visualization models discussed in this paper, supports only a single file format, and is tied to a specific platform. In order for structure prediction researchers to better understand the results of their algorithms and to enable life science researchers to interpret RNA structure easily, it is helpful to provide them with a flexible and powerful tool. jViz.Rna is a multiplatform visualization tool capable of displaying RNA secondary structures encoded in a variety of file formats. The same structure can be viewed using any of the models supported, including linked graph, circle graph, dot plot, and classical structure. Also, the output is dynamic and can easily be further manipulated by the user. In addition, any of the drawings produced can be saved in either the EPS or PNG file formats enabling easy usage in publications and presentations.

Covariance models provide excellent accuracy for ncRNA homology search. However, high computational complexity has limited their usefulness. This research improves the covariance model's search efficiency by building combined models for a group of different RNA families, which is selected using a clustering strategy. A series of combined partial covariance models are built from the stem loop structural elements that the ncRNA gene families share. Experimental results suggest that for most RNA gene families investigated, our combination search method successfully provides run time improvement with acceptable accuracy. Although there still exist limitations such as recall loss for a few RNA gene families, this novel combination approach has implications for future studies of reducing covariance model's search complexity.

An exploration of the use of multiple secondary structure elements for structural RNA gene finding is conducted. The secondary structure models are combined through a multilayer voting system which first combines the probability output of support vector machines and then combines the results of those votes to predict whether a sequence is a structural RNA gene or not. It is found that the voting in the first layer of the system has significant impact on the performance of individual secondary structure element models with improvements in classification results of up to 56%. Likewise, gains in classification F-measure over 0.6 were seen when two secondary structure element model predictions were voted together. When all the secondary structure element models were used in voting, an accuracy of over 93% was achieved by the secondary structure RNA gene classification system.

This paper explores the use of RNA structural elements for RNA gene finding. A classification experiment is performed in which several support vector machine models, based on the properties of individual RNA secondary structure elements, are trained and tested, revealing the structural elements which have properties useful for RNA gene finding. The study finds that the external loop and structure elements with classification accuracies of over 84% and the stemloop, hairpin, and tail elements with classification accuracies around 70% are the most likely structural elements to be successfully exploited by future RNA gene finders.

The shape that organic molecules such as biopolymers form within organic systems largely determines the function said molecules perform. RNA is a biopolymer that plays a central part in several stages of protein synthesis, and also has structural, functional, and regulatory roles in the cell. In an ab initio case most common structure prediction techniques employ minimization of the free energy of a given RNA molecule via a thermodynamic model. RnaPredict is an evolutionary algorithm for RNA folding. This paper compares the performance of an advanced thermodynamic model, efn2, against the stacking-energy thermodynamic models INN and INN-HB on a test set containing 24 sequences from 4 rRNA subtypes. The prediction accuracy of efn2 is demonstrated on a majority of test sequences. A comparison is also made with the mfold prediction algorithm which demonstrated RnaPredict's comparable performance.

Beyond its critical role in protein synthesis, RNA has vital structural, functional, and regulatory roles in the cell. The shape of an RNA molecule primarily determines its function in organic systems, so there is notable interest in the computational prediction of RNA structure. Pseudoknots are relatively rare but important structural elements which are difficult to predict computationally. RnaPredict is an evolutionary algorithm (EA) developed for the prediction of RNA secondary structure. This research evaluates RnaPredict after its enhancement with the thermodynamic model from HotKnots, a model specifically designed to compute free energies of structures containing pseudoknots. The performance of the EA is evaluated against the original HotKnots algorithm. RnaPredict significantly improved upon the sensitivity and specificity of structures predicted by HotKnots.

RNA has important structural, functional, and regulatory parts in the cell as well as a critical role in multiple stages of protein synthesis. An RNA molecule's shape largely determines its function in an organic system. Accordingly, computational RNA structural prediction methods are of significant interest. For ab initio cases where only an RNA sequence is known, structure prediction techniques typically employ free energy minimization of a given RNA molecule via a thermodynamic model. Unfortunately, the minimum free energy structure is rarely the native structure. This is thought to be due to errors in the experimentally determined thermodynamic model parameters. RnaPredict is an evolutionary algorithm designed for the prediction of RNA secondary structure; it currently utilizes the stacking-energy thermodynamic models INN and INN-HB. The effect of an enhanced model, efn2, on RnaPredict is investigated. The efn2 model significantly improved the sensitivity and specificity of the majority of structures evaluated.

Recently, there is a resurgence of interest in the RNA secondary structure prediction problem due to the discovery of many new families of non-coding RNAs with a variety of functions. This paper describes and presents a novel algorithm for RNA secondary structure prediction based on an ensemble-based approach. An evaluation of the performance in terms of sensitivity and specificity is made. Experiments were performed on eleven structures from four RNA classes (RNaseP, Group I intron 16S rRNA, Group I intron 23S rRNA and 16S rRNA). Three RNA secondary structure similarity metrics (base pair distance, tree edit distance, and thermodynamic energy distance) and their effects on the clustering algorithm were explored. The significant contribution of this paper is in the examining of the various results from employing different dissimilarity metrics. Overall, the base pair distance dissimilarity metric shows better results with the other two distance metrics (tree edit distance and thermodynamic energy distance). The results presented in this paper demonstrate that SARNA-Ensemble-Predict can give comparable performance to a state-of-the-art algorithm Sfold in terms of sensitivity.

Several factors make stem-loops an attractive sequence signal for a structural RNA gene-finder. Structural RNAs are virtually obligated to form stem-loops on their way to forming stable structures. Also, stem-loops can be identified along a sequence of length n in O(n) time. We postulate that stem-loops found in structural RNA genes may tend to be longer than those found in their genomic counterparts - coding sequences and noncoding DNA. We also postulate that stem-loops may occur in higher frequency in the structural RNA regions.

Pseudoknots are RNA tertiary structures which perform essential biological functions. This paper presents SARNA-Predict-pk, an algorithm for pseudoknotted RNA secondary structure prediction based on Simulated Annealing (SA). The research presented here extends previous work of SARNA-Predict and incorporates a new thermodynamic model into the algorithm, effectively enabling it to predict pseudo-knotted RNA structures. An evaluation of the performance of SARNA-Predict-pk in terms of prediction accuracy is made via comparison with several state-of-the-art prediction algorithms. We measured the sensitivity and specificity using five prediction algorithms. Three of these are dynamic programming algorithms: Pseudoknot (pknotsRE), NUPACK, and pknotsRG-mfe. The other two are heuristic algorithms: SARNA-Predict-pk and HotKnots algorithms. An evaluation for the performance of SARNA-Predict-pk in terms of prediction accuracy was verified with native structures. Experiments on ten individual known structures from six RNA classes (tRNA, viral RNA, anti-genomic HDV, telomerase RNA, tmRNA, and RNaseP) were performed. The results presented in this paper demonstrate that SARNA-Predict-pk can out-perform other state-of-the-art algorithms in terms of prediction accuracy.

RNA is central in several stages of protein synthesis, and also has structural, functional, and regulatory roles in the cell. The shape of organic molecules such as RNA largely determines their function within an organic system, thus methods for the computational prediction of structure are sought after. In the ab initio case where only the RNA sequence is known, the currently dominant structure prediction techniques employ minimization of the free energy of a given RNA molecule via a thermodynamic model. However, the minimum free energy structure is rarely the native structure; this is thought to be due to errors in the thermodynamic model parameters, which are experimentally determined. Cluster analysis performed by [6] on a sampling of structures from a Boltzmann weighted ensemble determined that the best cluster centroid had an improved sensitivity and significantly improved positive predictive value over the minimum free energy structure in the ensemble. Based on this result, we investigated the combination of an existing evolutionary algorithm for RNA secondary structure prediction with a clustering algorithm.

Among the most powerful and commonly used methods for finding new members of non-coding RNA gene families in genomic data are covariance models. The parameters of these models are estimated from the observed position-specific frequencies of insertions, deletions, and mutations in a multiple alignment of known non-coding RNA family members. Since the vast majority of positions in the multiple alignment have no observed changes, yet there is no reason to rule them out, some form of prior is applied to the estimate. Currently, observed-frequency priors are generated from non-family members based on model node type and child node type allowing for some differentiation between priors for loops versus helices and between internal segments of structures and edges of structures. In this work it is shown that parameter estimates might be improved when thermodynamic data is combined with the consensus structure/sequence and observed-frequency priors to create more realistic position-specific priors.

Ribonucleic acid, a single stranded linear molecule, is essential to all biological systems. Different regions of the same RNA strand will fold together via base pair interactions to make intricate secondary and tertiary structures that guide crucial homeostatic processes in living organisms. Since the structure of RNA molecules is key to their function, algorithms for the prediction of RNA structure are of great value. This paper discusses significant improvements made to SARNA-Predict, an RNA secondary structure prediction algorithm based on Simulated Annealing (SA). One major improvement is the incorporation of a sophisticated thermodynamic model (efn2). This model is used by mfold to rank sub-optimal structures, but cannot be used directly by mfold during the structure prediction. Experiments on eight individual known structures from four RNA classes (5S rRNA, Group I intron 23S rRNA, Group I intron 16S rRNA and 16S rRNA) were performed. The data demonstrate the robustness and the effectiveness of our improved prediction algorithm. The new algorithm shows results which surpass the dynamic programming algorithm mfold in terms of prediction accuracy on all tested structures.

The function of an RNA molecule is primarily established by its physical shape. As current physical structure determination methods are time consuming and expensive, there is great interest in finding computational structure prediction methods. P-RnaPredict is a parallel evolutionary algorithm for RNA secondary structure prediction. Two sets of experiments are performed on 5 known structures from 3 RNA classes (5S rRNA, Group I intron 16S rRNA, and 16S rRNA). The first determines the actual speedup, and the second evaluates the performance of P-RnaPredict through comparison to mfold. P-RnaPredict succeeds in predicting structures with higher true positive base pair counts and lower false positives than mfold on specific sequences.

In order for structure prediction researchers to better understand the results of their algorithms and to enable life science researchers to interpret RNA structure easily, it is helpful to provide them with a flexible and powerful tool for RNA secondary structure visualization. jViz.Rna is a multi-platform visualization tool capable of displaying RNA secondary structures encoded in a variety of file formats. A single structure can be shown using the linear Feynman, circular Feynman, dot plot, and classical structure visualization models. The resulting drawings are dynamic and can easily be further modified by the user. Any of the drawings produced can be saved to disk enabling easy dissemination. The unique usage of a spring model for classical structure drawing allows for clear visualization of pseudoknots with minimal overlaps. The addition of a locality tool allows for the isolation of pseudoknotted regions or other regions of interest. Availability: http://jviz.research.iat.sfu.ca

This paper presents a comparison of two types of algorithms for RNA secondary structure prediction: an implementation of Nussinov's dynamic programming algorithm (DPA), and P-RnaPredict, a parallel evolutionary algorithm (EA). The research presented here builds on previous work and examines the results from tests of three RNA sequences that are 118, 543, and 784 nucleotides in length. A variety of EA parameter settings were employed based on previous experimentation. Predicted structures were compared to those generated by the Nussinov DPA and to known structures to determine relative accuracy. Results indicate that the EA demonstrated high prediction accuracy and outperformed the Nussinov DPA on all tested sequences

This paper presents a fully parallel version of RnaPredict, a genetic algorithm (GA) for RNA secondary structure prediction. The research presented here builds on previous work and examines the impact of three different pseudorandom number generators (PRNGs) on the GA's performance. The three generators tested are the C standard library PRNG RAND, a parallelized multiplicative congruential generator (MCG), and a parallelized Mersenne Twister (MT). A fully parallel version of RnaPredict using the Message Passing Interface (MPI) was implemented on a 128-node Beowulf cluster. The PRNG comparison tests were performed with known structures whose sequences are 118, 122, 468, 543, and 556 nucleotides in length. The effects of the PRNGs are investigated and the predicted structures are compared to known structures. Results indicate that P-RnaPredict demonstrated good prediction accuracy, particularly so for shorter sequences.

This work builds on previous research from an EA used to predict secondary structure of RNA molecules. The EA has the goal of predicting which canonical base pairs will form hydrogen bonds and helices. The addition of stacking energies, through INN and INN-HB, to our thermodynamic model has enhanced our predictions. We test three RNA sequences of lengths 118, 543, and 784 nucleotides using a variety of previously successful operators and parameter settings. The accuracy of the predicted structures are compared against those generated by the Nussinov DPA and also to known structures. The EA showed high accuracy of prediction especially on short sequences. On all tested sequences, the EA outperforms the Nussinov DPA.

This paper presents a new coarse-grained distributed genetic algorithm (GA) for the prediction of the secondary structure of RNA molecules, based largely on a serial permutation-based GA. The benefits of the distributed GA over our existing serial GA are analyzed and demonstrated. We also analyze the impact of the keep-best reproduction (KBR) and roulette wheel selection (STDS) GA replacement techniques. Finally, we verify the increase in convergence speed of our distributed GA. Tests was performed on 241 and 785 nucleotide sequences. Overall, the distributed GA is found to improve upon the serial GA performances, with a much more pronounced impact on the STDS selection strategy. There is also a notable acceleration in convergence speed.

RNA is an important molecule as it serves a key role in the translation from the genetic information encoded in DNA in protein synthesis. Computational techniques for RNA folding suffer from combinatorial explosion. In this paper, a genetic algorithm (GA) will be used to attempt to solve the secondary structure prediction of RNA molecules.

The basic function of a biomolecule is determined by its 3 dimensional shape, otherwise known as the tertiary structure. However, existing empirical methods to determine this shape are too costly and lengthy to be practical. RNA is of interest as a biomolecule because it is central in several stages of protein synthesis. Also, its secondary structure dominates its tertiary structure. In our model, RNA secondary structure develops as a consequence of bonds which form between specific pairs of nucleotides known as the canonical base pairs. Searching a sequence of nucleotides for all possible base pairs is rapid and straightforward; the challenge comes from attempting to predict which specific canonical base pairs will form bonds in the real structure. Various algorithms have been used for RNA structure prediction such as dynamic programming, and comparative methods [1] and stochastic methods such as genetic algorithms (GA).

This paper presents a Genetic Algorithm (GA) to predict the secondary structure of RNA molecules, where the secondary structure is encoded as a permutation. More specifically, the proposed algorithm predicts which specific canonical base pairs will form hydrogen bonds and build helices, also known as stems. Since RNA is involved in both transcription and translation and also has catalytic and structural roles in the cell, determining the structure of RNA is of fundamental importance in helping to determine RNA function. We introduce a GA where a permutation is used to encode the secondary structure of RNA molecules. We discuss results on RNA sequences of lengths 76, 210, 681, and 785 nucleotides and present several improvements to our algorithm. We show that the Keep-Best Reproduction operator has similar benefits as in the traveling salesman problem domain. In addition, a comparison of several crossover operators is provided. We also compare the results of the permutation-based GA with a binary GA, demonstrating the benefits of the newly proposed representation.

This paper presents a genetic algorithm (GA) to predict the secondary structure of RNA molecules, where the secondary structure is encoded as a permutation. More specifically the proposed algorithm predicts which specific canonical base pairs will form hydrogen bonds and build helices, also known as stem loops. Since RNA is involved in both transcription and translation and also has catalytic and structural roles in the cell, knowing its structure is of fundamental importance since it will determine the function of the RNA molecule. We discuss results on RNA sequences of lengths 76, 681, and 785 nucleotides and present several improvements to our algorithm. We show that the Keep-Best Reproduction operator has similar benefits as in the TSP domain. In addition, a comparison of several crossover operators is provided, demonstrating that CX, an operator that is marginal in the TSP domain, performs very well in the RNA folding domain.