## 6 ICOREs for RNA Secondary Structure Analysis
### Structural Alignment
#### 6.4.1 Core Signature and Grammar for Structural Alignment  
A core signature for structural alignments must be elaborate enough to accommodate all these and similar situations, to allow for their independent scoring. We consider here the most general set of edit operations, such as introduced in [26], that is used with arc-annotated sequences and that allows for any kind of mutational event. Edit operations representing structural matches between single bases or base-pairings are mty, single, split, and pair. We re-use the names from signature _STR_, but note that single and pair now hold bases from both sequences as their arguments. For mismatches, we need edit operations for deletion and insertion of unpaired residues: del and ins, which both have exactly the same semantics as in sequence alignment (Section 5). We must also allow that a base pair in one sequence may be not present in the other sequence, because one or both bases are missing or because the pair cannot be formed, as dictated by predicate basep. These cases give rise to eight new operations, pair_ins, pair_del, pairL_ins, pairL_del, pairR_ins, pairR_del, pairLR_ins, pairLR_del. Therefore, we have a total of 12 edit operations (This does not account for mty and split, as in the standard model. An edit operation where the left or right part of a split has been lost might well be useful. It has been overlooked in the edit model of [26], probably because the graphical representation of structures as arc-annotated sequences has no explicit representation for structural branching. ), which are summarized graphically in Figure 5. Collecting the above cases, we arrive at a core signature _STRAL_ with 14 operators. In the definition of _STRAL_, \(\mathcal{R}\) denotes the RNA alphabet \(\{\texttt{A},\texttt{C},\texttt{G},\texttt{U}\}\), and _StrAli_ is the (only) sort of terms from the core signature. Akin to grammar SecStr, the grammar for structural alignment, StructAli, should avoid ambiguous structure representations, and does so by using an extra non-terminal symbol \(P\). The ICORE is presented on page 5.1. **Example 5**. : Consider the following structural alignment, presented in dot-bracket notation. \[ \begin{array}{cccc}\texttt{(. - - ) ( )}&\texttt{A}&\texttt{G}&\texttt{-}&\texttt{U}&\texttt{C}& \texttt{G}\\ \texttt{|}&\texttt{|}&&\texttt{|}&&\texttt{|}&&\texttt{|}\\ \texttt{A}&\texttt{G}&\texttt{C}&\texttt{C}&\texttt{U}&\texttt{C}&\texttt{A}\\ \texttt{( ( ).. ).... }&\texttt{}\texttt{}\texttt{}\texttt{}\texttt{}\texttt{}\texttt{}\texttt{} \texttt{}\texttt{}\texttt{}\texttt{}\texttt{}\texttt{}\texttt{}\texttt{}\texttt{}}& \texttt{}\texttt{}\texttt{}\texttt{}\texttt{}\texttt{}\texttt{}\end{array} \]  
It is encoded by the core term  
\(c=\texttt{split}(\texttt{pair}(\texttt{A},\texttt{A},\texttt{split}( \texttt{pairL}_{\texttt{ins}}(\texttt{G},\texttt{G},\texttt{mty},\texttt{C}), \texttt{ins}(\texttt{C},\texttt{mty})),\texttt{U},\texttt{U}),\texttt{pairLR}_{ \texttt{del}}(\texttt{C},\texttt{C},\texttt{mty},\texttt{G},\texttt{A})\)  
Figure 7: Example of a structural RNA alignment. Vertical bars indicate matching bases in the sequences. Note that the two structures are different, but similar.