Figure 3

An illustration of a rooted alignment A between T^vand$S^{v^{\prime }}$. (a) Each subtree of the form $T_u^v$ ($S_{u^{\prime }}^{v^{\prime }}$) is either pruned by the alignment, or matched to exactly one subtree of the form$S_{u^{\prime }}^{v^{\prime }}$ ($T_u^v$). In this example,$T_s^v$ is matched to$S_{z^{\prime }}^{v^{\prime }}$ (in red),$T_t^v$ is matched to$S_{y^{\prime }}^{v^{\prime }}$ (in blue), and$T_x^v$ is matched to$S_{t^{\prime }}^{v^{\prime }}$ (in green). These three subtree- matchings induce three sub-alignments of A:$A_s^v$,$A_t^v$, and$A_x^v$, respectively, where A is the union of these three sub-alignments (the pair (v,v′) participates in all three sub-alignments). The pruned subtrees in this example are $T_y^v$,$T_z^v$, and$S_{x^{\prime }}^{v^{\prime }}$. (b) The corresponding bipartite matching$M_{v,v^{\prime }}^A=\left\{\right(s,z^{\prime }),(t,y^{\prime }),(x,t^{\prime }\left)\right\}$ between N(v) and N(v′).