0000-0003-2028-7670 ††thanks:

0000-0001-9517-5839 ††thanks:

0000-0002-5016-5191 ††thanks:

# Alignments as Compositional Structures

Sarah Berkemer<EMAIL_ADDRESS>Max Planck Institute for
Mathematics in the Sciences, Leipzig, Germany; and Bioinformatics Group,
Department of Computer Science, Universität Leipzig, Germany  Christian Höner
zu Siederdissen<EMAIL_ADDRESS>Bioinformatics Group,
Department of Computer Science, Universität Leipzig, Germany  Peter F. Stadler
<EMAIL_ADDRESS>Bioinformatics Group, Department of Computer
Science, Universität Leipzig, Germany; Max Planck Institute for Mathematics in
the Sciences, Leipzig, Germany; Department of Theoretical Chemistry,
University of Vienna, Austria; Facultad de Ciencias, Universidad Nacional de
Colombia, Bogotá, Colombia; Santa Fe Institute, Santa Fe, NM, USA;

###### Abstract

Alignments, i.e., position-wise comparisons of two or more strings or ordered
lists are of utmost practical importance in computational biology and a host
of other fields, including historical linguistics and emerging areas of
research in the Digital Humanities. The problem is well-known to be
computationally hard as soon as the number of input strings is not bounded.
Due to its practical importance, a huge number of heuristics have been
devised, which have proved very successful in a wide range of applications.
Alignments nevertheless have received hardly any attention as formal,
mathematical structures. Here, we focus on the compositional aspects of
alignments, which underlie most algorithmic approaches to computing
alignments. We also show that the concepts naturally generalize to finite
partially ordered sets and partial maps between them that in some sense
preserve the partial orders.

##  1 Introduction

Alignments play an important role in particular in bioinformatics as a means
of comparing two or more strings by explicitly identifying correspondences
between letters (usually called matches and mismatches) as well as insertions
and deletions Durbin et al. (1998). The aligned positions are interpreted
either as deriving from a common ancestor (“homologous”) or to be functionally
equivalent. Alignments have also been explored as means of comparing words in
natural languages, see e.g. Kondrak (2000); Cysouw and Jung (2007); Steiner et
al. (2011); Bhattacharya et al. (2018), as a convenient way of comparing
ranked lists Fagin et al. (2003), for comparison of text editions Wolff
(2000); Tiepmar and Heyer (2017), and to analyse synteny in the comparison of
genomes Grabherr et al. (2010); Velandia-Huerto et al. (2016).

The literature on alignments is extensive. However, it its concerned almost
exclusively with practical algorithms and applications. The alignment problem
for two input strings has an elegant recursive solution for rather general
cost models and has served as one of the early paradigmatic examples of
dynamic programming Needleman and Wunsch (1970); Sankoff and Kruskal (1983).
Since these algorithms have only quadratic space and time requirements for
simple cost models Needleman and Wunsch (1970); Gotoh (1982), they are of key
importance in practical applications. The same recursive structure easily
generalizes to alignments of more than two sequences Carrillo and Lipman
(1988); Lipman et al. (1989) even though the cost models need to be more
restrictive to guarantee polynomial-time algorithms Kececioglu and Starrett
(2004). The computational effort for these exact solutions to the alignment
problem increases exponentially with the number of sequences, hence only
implementations for 3-way Gotoh (1986); Konagurthu et al. (2004); Kruspe and
Stadler (2007) and 4-way alignments Steiner et al. (2011) have gained
practical importance. A wide variety of multiple sequence alignment problems
(for arbitrary numbers of input sequences) have been shown to be NP-hard
Kececioglu (1993); Wang and Jiang (1994); Bonizzoni and Della Vedova (2001);
Just (2001); Elias (2006) and MAX SNP-hard Wareham (1995); Manthey (2003). The
construction of practical multiple alignment algorithms therefore relies on
heuristic approximations. These fall into several classes, see e.g. Edgar and
Batzoglou (2006); Baichoo and Ouzounis (2017) for reviews.

(1) _Progressive_ methods typically compute all pairwise alignments and then
use a “guide tree” to determine the order in which these are stepwisely
combined into a multiple alignment of all input sequences. The classical
example is ClustalW Larkin et al. (2007). The approach can be extended to
starting from exact 3-way Konagurthu et al. (2004); Kruspe and Stadler (2007)
or 4-way alignments Steiner et al. (2011).

(2) _Iterative_ methods starting to align small gapless subsequences and then
extend and improve the alignment until the score converges. A paradigmatic
example is DIALIGN Morgenstern (1999).

(3) _Consistency_ -based alignments and _consensus_ methods start from a
collection of partial alignments (often exact pairwise alignments) to obtain
candidate matches and extract a multiple alignment using agreements between
between the input alignments.

Most of the successful multiple alignment algorithm in computational biology
combine these paradigms. For example T-COFFEE Notredame et al. (2000) and
ProbCons Do et al. (2005) use consistency ideas in combination with
progressive constructions; MUSCLE Edgar (2004) and MAFFT Katoh et al. (2005)
combine progressive alignments with iterative refinements.

            (a)               (b)               (c)                (d)
      A 0000111110000    A 0000111110000    B 000011011----    B 000011011
      B 000011011----    C ----100010000    C ----100010000    C 100010000
        s = 4              s = 2              s = -5             s = 5

Figure 1: Alignments of three binary sequences A, B, and C with a simple
column-wise score of $+1$ for matches, $0$ for mismatches, and $-1$ for gaps.
Alignment (c) is transitively implied by (a) and (b), but is it not an optimal
pairwise alignment of B and C.

A key assumption underlying consistency based methods is transitivity:
considering three input sequences $x$, $y$, and $z$, if $x_{i}$ aligns with
$y_{j}$ and $y_{j}$ aligns with $z_{k}$, then $x_{i}$ should also align with
$z_{k}$. While this property holds for the pairwise constituents of a multiple
alignment, it is a well known fact that the three score-optimal alignments
that can be constructed from three sequences in general violate transitivity,
see Fig. 1. TRANSALIGN Malde and Furmanek (2013) uses transitivity to align
input sequences to a target database using an intermediary database of
sequences to increase the search space. Here, intermediary sequences show
which subsequences of input and target sequence can be transitively aligned.
This may result in a few well aligned subsequences that are then extended to
one aligned region via a simple scoring function. The same notion of
transitivity is also used in psiblast Altschul et al. (1997) to stepwisely
increase the set of sequences that are faintly similar to an input sequence.

Practical applications distinguish whether the complete input sequences are to
be aligned, or whether a maximally scoring interval is to be considered. In
the latter case one allows an additional “unaligned state” for prefixes and/or
suffixes of the input. This leads to slight changes in exact algorithms,
exemplified by an extra term in the local Smith-Waterman algorithm Smith and
Waterman (1981) compared to the global Needleman-Wunsch Needleman and Wunsch
(1970) algorithm. This idea can be generalized to mixed problems in which a
user can determine for each of the two ends of each input sequence whether it
is to be treated as local or global Retzlaff and Stadler (2018). For the
purpose of the present contribution (partially) local alignments require a
slight, trivial extension of the presentation, which we – for the sake of
clarity in the presentation – only briefly comment on.

Alignments are usually constructed from strings or other totally ordered
inputs, hence the columns of the resulting alignment are usually also treated
as a totally ordered set. Consecutive insertions and deletions, however, are
not naturally ordered relative to each other:

      gugugu--acgggcca          guguguac--gggcca
      gucuguug--gggccc          gucugu--uggggccc

(1)

are alignments that are equivalent under most plausible scoring models. The
idea to consider alignment columns as partial orders was explored
systematically in Lee et al. (2002) and a series of follow-up publications Lee
(2003); Grasso and Lee (2004). Here, (mis)matches are considered as an ordered
backbone, with no direct ordering constraints between an insertion and a
deletion. The resulting alignments are then represented as directed acyclic
graphs (DAGs), more precisely, as the Hasse diagrams of the partial order. The
key idea behind the POA software Lee et al. (2002) is that a sequence of DAGs
can be used as an input to a modified version of the Needleman-Wunsch
algorithm Needleman and Wunsch (1970). Recently this idea has been generalized
to the problem of aligning a sequence to a general directed graph Rautiainen
and Marschall (2017); Vaddadi et al. (2017).

Despite the immense practical importance of alignments, they have received
very little attention as mathematical structures in the past. The most
comprehensive treatment, at least to our knowledge, is the Technical Report
Morgenstern et al. (1999), which considers (pairwise) alignments as binary
relations between sequence positions that represent matchings and preserve
order. We use many of these ideas here. The notion of a composition of
pairwise alignments – formalized as composition of partial maps that represent
the matching – first appears in Malde and Furmanek (2013). We will return to
this point in Section 3. Following our earlier work Otto et al. (2011), we
will use a language that is closer to graph theory than the presentation of
Morgenstern et al. (1999).

##  2 Alignments and Partial Orders

Consider a finite collection $X$ of two or more finite totally ordered sets
$X_{a}$. It will be convenient in the following to denote an element $i\in
X_{a}$ by $(a,i)$. The following definition rephrases the approach taken e.g.
in Stoye et al. (1997); Morgenstern et al. (1999). It will be generalized
below to deal with partial orders instead of total orders.

######  Definition 1 (Otto et al. (2011)).

A total alignment of the totally ordered sets $X_{a}$ is a triple $(X,A,<)$
where $(X,A)$ is a graph and $<$ is a total order relation on the set of
connected components $\mathcal{C}(X,A)$ satisfying111There is no condition (3)
due to synchronization with the definitions for partial orders defined later.

  * (1)

