RNAalifold: improved consensus structure prediction for RNA alignments.

Bernhart SH, Hofacker IL, Will S, Gruber AR, Stadler PF. · 2008

Read RNAalifold: improved consensus structure prediction for RNA alignments. by Bernhart SH, Hofacker IL, Will S, Gruber AR, Stadler PF. (2008) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/europmc-pmc2621365.txt.

Introduction

Bernhart, Hofacker, Will, Gruber, and Stadler released an improved RNAalifold in 2008. The program is widely used. It predicts the shared folded shape of a set of related RNA molecules. RNA folds into structures that determine its function, and comparing sequences helps pin the true fold. Users and rival methods had exposed weaknesses in the original tool's handling of gaps and scoring.

The new version treats alignment gaps in a more rational way. It also replaces the simple covariance scoring with RIBOSUM-like matrices. Those matrices weight likely base-pair exchanges. Accuracy improved substantially without slowing the program down. On several test data sets the updated tool beat not only its predecessor but also competing approaches based on grammars, expected accuracy, and classifiers. The authors say it can replace the old version for almost any application.

Catalog record

CREATORBernhart SH, Hofacker IL, Will S, Gruber AR, Stadler PF.
YEAR2008
COLLECTIONPAPERS
FORMATTXT
FILE SIZE41 KB
LICENSECC BY 4.0
RIGHTSCC BY
SOURCEEurope PMC

Source: https://europepmc.org/articles/PMC2621365

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

