Dataset Information

Improving the accuracy of predicting secondary structure for aligned RNA sequences.

ABSTRACT: Considerable attention has been focused on predicting the secondary structure for aligned RNA sequences since it is useful not only for improving the limiting accuracy of conventional secondary structure prediction but also for finding non-coding RNAs in genomic sequences. Although there exist many algorithms of predicting secondary structure for aligned RNA sequences, further improvement of the accuracy is still awaited. In this article, toward improving the accuracy, a theoretical classification of state-of-the-art algorithms of predicting secondary structure for aligned RNA sequences is presented. The classification is based on the viewpoint of maximum expected accuracy (MEA), which has been successfully applied in various problems in bioinformatics. The classification reveals several disadvantages of the current algorithms but we propose an improvement of a previously introduced algorithm (CentroidAlifold). Finally, computational experiments strongly support the theoretical classification and indicate that the improved CentroidAlifold substantially outperforms other algorithms.

SUBMITTER: Hamada M

PROVIDER: S-EPMC3025558 | biostudies-literature | 2011 Jan

REPOSITORIES: biostudies-literature

ACCESS DATA

Publications

Improving the accuracy of predicting secondary structure for aligned RNA sequences.

Hamada Michiaki M Sato Kengo K Asai Kiyoshi K

Nucleic acids research 20100915 2

Considerable attention has been focused on predicting the secondary structure for aligned RNA sequences since it is useful not only for improving the limiting accuracy of conventional secondary structure prediction but also for finding non-coding RNAs in genomic sequences. Although there exist many algorithms of predicting secondary structure for aligned RNA sequences, further improvement of the accuracy is still awaited. In this article, toward improving the accuracy, a theoretical classificati ...[more]

PMID: 20843778

Similar Datasets

Project description:BACKGROUND: Since RNA molecules regulate genes and control alternative splicing by allostery, it is important to develop algorithms to predict RNA conformational switches. Some tools, such as paRNAss, RNAshapes and RNAbor, can be used to predict potential conformational switches; nevertheless, no existent tool can detect general (i.e., not family specific) entire riboswitches (both aptamer and expression platform) with accuracy. Thus, the development of additional algorithms to detect conformational switches seems important, especially since the difference in free energy between the two metastable secondary structures may be as large as 15-20 kcal/mol. It has recently emerged that RNA secondary structure can be more accurately predicted by computing the maximum expected accuracy (MEA) structure, rather than the minimum free energy (MFE) structure. RESULTS: Given an arbitrary RNA secondary structure S? for an RNA nucleotide sequence a = a?,..., a(n), we say that another secondary structure S of a is a k-neighbor of S?, if the base pair distance between S? and S is k. In this paper, we prove that the Boltzmann probability of all k-neighbors of the minimum free energy structure S? can be approximated with accuracy ? and confidence 1 - p, simultaneously for all 0 ? k < K, by a relative frequency count over N sampled structures, provided that N>N(?,p,K)=??¹(p/2K)²/4?², where ?(z) is the cumulative distribution function (CDF) for the standard normal distribution. We go on to describe the algorithm RNAborMEA, which for an arbitrary initial structure S? and for all values 0 ? k < K, computes the secondary structure MEA(k), having maximum expected accuracy over all k-neighbors of S?. Computation time is O(n³ · K²), and memory requirements are O(n² · K). We analyze a sample TPP riboswitch, and apply our algorithm to the class of purine riboswitches. CONCLUSIONS: The approximation of RNAbor by sampling, with rigorous bound on accuracy, together with the computation of maximum expected accuracy k-neighbors by RNAborMEA, provide additional tools toward conformational switch detection. Results from RNAborMEA are quite distinct from other tools, such as RNAbor, RNAshapes and paRNAss, hence may provide orthogonal information when looking for suboptimal structures or conformational switches. Source code for RNAborMEA can be downloaded from http://sourceforge.net/projects/rnabormea/ or http://bioinformatics.bc.edu/clotelab/RNAborMEA/.

Dataset Information

Improving the accuracy of predicting secondary structure for aligned RNA sequences.

Publications

Improving the accuracy of predicting secondary structure for aligned RNA sequences.

Similar Datasets

OmicsDI is part of the ELIXIR infrastructure

Tweets