$Q\in\mathcal{C}(X,A)$ is a complete subgraph of $(X,A)$.

  * (2)

If $(a,i)\in Q$ and $(a,j)\in Q$, then $i=j$.

  * (4)

If $(a,i),(b,j)\in P$ and $(a,k),(b,l)\in Q$ with $i<k$ then $j<l$.

  * (5)

If $(a,i)\in P$, $(a,j)\in Q$ and $i<j$ then $P<Q$.

The connected components of $(X,A)$ are usually called the alignment columns.
Condition (2) ensures that every alignment column contains at most one element
of each ordered set $X_{a}$. Conversely, every element $(a,i)$ is contained in
exactly one connected component, i.e., alignment column. Condition (4)
requires that alignment columns do not cross. Condition (5) ensures that the
order on the columns is such that the projection of the alignment columns to
each individual row exactly recovers the input order. Conditions (4) and (5)
in general only specify a partial order as the following result shows:

######  Lemma 2.

Let $(X,A)$ be the graph of an alignment and denote by $\prec$ the relation on
$\mathcal{C}(X,A)$ defined by $P\prec Q$ whenever there is $(a,i)\in P$ and
$(a,j)\in Q$ with $i<j$. Then the transitive closure $\ddot{\prec}$ of $\prec$
is a partial order on $\mathcal{C}(X,A)$.

###### Proof.

Clearly $\ddot{\prec}$ is antisymmetric. If $P\prec Q$, then there there is a
sequence of columns $P=Q_{0}\ddot{\prec}Q_{1}\ddot{\prec}\dots Q_{k}=Q$. Since
the sequence of elements $(a,i)$ belonging to the same $X_{a}$ is strictly
increasing with the column index $j$ for each $a$ along any such sequence of
columns, it follows that the transitive closure of $\ddot{\prec}$ is still
antisymmetric, and thus a partial order. ∎

As an immediate consequence, there is also a (not necessarily unique) total
order $<_{*}$ of the alignment columns, obtained as an arbitrary linear
extension of $\ddot{\prec}$, which by construction satisfies

$P<_{*}Q,\,(a,i)\in P,\,\textrm{and}\,(a,j)\in Q\quad\textrm{implies}\quad
i<j.$ (2)

Hence, whenever conditions (1), (2), and (4) in Definition 1 are satisfied,
there indeed exists a total order on $\mathcal{C}(X,A)$ that satisfies
condition (5).

In order to treat (partially) local alignments it is necessary to distinguish
aligned and “unaligned” columns. Each unaligned column may contain only a
single element – note however, that also regular columns may contain only a
single entry from each row. Furthermore, all “unaligned” positions for a
prefix and/or a suffix of each input $(X_{a},<_{a})$ form “unaligned” columns.

In this condition we will consider a more general setting. Instead of totally
ordered sets $X_{a}$ we will consider finite partially ordered sets
$(X_{a},\prec_{a})$.

######  Definition 3.

An alignment of $X$ is a triple $(X,A,\prec)$ where $(X,A)$ is a graph and
$\prec$ is a partial order on the set of connected components
$\mathcal{C}(X,A)$ such that

  * (A1)

$Q\in\mathcal{C}(X,A)$ is a complete subgraph of $(X,A)$.

  * (A2)

If $(a,i)\in Q$ and $(a,j)\in Q$, then $i=j$.

  * (A3)

If $(a,i)\in P$, $(a,j)\in Q$ and $(a,i)\prec_{a}(a,j)$ then $P\prec Q$.

  * (A4)

$P\prec Q$, $(a,i)\in P$ and $(a,j)\in Q$ implies $(a,i)\prec_{a}(a,j)$ or
$(a,i)$ and $(a,j)$ are incomparable w.r.t. $\prec_{a}$.

Condition (A3) constrains the partial order on the columns to respect the
partial order of the rows. Condition (A4) insists that columns also must not
cross indirectly.

Condition (A4) obviously implies the following generalization of (4):

  * (A4∗)

$(a,i),(b,j)\in P$ and $(a,k),(b,l)\in Q$ and $(a,i)\prec_{a}(a,k)$ implies
$(b,j)\prec_{b}(b,l)$ or $(b,j)$ and $(b,l)$ are incomparable w.r.t.
$\prec_{b}$.

However, (A4∗) is not sufficient to guarantee that the alignment columns form
a partially ordered set. A counterexample is shown in Fig. 2. It is therefore
necessary to require the existence of the partial order $\prec$ on
$\mathcal{C}(X,A)$ in Definition 3.

Figure 2: Property (A4∗) is not sufficient to ensure the existence of a
partial order $\prec$ on $\mathcal{C}(X,A)$. Consider the partial orders
$(a,4)\prec_{a}(a,1)$ and $(a,2)\prec_{a}(a,3)$ and $(b,1)\prec_{b}(b,2)$ and
$(b,3)\prec_{a}(b,4)$, with alignment colums $\\{(a,i),(b,i)\\}$ for
$i=1,2,3,4$. Clearly (A2), (A3), and (A4∗) holds, but the directed cycle shows
that no partial order on the colums exists that is consistent with both
partial orders.

In order to model partially local alignments of posets we consider the set
$\mathcal{A}$ of aligned columns and a partition of the set of “unaligned
columns” into two not necessarily non-empty subsets $\mathcal{P}$ and
$\mathcal{S}$ such that for all $U\in\mathcal{P}$, $V\in\mathcal{A}$ and
$W\in\mathcal{S}$ it holds that $W\not\preceq V$ and $V\not\preceq U$, i.e.,
no “unaligned” suffix column preceeds an aligned column, and no “unaligned”
prefix column succeeds an aligned column. “Unaligned” prefix columns belonging
to different rows $(X_{a},\prec_{a})$ are considered mutually incomparable;
the same is assumed for “unaligned” suffix columns. With the caveat that
“unaligned” columns need to be marked as such, there is no structural
difference between local and global alignments.

If all $(X_{a},\prec_{a})$ are totally ordered then condition (A4) implies the
non-crossing condition (4) because $(b,j)$ and $(b,l)$ cannot be incomparable
w.r.t. $\prec_{b}$, and thus the required partial order $\prec$ is obtained as
the transitive closure of the relative order of any two columns. Definitions 1
and 3 therefore coincide for totally ordered rows.

The existence of (non-trivial) alignments of any collection of finite partial
orders ${(X_{i},\prec_{i})}$, $i=1,\dots,N$ is easy to see: each of the
partial orders can be linearly extended to a total order $(X_{i},<_{i})$. Any
alignment of these total orders is also an alignment of the underlying partial
orders, with a suitable partial order of the columns given by Lemma 2.

It may be interesting to explore alignments satisfying a (much) stronger
version of axiom (A4), which stipulates that $(X_{a},\prec_{a})$ is recovered
as projection of $(X,A)$ onto row $a$, i.e.,

  * (A5)

$P\prec Q$, $(a,i)\in P$ and $(a,j)\in Q$ implies $(a,i)\prec_{a}(a,j)$.

As argued above, (A4) and (A5) are equivalent if all $(X_{a},\prec_{a})$ are
totally ordered. In general this is not the case, as the example in Fig. 3
shows.

Figure 3: Top: Pairwise alignments of partially ordered sets. Thin black edges
show the Hasse diagram, to be read from left to right. Alignment edges are
shown in green.
Bottom: The induced partial order of the alignment columns with corresponding
points vertically aligned. The partial order is again shown as a Hasse
diagram, with superflous edges omitted. Both the l.h.s. and the r.h.s. example
satisfy (A4), i.e., none of order relations $\prec_{1}$ and $\prec_{2}$ is
violated in the alignment. The red edges highlight two comparabilities
introduced by partial order of the columns that are absent in the input
posets. Red edges therefore imply a violation of condition (A5). Hence the
l.h.s. alignment violates (A5), while the r.h.s. alignment does not.

The following simple, technical result is a generalization of Lemma 2, showing
that condition (A5) is sufficient to guarantee the existence of a partial
order on the columns.

######  Lemma 4.

Let $(X,A)$ be a graph with connected components $\mathcal{C}(X,A)$ satisfying
(A1) and (A2). Let $\prec$ denote the transitive closure of the relation
$\dot{\prec}$ defined by (A3), i.e., $P\dot{\prec}Q$ whenever $(a,i)\in P$,
$(a,j)\in Q$ and $(a,i)\prec_{a}(a,j)$ then $P\prec Q$. Finally assume that
axiom (A5) holds. Then $\prec$ is a partial order on $\mathcal{C}(X,A)$

###### Proof.

It suffices to show that $\prec$ is antisymmetric. It is clear from the
construction that by (A5) we know that $\dot{\prec}$ is antisymmetric. If
$\prec$ is not antisymmetric, then there is a finite sequence of columns
$P_{i}$, $i=0,\dots,k$ such that
$P_{0}\dot{\prec}P_{1}\dot{\prec}\dots\dot{\prec}P_{k}\dot{\prec}P_{0}$ such
that any two consecutive columns $P_{i}$ and $P_{i+1}$ have at a pair of
entries, say $(a_{i},h)\in P_{i}$ and $(a_{i},h^{\prime})\in P_{i+1}$, in the
same row. For the transitive closure this would imply both
$(a_{i},h)\prec(a_{i},h^{\prime})$ from
$(a_{i},h)\dot{\prec}(a_{i},h^{\prime})$ and
$(a_{i},h^{\prime})\prec(a_{i},h)$ by going around the cycle, contradictiong
axiom (A5). ∎

