# Algebraic Dynamic Programming on Trees
## 6 Tree Alignment
Thus, storing the roots' indices in a forest will directly give us the right-most leaves of the corresponding trees. We finally consider a variant of Equation (7) that distinguishes the match rule \(\binom{T}{T}\rightarrow\binom{n}{n}\binom{F}{F}\) with a unique non-terminal \(\binom{T}{T}\) on the left-hand side of Equation (8). This rule, which corresponds to the matching of the roots of two subtrees, is critical for the calculation of _match probabilities_ and will play a major role in Section 8. The non-terminals \(\binom{T}{Z}\) and \(\binom{Z}{T}\) designate insertion and deletion states, respectively. Thus, we can formulate the formal grammar for tree alignment as follows:  
\[ \begin{array}{ccccc}\text{iter}&\binom{F}{F}&\rightarrow&\binom{T}{T}\circ \binom{F}{F}&\big{|}&\binom{Z}{T}\circ\binom{F}{F}&\big{|}&\binom{T}{Z}\circ \binom{F}{F}&\big{|}&\binom{\mathfrak{S}}{\mathfrak{S}}\\ \text{align}&\binom{T}{T}&\rightarrow&\binom{n}{n}\cdot\binom{F}{F}\\ \text{deletion}&\binom{T}{Z}&\rightarrow&\binom{n}{-}\cdot\binom{F}{F}\\ \text{insertion}&\binom{Z}{T}&\rightarrow&\binom{-}{n}\cdot\binom{F}{F}\\ \end{array}  \tag{8}\]  
This grammar explicitly splits \(F^{\downarrow}\) and \(F^{\rightarrow}\) by applying iter. Hence, these parts recurse independently from each other. As shown in Figure 4, aligning two trees can lead to aligning the downwards forest of one tree to the forest to the right of the other tree. Given Equation (6), the first case corresponds to our first rule in iter and the align rule. Thus replacing \(\binom{T}{T}\) in iter we obtain \(\binom{F}{F}\rightarrow\binom{\left(n\right)\downarrow\binom{F}{F}}\circ \binom{F}{F}\). Here, \(\binom{n}{n}\) will give the score for aligning two non-terminals thus \(\gamma_{\gamma_{2}}^{\text{\tiny{p}}_{1}}\). The tree concatenation operators \(\downarrow\binom{F}{F}\) and \(\circ\binom{F}{F}\) correspond to \(F_{1}^{\downarrow},F_{2}^{\downarrow}\) and \(F_{1}^{\rightarrow},F_{2}^{\rightarrow}\), respectively. Replacing \(\binom{T}{Z}\) and \(\binom{Z}{T}\) in the deletion and insertion rules, we get \(\binom{F}{F}\rightarrow\left(\binom{n}{-}\cdot\binom{F}{F}\right)\circ \binom{F}{F}\) and \(\binom{F}{F}\rightarrow\left(\binom{-}{n}\cdot\binom{F}{F}\right)\circ \binom{F}{F}\). This corresponds to case 2 and 3 in Equation (6). As depicted in Figure 4, given a deleted root in one tree, we recurse by aligning both subforests. In case one of the subforests is empty, it will be replaced by the first tree (the first \(k\) trees, respectively) of the remaining forest. The following shows an example scoring algebra for the case of tree alignment with linear gap costs. No costs are added in the _iter_ case but scores obtained from subsolutions are added, given by \(s_{U}\) and \(s_{V}\). Here, \(U\) and \(V\) stand for the non-terminal characters whereas \(u,v\) are terminals. \[ \begin{array}{c}\text{iter}(s_{U},s_{V})=s_{U}+s_{V}\\ \text{match}(s,\binom{u}{v})=s+\omega(u,v)\\ \text{deletion}(s,\binom{u}{-})=s+\omega(u,-)\\ \text{insertion}(s,\binom{-}{v})=s+\omega(-,v)\\ \text{empty}(\binom{\mathfrak{S}}{\mathfrak{S}})=0\\ \text{choice}(s_{1},s_{2},..)=min(s_{1},s_{2},..)\\ \text{with }u,v\in\mathcal{A}\text{ and }s,s_{U},s_{V}\in S\end{array}  \tag{9}\]Two and Multi-Tape Tree Alignment  
**Definition 10** (multiple tree alignment). : _Let \(T_{1},T_{2},\ldots,T_{k}\) be ordered trees following Definition 1. The partial order of nodes of each tree sorts parent nodes before their children and children are ordered from left to right. An alignment between trees is a triple of functions \(f^{i}\) with \(i\in[1,\ldots,k]\) defines a function matching nodes in tree \(T_{i}\) to the consensus tree of the alignment:_  
_(i) The set of matched nodes form a partial order-preserving bijection. That is, if \(a=f^{i}(a),b=f^{i}(b)\in T_{i}\) are matched with \(f^{j}(a),f^{j}(b)\in T_{j}\) the partial orders \(a\prec b\) and \(f^{j}(a)\prec f^{j}(b)\) hold for all nodes \(a,b\) and pairs of trees \(T_{i},T_{j}\).