# Progressive Multiple Alignment of Graphs
## 5 Concluding Remarks  
Progressive alignments of seven graphs with 16-19 vertices can be computed in about 10 s using the prototype implementation ProGrAlign. On our test sets, consensus graphs, defined to contain alignment columns in which at least half of the input graphs are included, are a very good approximations of the reference graph \(G_{0}\). A difference as low as 3.5 is comparable to the smallest differences (2-4, see Figure A1 in Appendix A.1) between \(G_{0}\) and its variations \(G_{i}\), \(1\leq i\leq 7\), in each of the 50 scenarios. Discrepancies between methods are small, suggesting that solutions are close to optimal. Figure 7: Comparison of running times [s] of the eight experiments carried each over the 50 scenarios: \(T\) and \(S\) refer to the use of Iterative_Trimming and VF2_step, respectively. Kernel-based (\(k\)) or random (\(r\)) guide trees show a moderate but systematic advantage of a kernel-based similarity. The exclusion (\(\bigcirc\)) or inclusion (\(\blacksquare\)) of ambiguous edges is also compared. The graph alignments considered here differ from related concepts by explicitly considering alignments as super-graphs. In contrast, related work considers only correspondences of vertices, and, i.e., \"alignment columns\", without specifying edges and without strictly enforcing the conservation of adjacency. The main advantage of considering alignments as graphs is the resulting \"compositionality\", which makes it possible to build up multiple alignments in a step-wise fashion. The property that every input graph is recovered through a well-defined projection operation, furthermore, makes MGAs a proper generalization of multiple sequence alignments and the ordered forest alignments used for comparing RNA structures. Vertex matching procedures do not share these properties. An important concept that arises from the idea that alignments of graphs are again graphs are the _ambiguous edges_ in the alignment, i.e., edges in an alignment graph that never appear in the projection of any of the input graphs. Note, however, that ambiguous edges may be unambiguously preserved in the restriction of an alignment graph to a subset \(S\) of rows: this is the case if neither of its incident vertices is reduced to an all-gap column in the restriction to \(S\). Ambiguous edges are analogs of the ambiguity in the relative order of insertions and deletions between two consecutive match columns in sequence alignments. Sequence alignments can be improved by realigning such regions with the aim of \"harmonizing\" indel patterns [51]. From a theoretical point of view, such ambiguities have been studied with regard to their handling in dynamic programming algorithms [52]. In the case of (progressive) graph alignments, the analogous ambiguities are at least alleviated by considering ambiguous edges. We emphasize that MGAs are not intended as a replacement for vertex-matching procedures. In applications that require only local similarities of subgraphs, the stringent definition of MGAs is usually not necessary and arguably computationally too expensive. Well-defined consensus graphs, on the other hand, require that the MGA itself is well-defined graph. We expect that the framework will prove useful in particular in applications to evolutionary biology, where alignments are used because they not only represent similarity but also convey a notion of evolutionary relatedness. The implementation of the MGA described here is intended as a proof-of-concept, showing the feasibility and potential usefulness of the concept, which has been introduced from a purely theoretical perspective in [5]. Alignments of moderate-size and small graphs are, in particular, appealing for applications to molecular graphs. For these, atom labels and bond orders impose strong semantic constraints on the matches, which limit the computational efforts. For larger-scale applications, however, further algorithmic improvements will be necessary.