Condition (A5) implies that the restriction of the partial order $\prec$ on
the columns to any subset of columns in which a given set of rows is
represented coincides with the induced partial order on the corresponding
vertex set in $(X_{a},\prec_{a})$. Regarding the $(X_{a},\prec_{a})$ as
graphs, the aligned columns form a common induced subgraph. The alignment
problem for partially ordered sets under axiom (A5) thus can be seen as a
generalized version of a maximum induced subgraph problem. We refer to Bunke
(1997) for a discussion of the relationships of edit distances and maximum
common subgraph problems in a more general setting.

The following result generalizes Lemma 1 of Otto et al. (2011):

######  Lemma 5.

Let $(X,A,\prec)$ be an alignment and let $Y\subseteq X$. Then the induced
subgraph $(X,A)[Y]$ with the partial order $\prec$ restricted to the non-empty
intersections $Q\cap Y$ for $Q\in\mathcal{C}(X,A)$ is again an alignment.
Furthermore, if $(X,A,\prec)$ satisfies (A5), then the restriction to
$(X,A)[Y]$ again satisfies (A5).

###### Proof.

Every induced subgraph of a complete graph is again a complete graph, hence
(A1) holds for $(X,A)[Y]$, hence the connected components of $(X,A)[Y]$ are
exactly the non-empty intersections of $Y$ with the components $Q$ of $(X,A)$.
Condition (A2) remains unchanged by the restriction to $Y$. Finally, the
partial order $\prec$ satisfying (A3) restricted to the non-empty
intersections $Q\cap Y$ for $Q\in\mathcal{C}(X,A)$ is a partial order that
obviously still satisfies (A4) since the restriction to $Y$ only removes some
of the conditions in (A4).

To see that the restriction of $(X,A)[Y]$ again satisfies (A5) it suffices to
recall that the partial order in the colums is given by $P\cap Y\prec Q\cap Y$
whenever $P\prec Q$ and both $P\cap Y\neq\emptyset$ and $Q\cap
Y\neq\emptyset$. If one of the intersections is empty, axiom (A5) becomes void
since the empty set is not a column in $(X,A)[Y]$. On the other hand, if the
two restricted columns have entries $(a,i)$ and $(a,j)$ in the same row, then
(A5) for $(X,A,\prec)$ ensures $(a,i)\prec_{a}(a,j)$, i.e., the implication
(A5) remains true for the restricted alignment. ∎

Note that additional partial orders on connected components of the induced
subgraph $(X,A)[Y]$ may exist that are not obtained as restrictions of the
partial order on $\mathcal{C}(X,A)$. The reason is that omitting parts of the
columns may allow a relaxation of their mutual ordering.

Rooted trees can be seen as partially ordered sets, with the natural partial
order defined by $x\prec y$ if $y$ lies on the unique path connecting $x$ and
the root of the tree. This special case is thus covered in the general
framework outlined here. Usually, tree alignments are defined on rooted
_oriented trees_ , however, where the relative order of siblings is preserved
Jiang et al. (1995); Höchsmann et al. (2004); Berkemer et al. (2017), thus
imposing additional restrictions on valid alignments. We will return to this
point in some generality in the discussion section.

##  3 Composition of Alignments

The fact that alignments are again totally or partially ordered sets implies
that one can also meaningfully define alignments of alignments. More
precisely:

######  Lemma 6.

Let $(X,A,\prec)$ be an alignment and consider a non-trivial partition
$\mathfrak{P}$ of the set of objects, i.e., the rows. Denote the site sets of
the classes of $\mathfrak{P}$ by $X_{1}$, $X_{2}$, …, $X_{p}$ and consider the
sub-alignments $(X,A,\prec)[X_{i}]$. Then $(X,A,\prec)$ is isomorphic to the
(vertex) disjoint union of the $(X,A,\prec)[X_{i}]$ augmented by extra edges
$(x^{\prime},x^{\prime\prime})$ whenever there is a column $Q$ of $A$ with
$x^{\prime}\in Q\cap X_{i}$ and $x^{\prime\prime}\in Q\cap X_{j}$ for
$X_{i}\neq X_{j}$.

###### Proof.

The alignments $(X,A,\prec)[X_{i}]$ are induced subgraphs of $(X,A)$. Their
disjoint union lacks exactly all edges that connect pairs of vertices that are
in the same connected component of $(X,A)$ but are not in the same subgraph
$(X,A)[X_{i}]$. Since the partial order on the colums of $(X,A)[X_{i}]$ is the
one inherted from $(X,A,\prec)$, the re-composition of the columns also
recovers the original partial order. ∎

The $(X,A,\prec)[X_{i}]$ can also be interpreted as partially ordered sets
whose _points_ are the non-empty restrictions $Q\cap X_{i}$ of the connected
components of $(X,A)$.

######  Definition 7.

We denote by $(X,A)/\mathfrak{P}$ the quotient graph whose vertices are the
columns of the alignments $(X,A)[X_{i}]$, that is, the non-empty sets $Q\cap
X_{i}$ where $Q$ is a connected component of $(X,A)$. Its edges are the pairs
$(Q\cap X_{i},Q\cap X_{j})$ for which both $Q\cap X_{i}$ and $Q\cap X_{j}$ are
non-empty.

The connected components of the graph $(X,A)/\mathfrak{P}$ are therefore of
the form $Q^{\prime}:=Q/\mathfrak{P}=\\{Q\cap X_{i}|Q\cap
X_{i}\neq\emptyset\\}$. Note that $Q^{\prime}$ is non-empty since the column
$Q$ of $(X,A)$ contains at least one element, which belongs to at least one of
the $(X,A)[X_{i}]$. Thus there is a 1-1 correspondence between the connected
components of $(X,A)$ and those of $(X,A)/\mathfrak{P}$. The columns of
$(X,A)/\mathfrak{P}$ naturally inherit the partial order $\prec$ of
$\mathcal{C}(X,A)$. We write $(X,A,\prec)/\mathfrak{P}$ for the quotient graph
with this partial order on its connected components.

######  Lemma 8.

$(X,A,\prec)/\mathfrak{P}$ is an alignment.

###### Proof.

Consider the quotient graph $(X,A)/\mathfrak{P}$. By construction, each column
$Q^{\prime}$ is a complete graph and contains at most one node for each class
of $\mathfrak{P}$ since it is the quotient of a column of $(X,A,\prec)$ w.r.t.
$\mathfrak{P}$. Also by construction, we have $P^{\prime}\prec Q^{\prime}$ for
the columns of $(X,A)/\mathfrak{P}$ whenever $P\prec Q$ in $(X,A,\prec)$.
Since there is a 1-1 correpondence between columns of $(X,A,\prec)$ and
$(X,A,\prec)/\mathfrak{P}$, $\prec$ also serves as a partial order on the
columns of $(X,A)/\mathfrak{P}$, which is by construction consistent with the
partial order on each of the $(X,A)[X_{i}]$. ∎

As a consequence, every alignment can be decomposed into an alignment of
alignments w.r.t. an arbitrary partition of the rows. The constituent
alignments $(X_{i},A,\prec_{i})$ have at most the same number of columns since
“all gap” columns, $Q^{\prime}=Q\cap X_{i}=\emptyset$, are removed. By Lemma
8, the decomposition can be used recursively until each constituent is only a
single partially ordered set $(X_{a},\prec_{a})$. Any such recursive
composition is naturally represented as a tree $\mathfrak{T}$ whose leaves are
the input posets $(X_{a},\prec_{a})$. Each internal node of $\mathfrak{T}$
corresponds the an alignment of its children, with the root corresponding to
$(X,A,\prec)$, the alignment of all the data.

The reverse of this type of decomposition underlies all _progressive
alignment_ schemes. One starts from a guide tree $\mathfrak{T}$ whose leaves
are the $(X_{a},\prec_{a})$ and for each inner node of $\mathfrak{T}$
constructs an alignment (or a set of alternative alignments) from the (set of)
alignments attached to its children. It is important to note that a score-
optimal alignment $(X,A,\prec)$ in general is not the score-optimal alignment
$(X,A,\prec)/\mathfrak{P}$ of score-optimal consitutents
$(X_{i},A_{i},\prec_{i})$, or, in other words, if $(X,A,\prec)$ is score-
optimal, there is no guarantee that there is any partition of the rows
$\mathfrak{P}$ such that all the restrictions $(X,A,\prec)[X_{i}]$ are score-
optimal subalignments. Progressive alignments methods thus can only
approximate the solution of the multiple alignment problem. Practical results
depend substantially on the choice of the guide tree $\mathfrak{T}$. It is has
been suggested early Feng and Doolittle (1987), that $\mathfrak{T}$ should
closely resemble the evolutionary history of the input sequences. Usually
$\mathfrak{T}$ is constructed from distance or similarity measures between all
pairs of input sequences – and usually pairwise alignments are employed to
obtain these data. A special case of progressive alignment adds a single
sequence in each step, instead of also considering alignments of alignments.

##  4 Blockwise Decompositions

On the other hand, we can also decompose alignments into blocks of columns.
More precisely, if $(X,A,\prec)$ is an alignment and $\mathfrak{Q}$ is a
partition of the $X$ with classes $Y_{k}$ such that

  * (i)

If $P\in\mathcal{C}(X,A)$ then $P\subseteq Y_{k}$ for some class
$Y_{k}\in\mathfrak{Q}$.

  * (ii)

