Doubly-Periodic String Comparison

To our knowledge, the doubly-periodic LCS problem has not been considered before as a separate algorithmic problem; however, more general as well as more specific problems have been considered. In particular, the problem includes as a special case the (singly)-periodic LCS problem, where only one of the input strings is periodic; the periodic structure of the other strings, if one exists, is ignored. Tiskin [27] gave an algorithm for this problem, called “wraparound combing”. Given a string $a$ of length $m$, and string $b^{\mathrm{\ell }}$, which is an $\mathrm{\ell }$-repeat of string $b$ of length $n$, the algorithm runs in time $O(mn)$. The algorithm’s construction is based on the framework that will be described in the next section. This algorithm was rediscovered independently by Bukh and Cox [8].

For the more general setting, a periodic string can be considered as a special case of a string compressed by a straight-line program (SLP). In particular, string $a^k$, which is a $k$-repeat of string $a$ of length $m$, can be represented by an SLP of length $O(m+\log k)$, and similarly for $b^{\mathrm{\ell }}$. Therefore, any algorithm for LCS on SLP-compressed strings implies an algorithm for the doubly-periodic LCS problem as a special case. Unfortunately, this more general problem was proved to be NP-hard by Lifshits and Lohrey [17, 18]. Hermelin et al. [13] and Gawrychowski [12], again using Tiskin’s framework, gave algorithms for the still more general weighted alignment problem, which includes LCS as a special case, on a pair of SLP-compressed strings $a$, $b$ of total compressed length $r$. The algorithms’ running time is parameterised by the strings’ total plain length $R$ (which, in general, may be exponential in $r$). The algorithm of [13] runs in time $O\left(R\log (R/r)\cdot r\right)$, which is reduced in [12] to $O\left(R{(\log (R/r))}^{1/2}\cdot r\right)$. For our problem, the worst-case running time is given by substituting $R=mk+n\mathrm{\ell }$, $r=(m+\log k)+(n+\log \mathrm{\ell })$. The algorithm proposed in this paper is a substantial improvement on this approach.

The remainder of this paper is organised as follows. In Section 2, we give a summary (without proofs) of Tiskin’s framework [25, 24, 26, 28] for the ordinary and singly-periodic LCS problem. In Section 3, we make explicit the algebraic definitions (affine permutations, affine sticky braids) behind the singly-periodic case, that were not stated explicitly before, and add a few more components to the framework (such as the concept of $\mathrm{\Phi }\mathrm{\Gamma }$-decomposition) that are required by our results. In Section 4, we present the main results, including fast algorithms for sticky multiplication of affine permutations, and for computing the LCS of doubly-periodic strings.

Alongside integer numbers, we will be using half-integers extensively. We denote half-integers by hatted letters ($\widehat{ı}$, $\widehat{ȷ}$, etc.), and the set of all half-integers is denoted $\widehat{\mathbb{Z}}$. Given an integer number $i$, $i^{-}=i-\frac{1}{2}$ and $i^{+}=i+\frac{1}{2}$ are the half-integers adjacent to it. Given a half-integer $\widehat{ı}$, integers ${\widehat{ı}}^{+}$, ${\widehat{ı}}^{-}$ are defined analogously.

We denote by $⟨m:n⟩$ the set of half-integers strictly between integer numbers $m$, $n$, and we denote usual integer intervals by $[m:n]$. The space to either side of the colon may be left empty if the corresponding boundary is obvious from the context: for example, $0$, $\pm \mathrm{\infty }$, the dimension of the matrix, etc. A semicolon (e.g. $[k:\mathrm{\ell };m:n]$) denotes the Cartesian product of the corresponding intervals.

We will be indexing string characters with half-integers, because this way the spaces between characters are indexed with integers, which will become convenient further. Given a string $a$, $a⟨\widehat{ı}⟩$ is its character at position $\widehat{ı}$, and $a⟨i:j⟩$ is its substring of length $j-i$.

We will also be considering permutations of half-integers and the corresponding permutation matrices, indexed with half-integers. We specify a matrix element by $M⟨\widehat{ı};\widehat{ȷ}⟩$, when it is indexed with half-integers, and by $M[i;j]$, when it is indexed with integers. The numbers in the indices may be replaced with intervals if we want to specify a submatrix.

Various forms of string periodicity are very common in string combinatorics and algorithms. We define periodic strings as follows.

Unless indicated otherwise, in this section we consider algorithmic problems that take strings $a⟨0:m⟩$, $b⟨0:n⟩$ as input.

