# Progressive Multiple Alignment of Graphs
## 2 Theory  
### Abstract Graph Alignments  
Following [5], we consider a class of finite hereditary set systems \((X,\mathcal{S})\), where \(X\) is a finite set and \(\mathcal{S}\) is some subset of \(2^{X}\cup 2^{2^{X}}\cup\dots\) such that for every subset \(Y\subseteq X\) the restriction \(\mathcal{S}_{Y}\) of \(\mathcal{S}\) to \(Y\) is well defined and satisfies the following consistency property \(\mathcal{S}_{Y}=(\mathcal{S}_{Z})_{Y}\) for all \(Y\subseteq Z\subseteq X\). In the following, we will refer to \((X,\mathcal{S})\) as an _object_. For \(Y\subseteq X\), \((Y,\mathcal{S}_{Y})=:(X,\mathcal{S}|Y]\) will be called the _subobject_ of \(X\) induced by \(Y\). Two set systems \((X,\mathcal{S})\) and \((X^{\prime},\mathcal{S}^{\prime})\) are _isomorphic_ if there is a bijection \(\varphi:X\to X^{\prime}\) such that \(\mathcal{S}^{\prime}=\varphi(\mathcal{S}^{\prime})\), where we use the convention that the application of a function to a set is defined point-wise, i.e., \(\varphi(Z):=\{\varphi(x)|x\in Z\}\). In this case, \(\varphi\) is an isomorphism and we write \((X,\mathcal{S})\simeq(X^{\prime},\mathcal{S}^{\prime})\). A very simple example of an object is the set \(X\) of positions in an DNA or protein sequence endowed with the total order \(\leq\) since these linear biomolecules have a specified orientation. The subobjects of \((X,\leq)\) are obtained as subsets of that preserve the order. To see that this indeed conforms to the abstract set systems introduced in the previous paragraph, we note that order relations can be encoded by sets: Setting \(S_{x}:=\{y\in X|y\leq x\}\) we see that \(x\leq y\) if and only if \(S_{x}\subseteq S_{y}\). Thus the order \(\leq\) is encoded by the subset relation in the set system \(\mathcal{S}:=\{S_{x}|x\in X\}\). The subobjects \((Y,\mathcal{S}_{Y})\) induced by \(Y\) thus are the set systems \(\mathcal{S}_{Y}=\{S_{x}\cap Y|x\in X\}\). Similarly, we may consider the class of rooted ordered trees [3]. As noted, for example, in [5], these correspond to finite sets with an orthogonal pair of partial orders: two vertices are either equal, comparable w.r.t. to the ancestor order, or w.r.t. to sibling order. In the present contribution, the objects of interest are graphs. Here, \(X\) denotes the vertices and \(\mathcal{S}\) corresponds to the edges of a graph, i.e., \(\mathcal{S}\) is a set of unordered pairs of distinct vertices. The sub-objects are the induced subgraphs defined by a subset of vertices. Abstraction, an _alignment_ of a set of \"input\" objects \((X_{i},\mathcal{S}_{i})\) consists of an object \((X,\mathcal{S})\) of the same class that contains each of the \((X_{i},\mathcal{S}_{i})\). More precisely, \(X_{i}\) is contained in \(X\) in the sense that there is an injective function \(\varphi_{i}:X_{i}\to X\) such that the subobject \((X,\mathcal{S})[Y_{i}]\) where \(Y_{i}=\varphi_{i}(X_{i})\) is isomorphic to \((X_{i},\mathcal{S}_{i})\) with \(\varphi_{i}:X_{i}\to Y_{i}\) being an isomorphism. It will be convenient to think of the \((X_{i},\mathcal{S}_{i})\) as the _rows_ of the alignment in analogy to multiple sequence alignments. Correspondingly, each \(x\in X\) specifies a _column_. Thus, the alignment can be encoded by a pair \((X,f)\) where \(f:X\to\{0,1\}^{n}\) and each component \(f_{i}:X\to\{0,1\}\) determines a subset \(Y_{i}:=\{x\in X|f_{i}(x)=1\}\) such that  
\[(X,\mathcal{S})[Y_{i}]\simeq(X_{i},\mathcal{S}_{i})\,. \tag{1}\]  
To avoid trivial cases, we forbid \"all-gap columns\", i.e., we insist that \(f_{i}(x)=1\) for at least one \(i\). Since we assume that the induced subobjects are unique, \(f\) defines the embeddings \(\varphi_{i}:X_{i}\to X\) up to isomorphism. We say that a point \(x\) in an alignment corresponds to a _match column_ of \(f_{i}(x)=1\) for all \(i\). Writing \(X_{M}=\{x\in X|f_{i}(x)=1,\,1\leq i\leq n\}\) for the set of matches, we observe that the restriction \((X_{M},\mathcal{S}_{X_{M}})\) of \((X,\mathcal{S})\) to \(X_{M}\subseteq X\) is a common sub-object of all \((X_{i},\mathcal{S}_{i})\).