# Progressive Multiple Alignment of Graphs
## 2 Theory
### Labels and Scores for Graph Alignments  
Labels are in particular used to introduce scoring functions, such as the BLOSSUM scores for (mis)matches of amino-acids. Most commonly, these are defined for pairwise alignments. Since all our practical computations also will involve only pairwise alignments, it suffices to consider the issue of scoring also for the pairwise case only. In this case, a common subobject is specified by a set of matches \(M\) whose elements are pairs \(x_{1}x_{2}\) with \(x_{1}\in X_{1}\) and \(x_{2}\in X_{2}\). Since the restriction of a set of matches to a subset  
Figure 2: Progressive graph alignment of three graphs (bottom) along a guide tree (fat red edges). The matching of vertices is shown by vertical lines. Two of the ambiguous edges in the pairwise alignment, which are inserted due to the matches with the third graph, are shown in green. is again a set of matches and thus defines again a common sub-object, the set \(\mathcal{M}\) of all sets of matches forms an independence system, i.e., \(M\in\mathcal{M}\) and \(M^{\prime}\subseteq M\) implies \(M\in\mathcal{M}^{\prime}\). We shall consider here only scoring functions that are defined on sets of matches, i.e., the score of a pairwise alignment is given by \(\sigma(M)\) where \(M\) is the set of matches corresponding to match columns \(X_{M}\). We say that a scoring function \(\sigma:\mathcal{M}\rightarrow\mathbb{R}\) is _strictly monotone_ if \(M^{\prime}\subsetneq M\) implies \(\sigma(M^{\prime})<\sigma(M)\). For strictly monotone scoring function, the maximum score can be attained only for sets of matches that are maximal, i.e., that cannot be augmented by an additional match. In the case of graphs, furthermore, every set of matches defines an alignment (which is unique up to ambiguous edges), and thus an optimal alignment is determined by a MCIS that in addition maximizes the scoring function \(\sigma\). The score may also depend on edge labels within the common induced subgraphs as long as the strict monotonicity property is preserved. A convenient special case is an additive scoring scheme in which every vertex-match and every edge-match yield a non-negative contribution. The inclusion of _additive_ edge-dependent scores is unproblematic from an algorithmic point of view because any procedure that adds or removes a match \(xx^{\prime}\) also adds or removes the incident edges \(\{xx^{\prime},yy^{\prime}\}\) connecting \(xx^{\prime}\) to the vertices \(yy^{\prime}\) in the rest of the common induced subgraph. Thus, every edge in the common induced subgraph is associated with a unique vertex operation, ensuring that adding/removing of single vertices affects the total score in a consistent manner. Assuming a strictly monotone scoring model, ambiguous edges are easy to handle. Suppose we attempt to add a match \(x_{1}x_{2}\) to a set \(M\) of matches. Then, the edge \(\{x_{1}x_{2},y_{1}y_{2}\}\) to some match \(y_{1}y_{2}\) is added if either both \(x_{1}y_{1}\) and \(x_{2}y_{2}\) are ambiguous edges, or one of the two edges is unambiguous and the other is ambiguous. No edge is inserted if there is a non-edge between \(x_{1}\) and \(y_{1}\) or \(x_{2}\) and \(y_{2}\). Note that if both the edges \(x_{1}y_{1}\) and \(x_{2}y_{2}\) are ambiguous, then \(\{x_{1}x_{2},y_{1}y_{2}\}\) is again ambiguous. In either case, the extension of \(M\) by \(x_{1}x_{2}\) by assumption incurs a positive score increment and thus yields a better score than leaving \(x_{1}\) and \(x_{2}\) as two unmatched vertices. Finally, we note that since ambiguous edges are removed in all branches at some lower-down node of the guide tree, they do not convey information on the input graphs. Thus, an edge \(\{x_{1}x_{2},y_{1}y_{2}\}\) where \(x_{1}y_{1}\) or \(y_{1}y_{2}\) is ambiguous naturally does not yield a positive score even when otherwise edge-matches are associated with score contributions. The most natural scoring function for alignments of alignments is the sum-of-pairs scoring model, in which the contributions of all pairwise alignments are simply added.