Although global comparison (full string against full string) and fully-local comparison (all substrings against all substrings) are the two most common approaches to comparing strings, another important type of string comparison lies “in between”.

A standard approach in LCS algorithms is to represent common subsequences of two strings as paths in a certain grid graph with added diagonal edges.

The LCS of two strings $a$, $b$ corresponds to the path from the top left corner to the bottom right corner of ${𝖦}_{a,b}[0:m;0:n]$ containing the most diagonal edges. The string-substring LCS of $a$, $b⟨i:j⟩$ corresponds to the path with the most diagonal edges from the top left to the bottom right corner of the subgrid enclosed by the substring $b⟨i:j⟩$, denoted ${𝖦}_{a,b}[0:m;i:j]$. Subgrids corresponding to the three other components of the semi-local LCS problem are defined analogously.

The analysis of boundary-to-boundary paths in an LCS grid can be simplified by padding string $b$ with $m$ wildcard characters (which is a character matching all other characters) on both sides. Let $b^{\text{pad}}⟨-m:m+n⟩={\text{?}}^{m}b{\text{?}}^m$. Semi-local common subsequences then correspond only to paths connecting the top and the bottom boundaries of the $m\times (2m+n)$ padded LCS grid ${𝖦}_{a,b^{\text{pad}}}[0:m;-m:m+n]$. It is convenient to store scores of such paths in a specially defined matrix.

Let $⟨I⟩$, $⟨J⟩$ be finite intervals of half-integers.

We define two fundamental operations on matrices: dominance summation and taking cross-differences. For the first operation, it will be convenient to always assume the argument matrix to be indexed by half-integers, and the resulting matrix by integers; for the second operation, the index types of the argument matrix and the resulting matrix are reversed.

At the centre of the framework is an efficient algorithm for sticky multiplication of permutation matrices, proposed by Tiskin [28]; a similar algorithm was proposed independently by Sakai [23].

We now take a complementary view on the sticky multiplication monoid of permutation matrices, defining it by an algebraic formalism of generators and relations.

Just as the elements of the classical braid group ${𝔹}_n$ are represented visually by braids, an element of ${ℍ}_n$ can be represented by a sticky braid of degree $n$: a set of $n$ vertically-monotone curves (called strands) connecting disjoint pairs between two sets of $n$ points, each set drawn on a separate horizontal line. The strands’ crossings correspond to the monoid’s generators. Such a representation is not unique; two sticky braids are considered to be equivalent, if they represent the same element of ${ℍ}_n$, i.e. they can be obtained from one another by applying the monoid’s relations.

Two sticky braids of the same degree can be composed in the same way as classical braids: we draw one braid above the other, identifying the bottom nodes of the top braid with the respective top nodes of the bottom braid, and then we join up each pair of strands that became incident.

From the general theory of Coxeter monoids, it is well-known that the elements of the sticky braid monoid ${ℍ}_n$ correspond bijectively to the elements of the symmetric group ${𝕊}_n$, and that any reduced word (minimal-length word in the generators) for an elements in one of these structures is also a reduced word for the corresponding element in the other [29] (see also [14]). For completeness, we now restate these facts in the language of sticky braids.

Note that the composition of two reduced sticky braids may not in general be reduced. The following two propositions on sticky braid reduction are a consequence of the general Coxeter theory (see e.g. [7]).

A reduced sticky braid can be associated with a permutation by canonical projection $\pi :{ℍ}_n\to {𝕊}_n$: a strand connecting top node $i$ and bottom node $j$ in the braid corresponds to an argument-image pair $i\mapsto j$.

A surprising key theorem of the framework states that the two monoids we have defined are in fact isomorphic. This has been rediscovered independently by Pflueger [22].

The isomorphism in the above theorem is established by identifying formal generator ${\tau }_i$ with a transposition, i.e. the permutation of interval $⟨0:n⟩$ that transposes $i^{-}$ with $i^{+}$, and leaves the other elements unchanged.

Given a (generally unreduced) sticky braid, an equivalent reduced one can be obtained by applying the following iterative combing procedure. We iterate over the braid’s transpositions from the top down (formally, along the word in the generators constituting the braid), removing those that create entanglements, while keeping the transpositions between pairs of strands that have not crossed previously. This procedure is an equivalence transformation on sticky braids, producing a reduced braid equivalent to the original one.

