# Progressive Multiple Alignment of Graphs
## 1 Introduction  
The notion of alignments was introduced as a means of sequence comparison in computational biology [1]. Pairwise sequence alignments can be understood as representations of solutions to the string-editing problem, in which one string is converted into another one by a minimal sequence of insertions, deletions, and substitutions. Letters missing in a sequence are denoted by a special gap character \"-\". The notion easily generalizes to alignments of more than two sequences, resulting in a matrix whose rows correspond to the input sequences (padded by gap characters) and whose columns designate corresponding letters, i.e., homologous characters in applications to biological sequences; see [2] for a detailed review. The concept of alignments was later extended to rooted ordered trees [3]as a means of comparing RNA secondary structures [4]. More recently, a formal framework was developed to define alignments in a much more general setting [5], which we will review in the Theory section below (Section 2) in some detail. In this general setting, alignments are considered as super-objects containing the contributing input objects (sequences, trees, graphs, etc.) such that these are recovered by means of well-defined projections. Specializing this framework to graphs yields a notion of multiple graph alignment (MGA) that pertains to both directed and undirected graphs and also accommodates labeled graphs. The key property of an MGA is that the constituent input graphs appear as _induced subgraphs_ of the alignment graph. The term \"graph alignment\" is frequently used in the literature to refer to matchings between the vertex sets of graphs that maximize some similarity measure [6; 7; 8]. The construction considered in [9] uses \"alignment\" columns allowing \"dummy nodes\" corresponding to gap symbols, but does not endow the \"alignment\" with a graph structure. Similarly, IsoRank in its 1-1 mapping mode [10] computes a maximum weighted multipartite matching between the vertices of input networks \(G_{i}\) constrained in such a way that the connected components of its transitive closure (i.e., the alignment columns) contain at most one vertex from each of the \(G_{i}\). The weights are application-specific similarity scores computed for all pairs of vertices from different \(G_{i}\) and typically combine similarities of vertex attributes with neighborhood similarities, as in FINAL[11] or HashAlign[12]. Different algorithmic approaches have been employed to solve this optimization problem. While [10] uses a greedy heuristic, integer quadratic programming is proposed in [13]. Moreover, a wide variety of learning approaches have been used in recent years for this type of graph comparison, see, e.g., [14] and the references therein. In summary, all these graph matching methodologies differ in two important aspects from the concept of alignments used here: (1) they do not require the strict preservation of the local structure inherent in alignments and (2) they do not consider the alignment again as a graph. Furthermore, in [15], a \"graph alignment\" was defined by means of injective embeddings of the input graphs \(G_{i}\) into an \"entity graph\" \(H\) such that vertices adjacent in \(G_{i}\) are mapped to adjacent vertices in \(H\). In contrast to our framework, however, non-adjacent vertices in \(G_{i}\) may be mapped to adjacent vertices in \(H\). The constituent graph \(G_{i}\) thus appears as subgraphs of \(H\) but not _induced_ subgraphs of \(H\) and thus is not recoverable from \(H\) as a projection. The _compositional properties_ of alignments [5] require both the projective property and the fact that the alignment is again a graph. As a consequence \"alignments of graph alignments\" are well defined, preserve the projections of the constituent input graphs, and thus are again graph alignments of the same constituent graphs.