## 7 Tree Comparison and Related Problems
### Tree Alignment under a Generalized Edit Model
In Section 6.4, we have approached the problem of RNA structural alignment using structure-annotated sequences. Since the structures are already known when we assume structure annotated sequences as our inputs, we could as well represent the structures directly as trees (which also include the sequence information at their leaves). For our example, we use the tree representation underlying the tool RNAforester [39]. There, the nodes labeled \(P\) indicate hydrogen bonds between base pairs: \(P(\mathtt{G},\mathtt{A},\mathtt{U},\mathtt{C})\) indicates that bases \(\mathtt{G}\) and \(\mathtt{C}\) form a hydrogen-bonded base pair, while \(\mathtt{A},\mathtt{U}\) constitute the hairpin loop. Figure 12 shows an example. Therefore, the right- and leftmost sibling of a \(P\)-node must always be a base, and not another \(P\)-node. The chosen representation is captured by the following satellite signature:  
Satellite signature \(RST\) with \begin{tabular}{l l l l l l}
**alphabet** & \(\{\mathtt{A},\mathtt{C},\mathtt{G},\mathtt{U}\}\) \\ \multicolumn{2}{l}{**operators**} \\ \(P\) & : & \(Rst\) & \(\rightarrow\) & \(Rst\) & - must have a subforest of at least two bases \\ \(\sim\) & : & \(Rst\times Rst\) & \(\rightarrow\) & \(Rst\) & - subforest concatenation \\ \(\varepsilon\) & : & & \(\rightarrow\) & \(Rst\) & - empty subforest \\ \end{tabular}   
Alignments of _RST_ trees under the atomic edit model clutter the search space with candidates that have no reasonable interpretation. For example, they allow to align a \(P\) node to a base node, or insert a \(P\) node without the two bases that make the bond. Such alignments are meaningless in this context. Replacement of \(P\) by an \(a\) must be avoided, and overall, \(P(a,...,b)\) should be treated as a unit, and so on. With generalized edit operations, we can define exactly the meaningful edit operations in this scenario:  
\[ \begin{array}{rcll}a&\leftrightarrow&b&\text{-- base match}\\ a&\leftrightarrow&\varepsilon&\text{-- base indel}\\ P(a{\sim}X{\sim}b)&\leftrightarrow&P(c{\sim}X{\sim}d)&\text{-- base pair match}\\ P(a{\sim}X{\sim}b)&\leftrightarrow&c{\sim}X{\sim}d&\text{-- bond indel}\\ P(a{\sim}X{\sim}b)&\leftrightarrow&X&\text{-- base pair indel}\\ P(a{\sim}X{\sim}b)&\leftrightarrow&c{\sim}X&\text{-- paired base loss\_intro right}\\ P(a{\sim}X{\sim}b)&\leftrightarrow&X{\sim}d&\text{-- pair base loss\_intro left}\\ X{\sim}Y&\leftrightarrow&X{\sim}Y&\text{-- no change}\end{array} \]  
for \(a,b,c,d\in\mathcal{R}\) where applicable. These general edit operations ensure that editing always leads from a legal RNA structure representation to another. To create the ICORE according to Definition 6 for tree alignments under this edit model, we can almost re-use the core signature _STRAL_ of Subsection 6.4. The overall representation has changed a bit, as we have gone from sequences to trees. This also affects the structure of their alignments. With _STRAL_, a base match also contains a sub-alignment of the sub-sequences following the matched bases. With _RST_ trees, all bases reside on leaves of the trees, and sub-alignments are connected by forest concatenation instead. We design our new core signature _STRAL2_ following _STRAL_, keeping the names for analog operations, but adjusting the types. The edit operations for base match and base pair match are symmetric, and in _STRAL2_, they give rise to a single operator each: b_match and pair. The \"no change\" rule is also symmmtric and gives rise to a single operator called \(\sim\). The resulting ICORE RNATreeAli is shown on page 127. While RNATreeAli only reformulates StructAli based on a tree representation, we can use the more general concept of tree edit operations to enrich our edit model by specific cases of interest. We give one more example. Figure 12: Structure representation where a \(P\)-node indicates a base pair bond between its left- and rightmost child, while the other subtrees represent structures enclosed by this base pair.