There is a partial order $\triangleleft$ on $\mathfrak{Q}$ such that for any
two distinct classes $Y^{\prime},Y^{\prime\prime}\in\mathfrak{Q}$ such that
$Y^{\prime}\triangleleft Y^{\prime\prime}$ whenever there are columns $P\in
Y^{\prime}$ and $Q\in Y^{\prime\prime}$ with $P\prec Q$.

We call the classes of such a partition _blocks_. By Lemma 5 each block
$(X,A,\prec)[Y_{k}]$ is again an alignment.

######  Lemma 9.

Given blocks $(X,A,\prec)[Y_{k}]$ and the partial order $\triangleleft$, there
is an alignment $(X,A,\prec^{\prime})$, where $\prec^{\prime}$ is an an
extension of $\prec$ defined by $P\prec^{\prime}Q$ if and only if $P\prec Q$
for $P,Q\in Y$ for some $Y\in\mathfrak{Q}$ and $P\prec^{\prime}Q$ for $P\in
Y^{\prime}$ and $Q\in Y^{\prime\prime}$ with $Y^{\prime}\triangleleft
Y^{\prime\prime}$.

###### Proof.

Each alignment block consists of the disjoint union of alignment column(s),
thus the disjoint union of complete subgraphs. Given the partial order of
alignment columns given by $P\prec Q$, this order is preserverd inside the
alignment blocks $Y_{k}$ as each block is an alignment, too. Given an
alignment block $Y$ with $P\prec Q$ for $P,Q\in Y$ for some
$Y\in\mathfrak{Q}$, one can decompose this into two blocks $Y^{\prime}$ and
$Y^{\prime\prime}$ with at least one column in each block such that $P\in
Y^{\prime}$ and $Q\in Y^{\prime\prime}$. Based on the decomposition of $Y$
into $Y^{\prime}$ and $Y^{\prime\prime}$ one can restore the order of the
alignment blocks such that $Y^{\prime}\triangleleft Y^{\prime\prime}$ based on
$Y$. Thus, one gets the order of $P\prec^{\prime}Q$ that is present for the
alignment columns $P$ and $Q$ as well as for the alignment blocks $Y^{\prime}$
and $Y^{\prime\prime}$. ∎

In the case of totally ordered inputs, the restriction $X_{a}\cap Y$ of a
block $Y$ to an input $X_{a}$ is an interval of $X_{a}$ and the columns in $Y$
form an interval of the columns of $(X,A,<)$. Similarly, one can restrict the
choice of blocks in such a way that $\triangleleft$ just “mirrors” the initial
partial order, i.e., $Y^{\prime}\triangleleft Y^{\prime\prime}$ if and only if
$P\prec Q$ for $P$ in $Y^{\prime}$ and $Q$ in $Y^{\prime\prime}$, in which
case $\prec^{\prime}\;=\;\prec$ and the original alignment is recovered by the
concatenation of the blocks. In particular, this also guarantees that valid
block decompositions can be constructed for alignments satisfying (A5).

Each alignment can thus be recursively decomposed into blocks. This sets the
stage for Divide-and-Conquer algorithms such as DCA Stoye et al. (1997), which
cuts the sequences to be aligned into subsequences and then concatenates the
subalignments so as to optimize a global score. In order to find the best cut-
points, the algorithm recurses on differently cut subsequences. Algorithms
such as dialign Morgenstern (1999) work in a conceptually similar manner but
use a bottom-up instead of a top-down approach: they first identify blocks
with high sequence conservation as “anchors” and recurse to construct
alignments for sequences between them.

An extreme case of the block-wise decomposition is to consider the division of
an alignment $(X,A,\prec)$ into a single maximal (or minimal) alignment column
$P$, and the rest $(X\setminus P,A^{\prime},\prec)$ of the alignment. In order
for $X\setminus A\triangleleft P$ to hold, we have to ensure that
$p_{a}\not\prec_{a}q_{a}$ for all $p_{a}\in P$ and $q_{a}\in X\setminus P$,
i.e., the column $P$ must entirely consist of suprema of the respective input
posets. Under this condition, we obtain a recursive column-wise decomposition
of alignments. As we shall see in the following section, this recursion can
also be used constructively.

##  5 Recursive Construction

Given a poset $(Y,\prec)$ we say that $P\subseteq Y$ is a _bottom set_ if, for
all $p\in P$, every $p^{\prime}\prec p$ satisfies $p^{\prime}\in P$. By
definition, the empty set, $Y$ itself, as well as the set $\\{p^{\prime}\in
Y|p^{\prime}\preceq y\\}$ for each $y\in Y$ are bottom sets. Note, however,
that $P$ also may contain points that are incomparable to all other elements
of $P$. Denote by $\sup P$ the set of _suprema_ of $P$, i.e., the points such
that there is no $p^{\prime}\in P$ with $p\prec p^{\prime}$. Clearly, if $P$
is a bottom set and $p\in\sup P$ then $P\setminus\\{p\\}$ is again a bottom
set. The latter observation suggests that there is a recursive construction
for the set of alignments of $(X_{1},\prec_{1})$ and $(X_{2},\prec_{2})$.

Denote by $\mathfrak{A}^{P}_{Q}$ the set of all pairwise alignments on bottom
sets $P$ in $X_{1}$ and $Q$ in $X_{2}$. An alignment
$\mathbb{A}\in\mathfrak{A}^{P}_{Q}$ is necessarily of one of three types:

  * (i)

$\mathbb{A}=\mathbb{A}^{\prime}{\scriptscriptstyle\left(\begin{smallmatrix}p\\\
q\end{smallmatrix}\right)}$ with
$\mathbb{A}^{\prime}\in\mathfrak{A}^{P^{\prime}}_{Q^{\prime}}$,

  * (ii)

$\mathbb{A}=\mathbb{A}^{\prime}{\scriptscriptstyle\left(\begin{smallmatrix}p\\\
-\end{smallmatrix}\right)}$ with
$\mathbb{A}^{\prime}\in\mathfrak{A}^{P^{\prime}}_{Q}$, or

  * (iii)

$\mathbb{A}=\mathbb{A}^{\prime}{\scriptscriptstyle\left(\begin{smallmatrix}-\\\
q\end{smallmatrix}\right)}$ with
$\mathbb{A}^{\prime}\in\mathfrak{A}^{P}_{Q^{\prime}}$,

where $P^{\prime}:=P\setminus\\{p\\}$ for $p\in\sup P$,
$Q^{\prime}:=Q\setminus\\{q\\}$ for $q\in\sup Q$, and
$\mathfrak{A}^{\emptyset}_{\emptyset}$ contains only the empty alignment.

The three cases correspond to a (mis)match, insertion, and deletion. It is
important to note that this recursion is in general not unique because the
columns extracted from $\mathbb{A}$ in consecutive steps are not necessarily
ordered relative to each other whenever $|\sup P|\geq 1$ or $|\sup Q|\geq 1$.
It is, however, a proper generalization of the Needleman-Wunsch recursion
Needleman and Wunsch (1970) for the pairwise alignment of ordered sets
(strings): If the $\prec_{a}$ are total orders, then $\sup P_{a}$ always
contains a single element, and we recover the usual Needleman-Wunsch
algorithm. In order to have a proper start and end case for the recursion and
thus DP-algorithm, it is convenient to introduce “virtual” source and a sink
nodes being connected to all start or end nodes of the poset, respectively.

This idea generalizes to alignments of an arbitrary number of partial orders
in the obvious way. Denote by $\mathfrak{A}(P_{1},P_{2},\dots,P_{N})$ the set
of all alignments where the $P_{a}$ are a bottom set of $(X_{a},\prec_{a})$.

######  Theorem 10.

Every alignment $\mathbb{A}\in\mathfrak{A}(P_{1},P_{2},\dots,P_{N})$ is of the
form $\mathbb{A^{\prime}}\Xi$ where the alignment column $\Xi$ is a supremum
w.r.t the partial order of $\prec$ of alignment columns and
$\mathbb{A^{\prime}}\in\mathfrak{A}(P^{\prime}_{1},P^{\prime}_{2},\dots,P^{\prime}_{N})$.
The column $\Xi$ contains in row $a$ either a gap row $a$, in which case
$P^{\prime}_{a}=P_{a}$, or $p_{a}\in\sup P_{a}$, in which case
$P^{\prime}_{a}=P_{a}\setminus\\{p_{a}\\}$, and does not entirely consist of
gaps. For every column $\Upsilon$ of $\mathbb{A}^{\prime}$ we have either
$\Upsilon\prec\Xi$ or $\Upsilon$ and $\Xi$ are incomparable.

###### Proof.