RNAalifold: improved consensus structure prediction for RNA alignments By Stephan H Bernhart, Ivo L Hofacker, Sebastian Will, Andreas R Gruber, Peter F Stadler Published in: BMC Bioinformatics DOI: 10.1186/1471-2105-9-474 ABSTRACT Background The prediction of a consensus structure for a set of related RNAs is an important first step for subsequent analyses. RNAalifold, which computes the minimum energy structure that is simultaneously formed by a set of aligned sequences, is one of the oldest and most widely used tools for this task. In recent years, several alternative approaches have been advocated, pointing to several shortcomings of the original RNAalifold approach. Results We show that the accuracy of RNAalifold predictions can be improved substantially by introducing a different, more rational handling of alignment gaps, and by replacing the rather simplistic model of covariance scoring with more sophisticated RIBOSUM-like scoring matrices. These improvements are achieved without compromising the computational efficiency of the algorithm. We show here that the new version of RNAalifold not only outperforms the old one, but also several other tools recently developed, on different datasets. Conclusion The new version of RNAalifold not only can replace the old one for almost any application but it is also competitive with other approaches including those based on SCFGs, maximum expected accuracy, or hierarchical nearest neighbor classifiers. BACKGROUND Unbiased surveys of the transcriptomes of higher eukaryotes by multiple techniques ranging from tiling arrays and short-read sequencing to large-scale sequencing of full-length cDNAs have dramatically changed our perception of genome organization: At least 90% of the mammalian genomes are transcribed, the vast majority of this transcription is non-protein-coding, and there is mounting evidence that a significant fraction of the non-coding transcripts are functional [1,2]. The investigation of non-coding RNAs has thus developed into a focal topic in molecular biology and bioinformatics alike. Most of the ancient house-keeping RNAs (tRNAs, rRNAs, snRNAs, snoRNAs) and many of the newly discovered regulatory RNAs, including microRNA precursors, form evolutionarily well-conserved secondary structures, reviewed e.g. in [3]. These structures are tightly linked to the molecules' functions. It is therefore a core task in RNA bioinformatics to compute in particular the consensus structures of evolutionarily conserved RNAs. It has long been known that the accuracy of thermodynamic structure predictions for individual sequences is rather limited. On the other hand, computing the consensus structure common to several related RNA sequences can drastically improve the prediction [4]. The conceptually most elegant approach towards consensus structure prediction is to solve the alignment and the structure prediction problem simultaneously. The Sankoff algorithm [5] provides a solution that is practically applicable and has been implemented in various variants including dynalign [6], stemloc [7], foldalign [8], LocARNA [9] or consan [10]. Still, these approaches are computationally too expensive for large-scale routine applications. One basic alternative is to first compute structures for the individual sequences and then to align these sequences taking into account the structural information. This can be achieved in different ways using sequence-based (e.g. stral [11]), tree-based [12,13], or Sankoff-style alignment algorithms [14]. Alignment-free approaches include RNAspa [15] and consensus shapes [16]. A large group of methods pre-supposes a (sequence) alignment. Most methods of this type use the alignment to super-impose predicted structures to global [17,18] or local structures [19]. RNAalifold [4], on the other hand, in essence averages the contributions of the standard Turner energy model [20] according to a given alignment A and then solves the thermodynamic folding problem w.r.t. these averaged energies. A special case is the ConStruct package [21], which besides acting as a front-end for several prediction tools provides an interface for changing RNA alignments using expert knowledge. METHODS Original RNAalifold The original RNAalifold approach combines a thermodynamic energy minimization [22] with a simple scoring model to assess evolutionary conservation. Both an energy minimization and a partition function version are implemented in the Vienna RNA package [4]. Energy minimization uses the following recursions: Fi,j=min⁡(Fi+1,j,min⁡i<k≤jCi,k+Fk+1,j)Ci,j=βγ(i,j)++min⁡{∑α∈Aℌ(i,j,α)min⁡i<k<l<j(∑α∈AJ(ij,kl,α)+Ck,l)min⁡i<k<j(Mi,k+Mk+1,j1+a)Mi,j=min⁡{Mi+1,j+cmin⁡i<k<jCi,k+Mk+1,j+bMi,j1Mi,j1=min⁡(Mi,j−11+c,Ci,k) As in single-sequence folding, the arrays F ij , C ij , M ij , and Mij1 hold, for every sub-sequence from i to j, the energies of the optimal folds of unconstrained structures, of structures enclosed by (i, j) base pairs, of multi-loop components, and of multi-loop components with a single branch, respectively [23]. The Turner energy parameters for hairpin loops delimited by alignment positions i and j in sequence α ∈ A are denoted by ℌ(i, j, α); similarly ℑ(ij, kl, α) encodes the energies of interior loops including stacked base pairs. Multi-loops are modeled by a linear model with a "closing" contribution a, and contribution b and c for each branch and unpaired position, respectively. Note that these values are the tabulated single-sequence parameters multiplied by the number N = |A| of aligned sequences, since the recursion above computes the sum of the folding energies. RNAalifold modifies the energy model by introducing a (base pair) conservation score γ(i, j) that evaluates the corresponding alignment columns w.r.t. evidence for base pairing. In [4], we used (1)γ′(i,j)=12∑α,β∈Aα≠β{h(αi,βi)+h(αj,βj)if (αi,αj)∈ℬ∧(βi,βj)∈ℬ0otherwise where the Hamming distance h(a, b) = 0 if a = b and h(a, b) = 1 if a ≠ b and ℬ = {AU, UA, CG, GC, GU, UG} is the set of possible base pairs. The full covariation score γ also includes penalties for sequences in which the (i, j) base pair cannot be realized: (2)γ(i,j)=γ′(i,j)+δ∑α∈A{0 if (αiαj)∈ℬ0.25 if αi∧αj are gaps1 otherwise Potentially paired columns, in which less than a user-defined number or fraction of sequences can form the pair, are considered to be forbidden. RNAalifold therefore predicts the structure common to most of the sequences in an alignment. A prediction for a single molecule that is consistent with the consensus structure can be obtained by using the result of RNAalifold as a constraint for single molecule folding. Both mfold [22] and RNAfold [24] can be used for this purpose. The purpose of this contribution is to explore several avenues for improving the performance of RNAalifold. Intuitively, there are two leverage points: (1) the details of the energy evaluations in the presence of gaps, and (2) the rather ad hoc covariance bonuses and penalties. Improved Energy Evaluation The 2002 implementation of RNAalifold uses a very simplistic way of treating gaps in order to save computational resources: gaps within unpaired regions are simply ignored, because then only alignment positions appear as indices and loop sizes, for instance, do not need to be evaluated separately for every sequence. This can, however, distort the energetics in particular if there are many gaps, and in extreme cases can lead to the inclusion of unrealistically short hairpins, see Figure 1. A second source of error is that gaps do not contribute to the dangling end energies in this setting. [Figure: Possible results of treating gaps as bases. The consensus structure of the alignment in the middle is predicted once with gaps treated as if they were bases (old), and once by removing them before computing the energies (new). The predicted structures (highlighted in red) are shown to the left. As can be seen in 1, sequence 1 can form a perfect hairpin. In 2, the sterically impossible hairpin for the other two sequences is shown. Two of the three sequences cannot form the predicted structure. On the other hand,

Read the complete text