Iterative combing can also be used to perform sticky multiplication of permutations. Given permutations $P$, $Q$, we first represent them as reduced braids $ℬ(P)$, $ℬ(Q)$, picking arbitrary ones from the respective equivalence classes. We then compose these two braids and apply iterative combing to the composition (which may skip $ℬ(P)$ and start at the boundary between the two braids, since $ℬ(P)$ is already reduced). Finally, we take the canonical projection of the resulting braid as the product $P⊡Q$. Reflecting the asymmetric nature of this procedure, we can think of sticky multiplication of permutations $P$, $Q$ as reduction of the permutation $Q$ relative to $P$. We denote²²2Pflueger [22] develops a particularly elegant theory and notation for this concept of relative reduction; however, the above definition and notation will suffice for our purposes. the result of such a reduction by $P╱Q$. Formally, we have $P╱Q=P^{-1}\cdot \left(P⊡Q\right)$, where the inversion and the first multiplication are in ${𝕊}_n$, and the second multiplication in ${ℍ}_n$.

The definitions of the previous sections have a natural extension, from finite objects to analogous objects with an infinite periodic structure. Generally, extensions of such type are well-known in algebra, where the infinite periodic analogues of structures such as ${𝕊}_n$ or ${ℍ}_n$ are called affine (see e.g. [16, 19]); we borrow this term here.

Note that an affine permutation of degree $n$ is also affine for any degree that is multiple of $n$.

Pflueger [22] shows how the definitions of a permutation matrix (Definition 8), dominance-sums matrix (Definition 10), tropical multiplication (Definition 11), sticky multiplication (Definition 12) all extend naturally from the finite to the affine case.

A smooth transition from the finite objects and their properties to their affine counterparts stops with the Tiskin–Sakai algorithm for multiplication in ${ℍ}_n$ (Theorem 14): the algorithm depends crucially on the permutations and their matrices being finite, and does not seem to allow for an easy generalisation to ${\widetilde{ℍ}}_n$. However, an affine extension of the algorithm to ${ℍ}_n$ can still be obtained: this is one of the contributions of this paper.

An affine extension of the definition of the sticky braid monoid in Coxeter presentation (Definition 15) is by a standard but elegant trick. It is achieved by adding an extra generator to the presentation, and extending the relations to this new generator in a natural way.

Iterative combing and relative reduction extend directly to their affine counterparts.

Pflueger [22] has established the isomorphism between the two definitions ${\widetilde{ℍ}}_n$ given above, mirroring Theorem 19.

We now introduce some basic definitions for constructing and decomposing affine permutations.

From now on, we are concerned with affine permutations of a fixed degree $N$.

In other words, an affine permutation is finite-type iff it can be obtained by the affine replication of an ordinary (finite) permutation. Note that the inverse of a finite-type permutation is still finite-type, while the inverse of a Grassmannian permutation is not necessarily Grassmannian.

We finally are able to apply the algebraic framework presented in Subsections 2.3–2.5 to the SLCS problem introduced in Subsection 2.2; in doing so, we follow [24, 25].

The key property of SLCS matrices is captured by the following theorem.

The intuition behind Theorem 33 is as follows. Let $b^{\prime }$ be a substring of $b$. If substring $b^{\prime }$ is extended on either the left or the right by one character, then its LCS score against string $a$ either is unchanged, or increases by $1$, depending on whether or not the new character of $b^{\prime }$ can be matched to a character of $a$. The unit-anti-Monge property of matrix ${𝖧}_{a,b}$ reflects the fact that, as substring $b^{\prime }$ grows while $a$ is fixed, obtaining a matching for each new character becomes relatively harder. Each nonzero in the SLCS kernel ${𝖯}_{a,b}$ represents a unit obstacle to character matching: at such a point, extending $b^{\prime }$ independently on the left or on the right gives a new match, and a corresponding increase by $1$ in the LCS score; however, these two new matches are incompatible, so extending $b^{\prime }$ simultaneously on the left or on the right gives a total increase in the LCS score by $1$ instead of $2$. The above is only very general intuition, since “obtaining a match” for a given character is not absolute, but depends on the choice of a particular highest-scoring path through the LCS grid. Even more generally, one can think of the nonzeros in ${𝖯}_{a,b}$ as “the places where string-substring LCS score, as a function of the substring’s endpoints, is nonlinear”.

SLCS kernels, along with the Tiskin–Sakai sticky multiplication algorithm, provide the basis for a divide-and-conquer approach to the SLCS problem in Tiskin’s framework.

An analogous, slightly more technical statement holds for full SLCS kernels. As a basis for affine extension, Theorem 35 will be sufficient in its given form.