The $P^{\prime}_{a}$ are again bottom sets, hence $\mathbb{A^{\prime}}$ is an
alignment. By assumption, there is a partial order on the columns $\prec$ of
$\mathbb{A}^{\prime}$. Since every non-gap entry in $\Xi$ is a $p_{a}\in\sup
P_{a}$, it follows that this partial order extends to $\mathbb{A}$ if and only
if $\Xi$ is a supremum, i.e., it is either incomparable with or larger than
any column in $\mathbb{A}^{\prime}$. Now suppose that the column $\Xi$
contains a $q_{a}\notin\sup P_{a}$, i.e., there is a $p_{a}\in X_{a}$ with
$p_{a}\succ q_{a}$. Consider the column $\Upsilon$ containing $p_{a}$. Then
either no partial order $\prec$ on the columns exists (contradicting that
$\mathbb{A}^{\prime}$ is an alignment), or $\Upsilon\succ\Xi$ (contradicting
that $\Xi$ is a supremum for the alignment columns. ∎

The bottom sets are of course uniquely defined by their suprema. Clearly $\sup
P$ is an antichain, i.e., its elements are pairwisely incomparable.
Conversely, every antichain $U$ in $(X_{a},\prec_{a})$ uniquely defines a
bottom set $P:=\\{p\in X_{a}|p\preceq U\\}$. It is obvious therefore that for
two bottom sets $P$ and $Q$ it holds that $P=Q$ if and only if $\sup P=\sup
Q$. Hence there is a 1-1 correspondence between the antichains of a partial
order and their bottom sets. The recursion in the theorem can be written in
terms of the antichains of the $(X_{a},\prec_{a})$.

In order to capture the more restrictive notion of alignments satisfying (A5)
the recursion has to be modified in a such a way that for every (mis)match
between two rows it can be ensured that all previously formed columns are
either comparable in both rows or incomparable in both rows. This is non-
trival because this information is not purely local. For ease of discussion,
we only consider the case of aligning two posets. There are at least two
strategies to maintain this information.

Attempting to construct a similar recursion as in the (A4) case, one could
store with each pair $P\in X_{1}$ and $Q\in X_{2}$ also all the set
$\mathcal{M}$ of all matchings
${\scriptscriptstyle\left(\begin{smallmatrix}p\\\ q\end{smallmatrix}\right)}$
“to the right” of $P$ and $Q$, i.e., $p\in X_{1}\setminus P$ and $q\in
X_{1}\setminus Q$. Then every allowed matching/column
${\scriptscriptstyle\left(\begin{smallmatrix}p^{\prime}\\\
q^{\prime}\end{smallmatrix}\right)}$, $p^{\prime}\in\sup P$ and
$q^{\prime}\in\sup Q$ must satisfy: for all
${\scriptscriptstyle\left(\begin{smallmatrix}p\\\
q\end{smallmatrix}\right)}\in\mathcal{M}$ holds: either $p^{\prime}\prec p$
and $q^{\prime}\prec q$, or both $p^{\prime},p$ and $q^{\prime},q$ are
incomparable. Every such pair can be appended to $\mathcal{M}$, with
corresponding updates $P\to P\setminus\\{p^{\prime}\\}$ and $Q\to
Q\setminus\\{q^{\prime}\\}$. Insertions and deletions of course only require
the removal of either $p^{\prime}$ from $P$ or $q^{\prime}$ from $Q$,
respectively. Initially, $P=X_{1}$, $Q=X_{2}$, and $\mathcal{M}=\emptyset$.
Every set of valid partial alignments is characterized by a triple
$(P,Q,\mathcal{M})$.

An alternative approach is to store instead for each $p\in P$ and $q\in Q$
also the sets $c_{Q}(p)$ and $c_{P}(q)$ that can form matches
${\scriptscriptstyle\left(\begin{smallmatrix}p\\\
q^{\prime}\end{smallmatrix}\right)}$, $q^{\prime}\in c_{Q}(p)$ and
${\scriptscriptstyle\left(\begin{smallmatrix}p^{\prime}\\\
q\end{smallmatrix}\right)}$, $p\in c_{P}(q)$, respectively. Initially, we have
$P=X_{1}$, $Q=X_{2}$, $c_{Q}(p)=Q$ for all $p\in P$ and $c_{P}(q)=P$ for all
$q\in Q$. Whenever an alignment is continued with a (mis)match
${\scriptscriptstyle\left(\begin{smallmatrix}p\\\ q\end{smallmatrix}\right)}$,
$p\in\sup P$, $q\in\sup Q$, we have to remove all candidates from
$c_{P}(q^{\prime})$ and $c_{Q}(p^{\prime})$ that are inconsistent with
${\scriptscriptstyle\left(\begin{smallmatrix}p\\\ q\end{smallmatrix}\right)}$.
That is: if $q^{\prime}\prec q$, then
$c_{P}(q^{\prime})\leftarrow\\{p^{\prime}\in c_{P}(q^{\prime})|p^{\prime}\prec
p\\}$. If $q$ and $q^{\prime}$ and incomparable, then
$c_{P}(q^{\prime})\leftarrow\\{p^{\prime}\in
c_{P}(q^{\prime})|p^{\prime},p\textrm{ incomparable}\\}$. The
$c_{Q}(p^{\prime})$ are updated correspondingly. In the case of an insertion
${\scriptscriptstyle\left(\begin{smallmatrix}p\\\ -\end{smallmatrix}\right)}$,
we only need to remove $p$ from $f_{P}(q^{\prime})$, $q^{\prime}\in Q$.
Similarly, ${\scriptscriptstyle\left(\begin{smallmatrix}-\\\
q\end{smallmatrix}\right)}$ implies that $q$ has to be removed from the
$f_{Q}(p^{\prime})$ for all $p^{\prime}\in P$. We suspect that an encoding of
alignment sets of the form $(P,f_{Q}:P\to 2^{P};Q,f_{P}:Q\to 2^{P})$ will be
efficient if the poset has only small antichains. A more detailed analysis of
this kind of recursive construction from the point of view of algorithmic
efficiency will be considered elsewhere.

The POA algorithm Lee et al. (2002) computes the alignment of two posets
satisfying (A5), albeit with the restriction that one of the two inputs is
totally ordered. This removes all ambiguities in the totally ordered po-set
and implies that, given any match
${\scriptscriptstyle\left(\begin{smallmatrix}u\\\ v\end{smallmatrix}\right)}$
in the alignment, all preceeding matches
${\scriptscriptstyle\left(\begin{smallmatrix}u^{\prime}\\\
v^{\prime}\end{smallmatrix}\right)}$ satisfy $v^{\prime}<v$ in the totally
ordered set and thus $u^{\prime}$ must be a predecessor of $u$. The alignment
thus must follow a single path in the Hasse diagram of the unrestricted input
poset.

##  6 Pairwise Alignments as Relations

Pairwise alignments have a particularly simple structure. In particular, they
are bipartite (undirected) graphs, and hence can be regarded equivalently as
symmetric binary relations $R\subseteq X_{1}\times X_{2}$. More precisely, we
can identify a relation $R$ with an undirected graph with vertex set
$X_{1}\dot{\cup}X_{2}$ and (undirected) edges $\\{x_{1},x_{2}\\}$ whenever
$(x_{1},x_{2})\in R$. We write this graph as $(X_{1}\dot{\cup}X_{2},R)$.

Relations have a natural composition. For $R\subseteq X\times Y$ and
$S\subseteq Y\times Z$ is is defined by

$(x,z)\in S\circ R\quad\textrm{iff}\quad\exists y\in Y\textrm{ s.t. }(x,y)\in
R\textrm{ and }(y,z)\in S$ (3)

In the following we will be interested in the following properties of binary
relations:

  * (M)

$(x,y)\in R$ and $(x,z)\in R$ implies $y=z$ and $(x,z)\in R$ and $(y,z)\in R$
implies $x=y$.

  * (P’)

There is a partial order $\prec$ on $R$ such that $u\prec_{1}x$ or
$v\prec_{2}y$ implies $(u,v)\prec(x,y)$.

  * (P)

If $(x_{1},y_{1})\in R$ and $(x_{2},y_{2})\in R$ then $x_{1}\prec x_{2}$ if
and only if $y_{1}\prec y_{2}$.

######  Lemma 11.

The composition of two binary relations satisfying (M) and (P) is again a
binary relation satisfing (M) and (P).

###### Proof.

Suppose $(x,z)\in R\circ S$. Then there is $y$ such that both $(x,y)\in R$ and
$(y,z)\in S$. By (M), there is no other $y^{\prime}\neq y$ with
$(x,y^{\prime})\in R$ and no $z^{\prime}\neq z$ such that
$(y^{\prime},z^{\prime})\in S$, hence in particular there is no
$z^{\prime}\neq z$ such that $(x,z^{\prime})\in R\circ S$. Analogously, one
argues that there is no $x^{\prime}\neq x$ such that $(x^{\prime},z)\in R\circ
S$. Thus $R\circ S$ again satisfies (M).

Suppose $(x_{1},z_{1}),(x_{2},z_{2})\in R\circ S$. By (M) there are unique
vertices $y_{1}$ and $y_{2}$ such that $(x_{1},y_{1}),(x_{2},y_{2})\in R$ and
$(y_{1},z_{1}),(y_{2},z_{2})\in S$, respectively. Now suppose
$x_{1}\prec_{1}x_{2}$. Then (P) implies $y_{1}\prec_{2}y_{2}$, and using (P)
again yields $z_{1}\prec_{3}z_{2}$. Starting from $z_{1}\prec_{3}z_{2}$, the
same argument yields $z_{1}\prec_{1}z_{2}$. Conversely, suppose
$(x_{1},z_{1}),(x_{2},z_{2})\in R\circ S$ and $x_{1},x_{2}$ are incomparable.
By (M) there are unique vertices $y_{1}$ and $y_{2}$ with
$(x_{1},y_{1}),(x_{2},y_{2})\in R$ and $(y_{1},z_{1}),(y_{2},z_{2})\in S$, for
which (P) now implies that they are incomparable. Using the same argument
again shows that that $z_{1}$ and $z_{2}$ also must be incomparable. Hence
concatenation preserves not only the relative order but also comparability,
i.e., $R\circ S$ again satisfies (P). ∎

It is easy to see that Axiom (P’) is in general not preserved under
concatenation: Requiring only (P’) allows the intermediate vertices $y_{1}$
and $y_{2}$ to be incomparable. Hence it is possible in this scenario to have
$x_{1}\prec_{1}x_{2}$, incomparable vertices $y_{1}$ and $y_{2}$, and
$z_{2}\prec_{3}z_{1}$ with $(x_{1},y_{1}),(x_{2},y_{2})\in R$ and
$(y_{1},z_{1}),(y_{2},z_{2})\in S$ while the concatenation violates the (P’).

A relation satisfying (M) and (P’) can easily be extended to an alignment
$(X_{1}\cup X_{2},R)$ considering each edge $(x_{1},y_{1})$ and considering
all unmatched positions, i.e., every $\\{x^{\prime}\\}$ such that there is no
$y\in X_{2}(x^{\prime},y)$ and every $\\{y^{\prime}\\}$ such that there is no
$x\in X_{1}(x,y^{\prime})$ as alignment columns. The relative order of these
columns is inherited from the partial order $(X_{1},\prec_{1})$ and
$(X_{2},\prec_{2})$.

######  Lemma 12.

Every pairwise alignment satisfying (A1), (A2), (A3), and (A4) can be written
as an extension of the a binary relation $R\subseteq X_{1}\times X_{2}$
satisfying (M) and (P’). Conversely, every binary relation $R\subseteq
X_{1}\times X_{2}$ satisfying (M) and (P’) gives rise to an alignment
satisfying (A1), (A2), (A3), and (A4).

###### Proof.

By definition, all edges are incident to one vertex in $X_{1}$ and one vertex
in $X_{2}$, thus the graph is a bipartite matching. Condition (M) is therefore
equivalent to (A1) and (A2) for the case of two input posets. Axiom (A3)
implies the ordering required by (P’) as well as its extension to the in/del
columns. (A4) and (P’) equivalently guarantee the existence of the partial
order on the columns that satisfy (A3). ∎

######  Lemma 13.

Every pairwise alignment satisfying (A5) corresponds to a binary relation
$R\subseteq X_{1}\times X_{2}$ satisfying (M) and (P).

###### Proof.

Axiom (A5) simplifies to (P) in the case of only two inputs. The existence of
the required partial order on the set of all columns is guaranteed by Lemma 4.
∎

This suggests that the more restrictive condition (A5) may be a more natural
condition for defining alignments of partially ordered sets. As a down-side,
however, it seems that there is no convenient recursive construction of the
search space similar to the dynamic programming approaches for sequence
alignment. Instead, it seems more natural to treat this class of alignment
problems as maximum induced subgraph problems.

Composition of binary relations is a powerful tool to construct multiple
alignments. Suppose we are given a set of posets $(X_{a},\prec_{a})$ and a set
$\mathcal{R}$ of pairwise relations satisfying (M) and (P) such that the graph
representation of $\mathcal{R}$ is tree, then there is a unique multiple
alignment satisfying (A5) obtained as the transitive closure of the graph on
$X$ with edges defined by the $R\in\mathcal{R}$. However, not every alignment
can be represented in this manner. As a simple counterexample consider the
alignment of the three sequences

      a  A-C         a  A-C                  a  A-C
      b  -BC         b  -BC     b  -BC       b  -BC
      c  AB-                    c  AB-       c A-B-

where the composition of any two pairwise alignments gives rise to two
different columns for in/del columns of the pairwise components, in the
example of two A entries. On the other hand the progressive approach, in which
sequence c is aligned to the pairwise alignment of a and b yields the example
alignment. In fact, Lemma 8 implies that in principle every alignment can be
obtained by a progressive alignment scheme.

If $\mathcal{R}$ contains cycles, then there is no guarantee that the
transitive closure $\widehat{A}$ of $\bigcup_{R\in\mathcal{R}}R$ is an
alignment: In general, both conditions (A1) and (A2) will be violated. So-
called _transitive alignment_ approaches deliberately accept this at an
intermediate stage. Various heuristics can be used to remove superfluous edges
from the graph $(X,\widehat{A})$, that is they construct a subgraph $(X,A)$,
$A\subseteq\widehat{A}$ that again satisfies all conditions of a valid
alignment.

##  7 Discussion

An interesting idea that follows quite naturally from the discussion above is
a general approach towards graph comparison for sets of graphs: it seems
natural to generalize the idea of progressive alignments in the following
manner: (1) Given two graphs $G_{1}$ and $G_{2}$ and a common induced subgraph
$H$ (strictly speaking together with an embedding of $H$ into $G_{1}$ and
$G_{2}$) the graph defined by identifing the copies of $H$ in $G_{1}$ and
$G_{2}$ can be thought of as pairwise alignment. If $G_{1}$ and $G_{2}$ have
vertex labels $\alpha_{i}:V(G_{i})\to A_{i}$, $i=1,2$ for some alphabets
$A_{i}$, on labels $G_{1}\bullet_{H}G_{2}$ with label pairs
($\alpha_{1}(x),\alpha_{2}(x)$) for $x\in V(H)$, $(\alpha_{1}(x),-)$ for $x\in
V(G_{1}\setminus H)$ and $(-,\alpha_{2})$ for $x\in V(G_{2}\setminus H)$.
Naturally, an optimization criterion such as “maximal common induced subgraph”
will be used in practice. Since $G_{1}\bullet_{H}G_{2}$ is again a (labeled)
graph, the procedure can be repeated e.g. along a line of guidetrees. This
gives raise to a natural notion of a multiple alignment of graphs $G_{a}$ with
vertex sets $V(G_{a})$ and edge sets $E(G_{a})$. Let $X=\dot{\bigcup}V(G_{a})$
and $A$ be a set of undirected edges on $X$ and let $\mathcal{C}(X,A)$ be the
set of connected components of the graph $(X,A)$. Then $(X,A,E^{*})$ is a
multiple alignment of the graph $G_{a}$, where $E^{*}$ denotes the set of
edges on $\mathcal{C}(X,A)$.

  * (G1)

$Q\in\mathcal{C}(X,A)$ is complete subgraph of $(X,A)$.

  * (G2)

If $(a,i)\in Q$ and $(a,j)\in Q$, then $i=j$.

  * (G3)

If $(a,i)\in P$, $(a,j)\in Q$ for some $P,Q\in\mathcal{C}(X,A)$ and
$((a,i),(a,j))\in E(G_{a})$ then $(P,Q)\in E^{*}$

  * (G5)

If $(P,Q)\in E$, $(a,i)\in P$, and $(a,j)\in Q$ then $((a,i),(a,j))\in E^{*}$

The graph $(\mathcal{C}(X,A),E^{*})$ can be constructed as the quotient graph
$(X,A\cup\bigcup_{a}E(G_{a}))/\mathcal{C}(X,A)$ obtained by adding in all the
edges of $G_{a}$ and collapsing all columns (connected components) of $(X,A)$
to a single vertex. A plausible generalization of (A4) might be to require

  * (G4)

If $(P,Q)\in E^{*}$ then there is a row $a$ with $(a,i)\in P$, $(a,j)\in Q$
and $((a,i),(a,j))\in E(G_{a})$,

i.e., (G3) completely determines the edges between alignment columns. In this
setting (G4) does not impose additional conditions on the columns. However, if
both the input graphs $G_{a}$ and the alignment graph
$(\mathcal{C}(X,A),E^{*})$ are restricted to particular graph classes, such
constraints appear. The graphs of partially ordered sets, i.e., the transitive
acyclic digraphs discussed at length in the previous sections, of course,
serve as a non-trivial example.

It is important to note the graph alignment in the sense used here – namely
requiring a matching between vertices and notion of structural congruence
between the alignment and its consitutent graphs – are more restrictive than
some concepts of “graph alignments” discussed in the literature. In
particular, we make a sharp distinction here between “graph alignments” and
various approaches of comparison by means of graph editing, see e.g. Emmert-
Streib et al. (2016) for a recent review.

The example of graph alignments and oriented tree alignments suggests to
consider an even broader class of structures: Given a (finite) collection of
sets $X_{a}$, each endowed with a set of relational structures (or more
general set systems), we may ask for collections of partial maps between any
pair of them that satisfy (G1) and (G2), i.e., define a partition on
$\bigcup_{a}X_{a}$ such that each class contains at most one element of each
$X_{a}$ and the relation (or set system) structure is preserved in a sense
similar to conditions (G3) and (G5) above. Such constructions are of practical
interest e.g. for alignments of oriented trees (or forests) Jiang et al.
(1995); Höchsmann et al. (2004); Berkemer et al. (2017), where two distinct
partial orders are defined, one capturing the order implied by parent-child
relationship and another one representing the relative order of siblings.
Alignments of ordered trees preserve both partial orders, since the alignment
is defined as an ordered tree on the columns such that each ordered input tree
(with vertices $X_{a}$) is obtained as a restriction to exactly the columns in
which row $a$ does not have a gap entry. Intuitively, this seems to require
that (1) a super-object $G$ exists for a pair of objects $G_{1}$ and $G_{2}$
such that $G_{1}$ and $G_{2}$ can be obtained as projections and (2) an
intersection of the embeddings of $G_{1}$ and $G_{2}$ into $G$ defines an
induced sub-object $H$ common to $G_{1}$ and $G_{2}$ is well defined. While
the super-object corresponds to the alignments, the sub-object takes on the
role of matches in the alignment. A similar notion of alignment is used in
computational biology for RNA structures, where base pairs need to be
preserved in addition the total order of the input sequences Möhl et al.
(2010). Here, however, only consistency similar in flavor to (A4) is enforced,
suggesting that it may be of interest to relax the requirement of _induced_
sub-objects.

The recursive formulation of the poset alignments is an extension of the well-
known Needleman-Wunsch alignment algorithm. Beyond many implementations of the
Needleman-Wunsch algorithm, the implementation based on ADPfusion (Algebraic
Dynamic Programming with compile-time fusion of grammar and algebra) Höner zu
Siederdissen (2012) is designed in a way to be extendable to different scoring
functions, problem descriptions, and data structures Höner zu Siederdissen et
al. (2015a). Future work thus will include the adaptation of the ADPfusion
framework written in a functional language (Haskell) to the data structure of
posets. Earlier adaptations of the Needleman-Wunsch algorithm to trees,
forests and sets already exist Berkemer et al. (2017); Höner zu Siederdissen
et al. (2015b).

It may also be possible to implement the poset alignment algorithm for the
(A5)-notion of alignments in a way similar to the graph alignment algorithm
above, i.e., starting from a maximal induced common subgraph that is then
extended. Depending on the structure of the posets, this might be more
efficient than the recursive DP algorithm where additional information has to
be stored and updated in each step.

Finding maximal induced common subgraphs is well known to be a NP-complete
problem. Nevertheless, DP algorithms have been devised for restricted settings
such as planar graphs Fomin et al. (2011). These proved practical for moderate
size problems even though their resource requirements still scale
exponentially.

For general graphs, there exist algorithms to detect common subgraphs Akutsu
(1993). However, as the problem is NP-complete, the problem can only be solved
for small instances of the input structures in a reasonable amount of time.
For small graphs such as representations of small chemical molecules, the DP
algorithm might be able to solve the maximal common subgraph problem as
described in Akutsu (1993). Here, the DP algorithm is based on the analogous
version for trees where the vertex degree has to be bounded in order to find a
solution in a reasonable time frame. The algorithm divides the input
structures in (overlapping) biconnected components and tries to find the best
match between both input graphs preserving the order of the biconnected
components of the original graph.

Finally, it seems natural to consider multiple alignments at a more abstract
level: In order to properly define them, it seems sufficient that (induced)
sub-objects can be used to “glue together” two (and recursively more) objects
in such a way that the resulting super-object projects down to the given
inputs. It is natural to ask how such structures can be characterized in the
language of category theory. Is there an interesting class of categories that
admit well-defined alignments objects, and do the resulting alignments
themselves from categories with useful properties?

## Acknowledgements

This work was supported in part by the German Academic Exchange Service
(DAAD), proj.no. 57390771.

## References

  * Akutsu [1993] Tatsuya Akutsu.  A polynomial time algorithm for finding a largest common subgraph of almost trees of bounded degree.  _IEICE transactions on fundamentals of electronics, communications and computer sciences_ , 76(9):1488–1493, 1993\.
  * Altschul et al. [1997] Stephen F Altschul, Thomas L Madden, Alejandro A Schäffer, Jinghui Zhang, Zheng Zhang, Webb Miller, and David J Lipman.  Gapped BLAST and PSI-BLAST: a new generation of protein database search programs.  _Nucleic Acids Res._ , 25:3389–3402, 1997.  10.1093/nar/25.17.3389.
  * Baichoo and Ouzounis [2017] Shakuntala Baichoo and Christos A. Ouzounis.  Computational complexity of algorithms for sequence comparison, short-read assembly and genome alignment.  _Biosystems_ , 156/157:72–85, 2017.  10.1016/j.biosystems.2017.03.003.
  * Berkemer et al. [2017] Sarah J Berkemer, Christian Höner zu Siederdissen, and Peter F Stadler.  Algebraic dynamic programming on trees.  _Algorithms_ , 10:135, 2017.  10.3390/a10040135.
  * Bhattacharya et al. [2018] Tanmoy Bhattacharya, Damian Blasi, William Croft, Michael Cysouw, Daniel Hruschka, Ian Maddieson, Lydia Müller, Nancy Retzlaff, Eric Smith, Peter F. Stadler, George Starostin, and Hyejin Youn.  Studying language evolution in the age of big data.  _J. Language Evol._ , 3:94–129, 2018.  10.1093/jole/lzy004.
  * Bonizzoni and Della Vedova [2001] Paola Bonizzoni and Gianluca Della Vedova.  The complexity of multiple sequence alignment with SP-score that is a metric.  _Theor. Comp. Sci._ , 259:63–79, 2001.  10.1016/S0304-3975(99)00324-2.
  * Bunke [1997] H. Bunke.  On a relation between graph edit distance and maximum common subgraph.  _Pattern Recognition Letters_ , 18:689–694, 1997.  10.1016/S0167-8655(97)00060-3.
  * Carrillo and Lipman [1988] Humberto Carrillo and David Lipman.  The multiple sequence alignment problem in biology.  _SIAM J. Appl. Math._ , 48:1073–1082, 1988.  10.1137/0148063.
  * Cysouw and Jung [2007] Michael Cysouw and Hagen Jung.  Cognate identification and alignment using practical orthographies.  In _Proceedings of Ninth Meeting of the ACL Special Interest Group in Computational Morphology and Phonology_ , pages 109–116. Association for Computational Linguistics, 2007.  URL https://www.aclweb.org/anthology/W/W07/W07-1314.pdf.
  * Do et al. [2005] Chuong B Do, Mahathi SP Mahabhashyam, Michael Brudno, and Serafim Batzoglou.  ProbCons: Probabilistic consistency-based multiple sequence alignment.  _Genome Res._ , 15:330–340, 2005.  10.1101/gr.2821705.
  * Durbin et al. [1998] Richard Durbin, Sean R Eddy, Anders Krogh, and Graeme Mitchison.  _Biological sequence analysis: probabilistic models of proteins and nucleic acids_.  Cambridge University Press, Cambridge, UK, 1998.
  * Edgar and Batzoglou [2006] R C Edgar and S Batzoglou.  Multiple sequence alignment.  _Curr Opin Struct Biol_ , 16:368–373, 2006.  10.1016/j.sbi.2006.04.004.
  * Edgar [2004] Robert C Edgar.  MUSCLE: multiple sequence alignment with high accuracy and high throughput.  _Nucleic Acids Res._ , 32:1792–1797, 2004.  10.1093/nar/gkh340.
  * Elias [2006] Isaac Elias.  Settling the intractability of multiple alignment.  _J. Comp. Biol._ , 13:1323–1339, 2006.  10.1089/cmb.2006.13.1323.
  * Emmert-Streib et al. [2016] Frank Emmert-Streib, Matthias Dehmer, and Yongtang Shi.  Fifty years of graph matching, network alignment and network comparison.  _Information Sci._ , 346/347:180–197, 2016.  10.1016/j.ins.2016.01.074.
  * Fagin et al. [2003] Ronald Fagin, Ravi Kumar, and D. Sivakumar.  Comparing top-$k$ lists.  _SIAM J. Discr. Math._ , 17:134–160, 2003.  10.1137/S0895480102412856.
  * Feng and Doolittle [1987] Da-Fei Feng and Russell F Doolittle.  Progressive sequence alignment as a prerequisite to correct phylogenetic trees.  _J. Mol. Evol._ , 25:351–360, 1987.  10.1007/BF02603120.
  * Fomin et al. [2011] Fedor V. Fomin, Ioan Todinca, and Yngve Villanger.  Exact algorithm for the maximum induced planar subgraph problem.  In Camil Demetrescu and Magnús M. Halldórsson, editors, _Proceedings of the 19th European conference on Algorithms_ , volume 6942 of _Lecture Notes Comp. Sci._ , pages 287–298, Berlin, Heidelberg, 2011. Springer-Verlag.
  * Gotoh [1982] O Gotoh.  An improved algorithm for matching biological sequences.  _J. Mol. Biol._ , 162:705–708, 1982.  10.1016/0022-2836(82)90398-9.
  * Gotoh [1986] O. Gotoh.  Alignment of three biological sequences with an efficient traceback procedure.  _J. theor. Biol._ , 121:327–337, 1986.  10.1016/S0022-5193(86)80112-6.
  * Grabherr et al. [2010] Manfred G. Grabherr, Pamela Russell, Miriah Meyer, Evan Mauceli, Jessica Alföldi, Federica Di Palma, and Kerstin Lindblad-Toh.  Genome-wide synteny through highly sensitive sequence alignment: Satsuma.  _Bioinformatics_ , 26:1145–1151, 2010.  10.1093/bioinformatics/btq102.
  * Grasso and Lee [2004] Catherine Grasso and Christopher Lee.  Combining partial order alignment and progressive multiple sequence alignment increases alignment speed and scalability to very large alignment problems.  _Bioinformatics_ , 20:1546–1556, 2004.  10.1093/bioinformatics/bth126.
  * Höchsmann et al. [2004] Michael Höchsmann, Björn Voss, and Robert Giegerich.  Pure multiple RNA secondary structure alignments: a progressive profile approach.  _IEEE/ACM Trans. Comp. Biol. Bioinf._ , 1:53–62, 2004.  10.1109/TCBB.2004.11.
  * Höner zu Siederdissen [2012] Christian Höner zu Siederdissen.  Sneaking around concatMap: Efficient combinators for dynamic programming.  In _Proceedings of the 17th ACM SIGPLAN international conference on Functional programming_ , ICFP ’12, pages 215–226, New York, NY, USA, 2012. ACM.  ISBN 978-1-4503-1054-3.  10.1145/2364527.2364559.  URL http://www.bioinf.uni-leipzig.de/Software/gADP/.
  * Höner zu Siederdissen et al. [2015a] Christian Höner zu Siederdissen, Ivo L. Hofacker, and Peter F. Stadler.  Product grammars for alignment and folding.  _IEEE/ACM Trans. Comp. Biol. Bioinf._ , 12:507–519, 2015a.  10.1109/TCBB.2014.2326155.
  * Höner zu Siederdissen et al. [2015b] Christian Höner zu Siederdissen, Sonja J. Prohaska, and Peter F. Stadler.  Algebraic dynamic programming over general data structures.  _BMC Bioinformatics_ , 16 Suppl 19:S2, 2015b.  10.1186/1471-2105-16-S19-S2.
  * Jiang et al. [1995] Tao Jiang, Lusheng Wang, and Kaizhong Zhang.  Alignment of trees – an alternative to tree edit.  _Theor. Comp. Sci._ , 143:137–148, 1995.  10.1016/0304-3975(95)80029-9.
  * Just [2001] Winfried Just.  Computational complexity of multiple sequence alignment with SP-score.  _J. Comp. Biol._ , 8:615–623, 2001.  10.1089/106652701753307511.
  * Katoh et al. [2005] Kazutaka Katoh, Kei-ichi Kuma, Hiroyuki Toh, and Takashi Miyata.  MAFFT version 5: improvement in accuracy of multiple sequence alignment.  _Nucleic Acids Res._ , 33:511–518, 2005.  10.1093/nar/gki198.
  * Kececioglu [1993] J. D. Kececioglu.  The maximum weight trace problem in multiple sequence alignment.  In _Proceedings of the 4th Symposium on Combinatorial Pattern Matching_ , volume 684 of _Lecture Notes Comp. Sci._ , pages 106–119, Berlin, 1993. Springer.
  * Kececioglu and Starrett [2004] John Kececioglu and Dean Starrett.  Aligning alignments exactly.  In Philip E. Bourne and Dan Gusfield, editors, _Proceedings of the 8th ACM Conference on Research in Computational Molecular Biology (RECOMB)_ , pages 85–96, New York, NY, 2004. ACM.  10.1145/974614.974626.
  * Konagurthu et al. [2004] A. S. Konagurthu, J. Whisstock, and P. J. Stuckey.  Progressive multiple alignment using sequence triplet optimization and three-residue exchange costs.  _J. Bioinf. and Comp. Biol._ , 2:719–745, 2004.  10.1142/S0219720004000831.
  * Kondrak [2000] Grzegorz Kondrak.  A new algorithm for the alignment of phonetic sequences.  In _Proceedings of NAACL 2000 1st Meeting of the North American Chapter of the Association for Computational Linguistics_ , pages 288–295, San Francisco, CA, USA, 2000. Morgan Kaufmann Publishers Inc.  10.1.1.19.9698.  URL http://aclweb.org/anthology/A00-2038.
  * Kruspe and Stadler [2007] Matthias Kruspe and Peter F. Stadler.  Progressive multiple sequence alignments from triplets.  _BMC Bioinformatics_ , 8:254, 2007.  10.1186/1471-2105-8-254.
  * Larkin et al. [2007] Mark A Larkin, Gordon Blackshields, N P Brown, R Chenna, Paul A McGettigan, Hamish McWilliam, Franck Valentin, Iain M Wallace, Andreas Wilm, Rodrigo Lopez, J D Thompson, T J Gibson, and D. G. Higgins.  Clustal W and Clustal X version 2.0.  _Bioinformatics_ , 23:2947–2948, 2007.  10.1093/bioinformatics/btm404.
  * Lee [2003] Christopher Lee.  Generating consensus sequences from partial order multiple sequence alignment graphs.  _Bioinformatics_ , 19:999–1008, 2003.  10.1093/bioinformatics/btg109.
  * Lee et al. [2002] Christopher Lee, Catherine Grasso, and Mark F. Sharlow.  Multiple sequence alignment using partial order graphs.  _Bioinformatics_ , 18:452–464, 2002.  10.1093/bioinformatics/18.3.452.
  * Lipman et al. [1989] David J Lipman, Stephen F Altschul, and John D Kececioglu.  A tool for multiple sequence alignment.  _Proc. Natl. Acad. Sci. USA_ , 86:4412–4415, 1989.  10.1073/pnas.86.12.4412.
  * Malde and Furmanek [2013] Ketil Malde and Tomasz Furmanek.  Increasing sequence search sensitivity with transitive alignments.  _PloS one_ , 8:e54422, 2013.  10.1371/journal.pone.0054422.
  * Manthey [2003] Bodo Manthey.  Non-approximability of weighted multiple sequence alignment.  _Theor. Comp. Sci._ , 296:179–192, 2003.  10.1007/3-540-44679-6_9.
  * Möhl et al. [2010] Mathias Möhl, Sebastian Will, and Rolf Backofen.  Lifting prediction to alignment of RNA pseudoknots.  _J Comput Biol._ , 17:429–442, 2010.  10.1089/cmb.2009.0168.
  * Morgenstern [1999] Burkhard Morgenstern.  DIALIGN 2: improvement of the segment-to-segment approach to multiple sequence alignment.  _Bioinformatics_ , 15:211–218, 1999.  10.1093/bioinformatics/15.3.211.
  * Morgenstern et al. [1999] Burkhard Morgenstern, Jens Stoye, and Andreas W. M. Dress.  Consistent equivalence relations: a set-theoretical framework for multiple sequence alignments.  Technical report, University of Bielefeld, FSPM, 1999.
  * Needleman and Wunsch [1970] Saul B Needleman and Christian D Wunsch.  A general method applicable to the search for similarities in the amino acid sequence of two proteins.  _J. Mol. Biol._ , 48:443–453, 1970.  10.1016/0022-2836(70)90057-4.
  * Notredame et al. [2000] Cédric Notredame, Desmond G Higgins, and Jaap Heringa.  T-coffee: a novel method for fast and accurate multiple sequence alignment.  _Journal of molecular biology_ , 302:205–217, 2000.  10.1006/jmbi.2000.4042.
  * Otto et al. [2011] Wolfgang Otto, Peter F. Stadler, and Sonja J. Prohaska.  Phylogenetic footprinting and consistent sets of local aligments.  In R. Giancarlo and G. Manzini, editors, _CPM 2011_ , volume 6661 of _Lecture Notes in Computer Science_ , pages 118–131, Heidelberg, Germany, 2011. Springer-Verlag.  10.1007/978-3-642-21458-5_12.
  * Rautiainen and Marschall [2017] Mikko Rautiainen and Tobias Marschall.  Aligning sequences to general graphs in $O(V+mE)$ time.  Technical report, bioRxiv, 2017.
  * Retzlaff and Stadler [2018] Nancy Retzlaff and Peter F. Stadler.  Partially local multi-way alignments.  _Math. Comp. Sci._ , 12:207–234, 2018.  10.1007/s11786-018-0338-4.
  * Sankoff and Kruskal [1983] David Sankoff and Joseph Kruskal, editors.  _Time Warps, String Edits and Macromolecules: the theory and practice of Sequence Comparison_.  Addison-Wesley, London, U.K., 1983.
  * Smith and Waterman [1981] Temple F Smith and Michael S Waterman.  Comparison of biosequences.  _Adv. Appl. Math._ , 2:482–489, 1981.  10.1016/0196-8858(81)90046-4.
  * Steiner et al. [2011] Lydia Steiner, Peter F Stadler, and Michael Cysouw.  A pipeline for computational historical linguistics.  _Language Dynamics & Change_, 1:89–127, 2011.  10.1163/221058211X570358.
  * Stoye et al. [1997] Jens Stoye, Vincent Moulton, and Andreas W M Dress.  DCA: an efficient implementation of the divide-and-conquer approach to simultaneous multiple sequence alignment.  _Comput. Appl. Biosci._ , 13:625–626, 1997.  10.1093/bioinformatics/13.6.625.
  * Tiepmar and Heyer [2017] Jochen Tiepmar and Gerhard Heyer.  An overview of canonical text services.  _Linguistics Literature Studies_ , 5:132–148, 2017.  10.13189/lls.2017.050209.
  * Vaddadi et al. [2017] Kavya Vaddadi, Naveen Sivadasan, Kshitij Tayal, and Rajgopal Srinivasan.  Sequence alignment on directed graphs.  Technical report, bioRxiv, 2017.
  * Velandia-Huerto et al. [2016] Cristian A Velandia-Huerto, Sarah J Berkemer, Anne Hoffmann, Nancy Retzlaff, Liliana C Romero Marroquín, Maribel Hernández Rosales, Peter F Stadler, and Clara I Bermúdez-Santana.  Orthologs, turn-over, and remolding of tRNAs in primates and fruit flies.  _BMC Genomics_ , 17:617, 2016.  10.1186/s12864-016-2927-4.
  * Wang and Jiang [1994] L Wang and T Jiang.  On the complexity of multiple sequence alignment.  _J Comput Biol_ , 1:337–348, 1994.  10.1089/cmb.1994.1.337.
  * Wareham [1995] H T Wareham.  A simplified proof of the NP- and MAX SNP-hardness of multiple sequence tree alignment.  _J Comput Biol._ , 2:509–514, 1995.  10.1089/cmb.1995.2.509.
  * Wolff [2000] J G Wolff.  Syntax, parsing and production of natural language in a framework of information compression by multiple alignment, unification and search.  _J. Universal Comp. Sci._ , 6(8):781–829, 2000\.  10.3217/jucs-006-08-0781.