## 6 ICOREs for RNA Secondary Structure Analysis
### Sequence-to-Structure Alignment and RNA Family Modeling
#### 6.6.4 A Structural Matcher for Exact Search  
For sake of clarity, we first head for the hard-coded version of the simple ICORE S2 SExact, that contains only four rules, \((\gamma_{1})-(\gamma_{4})\). The goal is to construct a grammar that restricts the search space to all and only the core terms that rewrite to \(r\) on the first satellite. Given this grammar, there will no longer be a need to rewrite a core term to \(r\), and hence we will be able to eliminate altogether the first satellite and the rewrite rules that produce it. We start from the grammar StructAli, and ignore all rules that deal with deletions and insertions, as we are heading for an exact matcher. This leaves us with four rules, which reduce to three after \"inlining\" the nonterminal symbol \(P\) for simplification. The grammar now is simply  
\[S\ \ \rightarrow\ \ \mathtt{single}(a,c,S)\mid\mathtt{split}(\mathtt{pair}(a,c,S, b,d),S)\mid\mathtt{mty}\]  
As \(r\) has 9 residues, we create 10 copies of this grammar, which use 10 non-terminal symbols, indexed by the positions in \(r\). This gives the grammar template  
\[S_{i}\ \ \rightarrow\ \ \mathtt{single}(a,c,S_{i+1})\mid\mathtt{split}( \mathtt{pair}(a,c,S_{i+1},b,d),S_{j+1})\mid\mathtt{mty}\]  
where \(j\) is determined as the position of the closing base partner of position \(i\). Now we specialize this grammar template to retain productions that can be applied in a successful derivation of residue \(i\) in \(r\), and then drop whatever refers to the first satellite input. For each symbol \(\bullet_{a}^{i}\) in \(r\), we have a production  
\[S_{i}\rightarrow\mathtt{single}(a,c,S_{i+1})\]  
and for each pair of matching brackets \(\varsigma_{a}^{i}\) and \(>_{b}^{j}\) in \(r\), we have a production  
\[S_{i}\rightarrow\mathtt{split}(\mathtt{pair}(a,c,S_{i+1},b,d),S_{j+1})\]  
This leads to the grammar and ICORE named Match_S2S_r for the sequence-to-structure alignment problem with target \(r\), that is displayed on page 103. For clarity, we have added the position of each character in \(r\) in a superscript in the grammar.  
_Algorithms_2014, 7_
```
1 CORE Match_S2S_R: dimension 1 -- for R =
```
Satellite signature RNA  
Core signature STRAL  
Grammar Match_S2S_R  
\[S_{1}^{*} \rightarrow \text{split}(\text{pair}(\mathbb{A}^{1},c,S_{2},\mathbb{U}^{6},d),S_{7})\] \[S_{2} \rightarrow \text{split}(\text{pair}(\mathbb{G}^{2},c,S_{3},\mathbb  
**Example 9**.: With ICORE Match_S2S_r, we find that there is some core term \(t\) such that  
\[t\rightarrow^{*}\textbf{ \"GGUCUCAUG\"}\]  
while there is no core term \(t^{\prime}\) such that  
\[t^{\prime}\rightarrow^{*}\textbf{ \"AGUCUCAUG\"}\]  
The core terms generated by the grammar of Match_S2S_r contain all the sequence information about the target structure, and so, a core signature algebra can implement position and sequence specific scoring. If no scoring depending on the sequence content of the internalized target is desired, the ICORE can be simplified by not reproducing the residues of the target. The core signature simplifies from _STRAL_ to _STR_, and we obtain an new ICORE, Match_S2S_r' presented on page 104. In this simplified form, this ICORE is the same as RNAFold (page 93), except for the grammar. Naturally-all we do is predicting a structure for a plain RNA sequence, restricted to match the target. This ICORE, without the provision for target specific scoring, could also have been derived from RNAFold directly.