## 6 ICOREs for RNA Secondary Structure Analysis
### RNA Folding  
Our first RNA-related ICORE is a version of the classical Nussinov algorithm which, given a single RNA sequence, predicts its secondary structure by maximizing the number of base pairs [22]. This problem is of dimension 1. The input is a plain sequence represented as a string from the satellite signature _RNA_, and the output is a secondary structure. We need a core signature _STR_ to describe such secondary structures. For that, we use four operators. Operator mty represents the empty structure, pair takes as input two letters and a substructure and builds a base pair around the latter, single takes as input one letter and adds it as an unpaired base to a structure, and split is for the concatenation of two structures, used when a structure branches as in Figure 4.  
**Example 4**. : Figure 6 shows a core term for the plain sequence \"ACGACGAUCUU\". This core term represents the secondary structure displayed in Figure 4.  
The grammar SecStr (see below) guarantees that this representation is unique. It uses a production of tree height 2 to make sure that core terms uniquely represent secondary structures, disallowing core terms such as split\((\texttt{mty},\texttt{mty})\) Grammar SecStr does not impose a restriction on the two bases in pair\((a,S,b)\), so the structure terms may also represent structures with non-standard base pairs. For the RNA folding problem, legal base pairing is enforced in the rules, where basep is a syntactic predicate defining legal base pairs. The standard definition is  
\[\texttt{basep}(a,b) = \{(a,b)\in\{(\texttt{A},\texttt{U}),(\texttt{U},\texttt{A}),( \texttt{C},\texttt{G}),(\texttt{G},\texttt{C}),(\texttt{G},\texttt{U}),(\texttt{ U},\texttt{G})\}\]  
to allow for canonical base pairs (Watson-Crick or wobble base pairs). By setting  
\[\texttt{basep}(a,b) = \texttt{TRUE}\]  
we would allow also non-canonical pairs and let the scoring makes the difference. This is commonly done in stochastic RNA family models, where non-standard base pairs are allowed with low probability. Figure 6: Core term for secondary structure of Figure 4.  
The rewrite rules explain how to build the secondary RNA structure from the plain sequence: either by creating a base pair with pair, or by adding a single base with single, or by concatenating two structures with split. Completed with some algebras, the resulting ICORE RNAfold is displayed on page 93. We propose three algebras with ICORE RNAfold:  
* Algebra BPmax implements base pair maximization as our objective function, as it is done in the Nussinov algorithm. * Algebra DotPar serves to visualize predicted structures as strings in a dot-bracket notation. Used by itself in a call to RNAfold\((\textsc{DotPar},s)\), this algebra would enumerate the full candidate space for input \(s\). Normally, it is used in a product with other algebras (cf. Section 8), where it reports optimal candidates. * Algebra Prob assigns a probability score to each core term, such as it is done with _stochastic context free grammars_[20; 23; 24]. Algebra Prob deserves more comments. Stochastic context free grammars (SCFGs) allow to parse a string into (context free) structures of any kind, and a stochastic scoring scheme allows us to select the most likely parse for it, or to compute the probability sum over all parses. The parameters \(\pi_{a}\), \(\pi_{ab}\), and \(\pi_{split}\) reflect the probability of encountering an unpaired base \(a\), a base pair \((a,b)\), and a structural split; they must be estimated from a set of training data. More sophisticated SCFGs will replace the grammar SecStr by a more refined grammar, leading to a larger number of parameters, but in principle, nothing else changes. Calling RNAfold with algebra \(Prob\) an input sequence \(s\) and \(\phi=\max\), we can find the most likely parse of sequence \(s\), which indicates a structure of high likelihood.