## 7 Tree Comparison and Related Problems
### Tree Alignment
#### 7.2.2 Tree Alignment with Affine Gap Scoring
In trees representing RNA secondary structure, any gap on the primary sequence that is consistent with the secondary structure (i.e., the gap does not break any base pair) is a complete subforest gap in the tree. Such gaps are implemented in [36; 37; 38]. Compared to CompleteSubtree, the grammar CompleteSubforest needs two additional symbols: E (sibling deletion) and J (sibling insertion). **Example 14**. : Consider the two trees \(a(b\!\!\sim\!\!c(d)\!\!\sim\!\!e\!\sim\!\!f)\) and \(a(b\!\!\sim\!\!f)\). In the complete subtree gap mode, the alignment requires two gaps:  
\[t_{1}=\texttt{rep}(a,a,\texttt{rep}(b,b,\texttt{mty})\!\!\sim\!\!\texttt{ open\_del}(c,\texttt{del}(d,\texttt{mty}))\!\!\sim\!\!\texttt{open\_del}(e, \texttt{mty})\!\!\sim\!\!\texttt{rep}(f,f,\texttt{mty}))\!\!\sim\!\!\texttt{mty}\]  
In the complete subforest mode, it requires only one gap:  
\[t_{2}=\texttt{rep}(a,a,\texttt{rep}(b,b,\texttt{mty})\!\!\sim\!\!\texttt{ open\_del}(c,\texttt{del}(d,\texttt{mty}))\!\!\sim\!\!\texttt{del}(e,\texttt{mty}) \!\!\sim\!\!\texttt{rep}(f,f,\texttt{mty}))\!\!\sim\!\!\texttt{mty}\]  
The alignment \(t_{1}\) is also in the search space of CompleteSubforest, where it competes with the alignment \(t_{2}\) which uses only one deletion opening. Conversely, the grammar of CompleteSubtree does not allow to generate \(t_{2}\), and therefore, \(t_{2}\) is not in the search space of CompleteSubtree. Gaps as subtrees.The two preceding definitions of gaps do not allow to continue an alignment with a replacement in a subtree below a number of insertions and deletions. This can be fixed by considering arbitrary subtrees instead of complete subtrees (and arbitrary subforest instead of complete subforest, see later). With subtree gaps, a gap node is the extension of a larger gap because its ancestor is a gap node, like for complete subtrees. The difference is that a gap is not required to cover the complete subtree. This definition of a gap is used in [35]. In order to continue with insertions below deletions, and then with replacements further below, the grammar Subtree provides direct transitions between D and I with gaps opened in the other tree. Returning to our previous example of trees \(a(b(c{\sim}f))\) and \(a(d(e{\sim}f))\), we can now align the two nodes labeled \(f\) after deletion/insertion of \(b\) and \(d\). The grammar allows us to derive the core term  
\[t=\texttt{rep}(a,a,t_{1}){\sim}\texttt{mty}\]  
\[t_{1}=\texttt{open\_del}(b,\texttt{del}(c,\texttt{mty}){\sim}t_{2}){\sim} \texttt{mty}\]  
\[t_{2}=\texttt{open\_ins}(d,\texttt{ins}(e,\texttt{mty}){\sim}\texttt{rep}(f,f, \texttt{mty}){\sim}\texttt{mty}){\sim}\texttt{mty}\]  
In contrast to the previous situation, sub-alignment \(t_{2}\) is now embedded in \(t_{1}\). Gaps as subforests.This is our most general definition for a gap. A gap node can extend both an ancestor gap node or a sibling gap node, like with complete subforests, and a gap can stop anywhere in the tree, like with arbitrary subtrees. This definition is implemented in [PERSON]'s algorithm [39]. Consider the two trees \(a(b(c){\sim}d(e{\sim}f{\sim}g){\sim}h{\sim}i(j{\sim}k))\) and \(a(b(c){\sim}f{\sim}i(j{\sim}k))\). The first tree is isomorphic to the one depicted in \[t=\texttt{rep}(a,a,t_{1}{\sim}t_{2}){\sim}\texttt{mty}\]0 For all kinds of gap, there is a core term of the form  
\[t=\texttt{rep}(a,a,t_{1}{\sim}t_{2}){\sim}\texttt{mty}\]1where \(t\) is a core term that describes the sub-alignment between \(d(e{\sim}f{\sim}g){\sim}h\) and \(f\). In the complete subtree gap mode, this alignment requires three gaps: the first one to delete the complete subtree \(d(e{\sim}f{\sim}g)\), the second one to delete the other complete subtree \(h\), and the last one to insert the complete subtree \(f\).