## 7 Tree Comparison and Related Problems
### Tree Alignment
#### 7.2.2 Tree Alignment with Affine Gap Scoring  
Tree alignment with affine gap scoring transfers the scoring models presented in Subsection 5.1 from pairwise sequence alignment to tree alignment. The difference is that the problem splits up in several variants because there are different ways to define a _gap_ in a tree, all of which may be justified in a particular application. This variety is a good example to see how the components of ICOREs cooperate in a modular fashion. The core signature captures affine scoring and the rewrite rules define the mapping between (all possible) core terms, i.e., alignments, and their input trees. These components remain the same, while different grammars come in to capture the different gap models which have been studied in the literature. Core signature and rewrite rules for composite gap scoring.Starting from ICORE TreeAlign with its atomic gap model, we first need to extend the core signature to distinguish gap openings from extensions, and describe suitable rewrite rules. We collect them in an ICORE template named TreeAliGeneric on page 113. TreeAliGeneric is to be extended with different grammars, according to the type of gap considered. In the literature, we can find a variety of ways to define _composite gaps_ in a tree. We review four of them, which are illustrated in Figure 10: (arbitrary) subtrees, complete subtrees, (arbitrary) subforests, and complete subforests. Let \(T\) be a tree. A _subtree_\(t\) of \(T\) is a set of nodes of \(T\) satisfying the two conditions: all the nodes of \(t\) have a lowest common ancestor, called the root of \(t\), and for each node \(x\) of \(t\), with the exception of the root, the parent of \(x\) belongs to \(t\). A _complete subtree_\(t\) of \(T\) is a subtree such that for each node \(x\) of \(t\), all descendants of \(x\) belong to \(t\). A _subforest_\(F\) of \(T\) is a contiguous sequence of of subtrees. A _complete subforest_ is a contiguous sequence of complete subtrees, which all share the same parent node. Gaps as complete subtrees.In this mode, a gap node belongs to the same composite gap as its ancestor node. The fact that we require that gaps are _complete_ subtrees means that it is not possible to continue an alignment in a subtree after a number of insertions and deletions. Such alignments are equivalent to edit scripts including no deletion, neither insertion of internal nodes. [PERSON] proposed a quadratic algorithm for this problem with linear gap weights [34]. An alternative solution that allows for arbitrary gap weights is to be found in [35]. We present here a grammar CompleteSubtree for this kind of gap, which uses three non-terminal symbols: N(o gap), D(eletion) and I(insertion). **Example 13**. : Consider the trees \(a(b(c{\sim}f))\) and \(a(d(e{\sim}f))\). The core term  
\[t=\texttt{rep}(a,a,t_{1}{\sim}t_{2}){\sim}\texttt{mty}\]  
Figure 10: Gaps for tree comparison. \[t_{1}=\texttt{open\_del}(b,\texttt{del}(c,\texttt{mty})\!\!\sim\!\! \texttt{del}(f,\texttt{mty})\!\!\sim\!\!\texttt{mty})\!\!\sim\!\!\texttt{mty}\] \[t_{2}=\texttt{open\_ins}(d,\texttt{ins}(e,\texttt{mty})\!\!\sim \!\!\texttt{ins}(f,\texttt{mty})\!\!\sim\!\!\texttt{mty})\!\!\sim\!\! \texttt{mty}\]  
represents the alignment where the subtree rooted by \(b\) is deleted, and the subtree rooted by \(d\) is inserted. Note that the grammar provides no way to align the two nodes labeled \(f\) once we deleted/inserted \(b\) and \(d\). Also, a subtree below an open_del can host neither insertions nor further deletion openings, and vice versa for open_ins. Gaps as complete subforests.The preceding gap model can be extended by considering complete subforests, instead of complete subtrees. Here, a gap node can be the extension of a larger gap for two separate reasons - because its ancestor is a gap node (like for subtrees), or because its left sibling is a gap node. With this definition, any gap in the tree is a gap on the underlying sequence of leaves.