Just like a permutation can be represented by a sticky braid, an SLCS kernel can be represented with a sticky braid embedded in a special way in the LCS grid (both representations are only unique up to equivalence in ${ℍ}_n$).

Definition 36 implies that every cell in the grid is traversed by exactly two strands of an embedded braid, entering across the cell’s west and north edges, and leaving across the cell’s east and south edges (not necessarily in that order). A diagonal edge, if it exists, is never traversed by a strand. Thus, the strands never cross in a match cell, but may or may not cross in an mismatch cell.

Note that a saturated braid is generally unreduced. Upon reduction, such a braid corresponds precisely to the SLCS kernel.

The iterative combing procedure can be realised on an LCS grid in a straightforward way. We initialise an embedded braid as a saturated embedded braid, and then iterate over the cells in an arbitrary order compatible with the north-to-south and east-to west partial order of the cells. In a match cell, we do nothing; in a mismatch cell, we prevent the strands from becoming entangled in exactly the same way as in iterative combing on generic sticky braids. Just like with generic braids, an entanglement check can be performed in time $O(1)$, so the whole iterative combing procedure runs in time $O(mn)$.

We now consider an extension of the semi-local LCS problem to the inputs $a$, $b^{\mathrm{\infty }}$, where $a$ is an ordinary string, and $b^{\mathrm{\infty }}$ is an infinite repeat. The analogue for the SLCS problem for such a setting is the string-substring problem on $a$, $b^{\mathrm{\infty }}$; the other three components of the SLCS problem are not required. The definition of SLCS matrix extends naturally to its affine counterpart. The definitions of an SLCS kernel and an embedded braid also extend directly, except that

• $\mathrm{■}$

  we must assume that every character of $a$ appears in $b$ at least once (otherwise a character in $a$ not appearing in $b$ would create a spurious unattached strand in the embedded braid); this condition can obviously be guaranteed without loss of generality;

• $\mathrm{■}$

  every cell in the grid, either match or mismatch one, should be considered as giving a total skew of $1$ to the pair of strands passing through the cell. For a given character of $a$, a horizontal row of cells across a single period of the LCS grid will therefore give a skew of $1$ to every strand in the braid. The resulting affine braid across the whole grid will acquire a total skew of $m$, so the affine LCS kernel will be a skew-affine permutation with skew $m$, which we denote ${𝖯}_{a,b^{\mathrm{\infty }}}$.

Theorem 35 on string-substring LCS kernel composition extends to the affine setting with a proof that is vertually identical to the finite case (for now, without any claims on running time).

Here, the sticky product of skew-affine permutations is understood as in Remark 23.

The definitions of an LCS grid (Definition 4), an embedded braid (Definition 36) and a saturated braid (Definition 37) extend directly to the case of the inputs $a$, $b^{\mathrm{\infty }}$. In order for the iterative combing procedure to be realised on an infinite periodic LCS grid in such a setting, Tiskin [27] modified it to the following procedure, called wraparound combing. We initialise an affine embedded braid as a saturated affine embedded braid. We then iterate over the cells in the following order. In the outer loop, we iterate over the characters of $a$, moving north-to-south through the grid. Recall that we assume that every character of $a$ occurs in $b$ at least once; therefore, there will be a match cell in the row of the grid corresponding to the current character. In the inner loop, we iterate over one whole period of $b^{\mathrm{\infty }}$, beginning at a match cell in the current row (if there is more that one per period, one is chosen arbitrarily); note that the choice of the period may differ between the iterations of the outer loop. The combing within each cell of a period is now performed as in ordinary iterative combing, except that the entanglement check should now respect the infinite periodic structure of the grid. Such a check can still be performed in time $O(1)$, and the whole iterative combing procedure still runs in time $O(mn)$.

We reduce sticky multiplication of affine permutations $\tilde{P}$, $\tilde{Q}$ to sticky multiplication of finite permutations. The reduction is achieved by computing the sticky product of one fixed period of $\tilde{P}$, $\tilde{Q}$, taken with respect to $ran\tilde{P}=dom\tilde{Q}$, joined by one extra period on either side (in total, three periods are multiplied). We then take the restriction of the product to the original fixed period and replicate it infinitely, obtaining an affine permutation. We claim that this procedure is well-defined, and that the resulting permutation is $\tilde{P}⊡\tilde{Q}$. Formally, we describe this procedure using the concept of $\mathrm{\Gamma }\mathrm{\Phi }$-decomposition, see Algorithm 1.