Generalized Fibonacci Cubes Based on Swap and Mismatch Distance

The $n$-dimensional hypercube, $Q_n$, is the well-known graph whose vertices are in correspondence with the $2^n$ words of length $n$ over the binary alphabet $\{0,1\}$ and two vertices are connected by an edge if the corresponding words differ in one position, that is, if their Hamming distance is 1. Hence, the distance (number of edges in a minimal path) between two vertices in the graph is the Hamming distance of the corresponding words. The notion of hypercube has been extensively investigated because it is used to design interconnection networks (cf. [13, 17]) and also finds applications in theoretical chemistry (cf. [27] and [20, 24] for surveys). However, the critical limitation of the hypercube lies in its exponential growth in size, specifically in the number of vertices. Exploring some of its isometric subgraphs can improve efficiency. A subgraph of the $n$-dimensional hypercube is isometric to $Q_n$ if the distance between any pair of vertices in such subgraphs is the same as the distance in the complete hypercube. With this aim, in 1993, Hsu introduced the Fibonacci cubes [21], obtained from $Q_n$ by selecting only those vertices that do not contain $11$ as a factor. They have a Fibonacci number of vertices making them useful in applications to reduce the complexity and to limit resources. They have many remarkable properties, also related to Fibonacci numbers (cf. [15]).

In 2012, Generalized Fibonacci cubes have been defined by means of a binary word $f$; the graph $Q_n(f)$ is a subgraphs of $Q_n$ whose vertices do not contain $f$ as a factor, i.e. the vertices are $f$-free binary words [22]. Then, the property of $Q_n(f)$ being an isometric subgraph of $Q_n$ is related to some combinatorial properties of the avoided word $f$ that in such cases is called isometric. More formally, a binary word $f$ is isometric (or Ham-isometric) when, for any $n\ge 1$, $Q_n(f)$ is an isometric subgraph of $Q_n$, and non-isometric, otherwise [25]. The definition can also be done without mentioning graphs and only in terms of the Hamming distance. A word $f$ is Ham-isometric, if for any pair of $f$-free words $u$ and $v$ of the same length, $u$ can be transformed into $v$ by a minimal sequence of symbol replacements that each time produce an $f$-free word, as well. Binary Ham-isometric words have been characterized in [23, 25, 35, 38, 39] and research on the topic remains very active [11, 36, 37, 12, 6, 7, 16, 8, 9, 4, 10].

Over the years, many variations of the hypercube have been introduced to enhance certain features. For example, folded hypercubes (cf. [18]) and enhanced hypercubes (cf. [32]) have been defined by adding some edges to the original structure, providing several advantages in terms of topological properties. Motivated by the same reasons, we introduced a type of generalized hypercube that employs a different distance, enabling the definition of isometric subgraphs. The inspiration and motivation came from many applications of computational biology, where many processes involve complex transformations and it is natural to consider not only replacement operations but also swap operations that exchange two adjacent different symbols in a word. The edit distance based on swaps and replacements is worth considering [1, 19, 29] instead of the Hamming distance. Actually, this distance was defined in the 70s by Wagner and Fischer [34, 33] who proved that it can be efficiently computed.

In [3] this distance is referred to as tilde-distance, since the $\sim$ symbol somehow evokes the swap operation. In [2], the tilde-distance is taken as the base to define the tilde-hypercube, ${\tilde{Q}}_n$; it has again all the $n$-binary strings as vertices, but two vertices are adjacent if the tilde-distance is equal to 1. This implies that ${\tilde{Q}}_n$ has more edges than $Q_n$; in particular, since a swap corresponds to two replacements of consecutive characters, some vertices at distance $2$ in $Q_n$, become adjacent in ${\tilde{Q}}_n$.

This paper surveys most of the recent results on tilde-isometric words and generalized tilde-Fibonacci cubes. In particular, we collect the main definitions to give a recursive construction of tilde-hypercubes and enumerate their edges and vertices. Then, the subgraphs ${\tilde{Q}}_n(f)$ of the tilde-hypercubes are considered. They are obtained by selecting the vertices corresponding to $f$-free words, for a given word $f$. It is also reported the characterization of words $f$ such that ${\tilde{Q}}_n(f)$ is an isometric subgraph of ${\tilde{Q}}_n$ as proved in [5]. We also exhibit an infinite family of tilde-isometric words that are not Hamming-isometric and vice versa. Finally, the last part of the paper focuses on the word $f=11$, that is both a Hamming- and a tilde-isometric word; the subgraph ${\tilde{Q}}_n(11)$ is referred to as the tilde-Fibonacci cube. We describe its recursive construction and present new simple results on diameter and radius that prove that the tilde-Fibonacci cubes are self-centered graphs.

In this paper we focus only on the binary alphabet $\mathrm{\Sigma }=\{0,1\}$. A word (or string) $w$ over $\mathrm{\Sigma }$ of length $|w|=n$, is $w=a_1{a}_2\mathrm{\cdots }{a}_n$, where $a_1,a_2,\mathrm{\dots },a_n$ are symbols in $\mathrm{\Sigma }$. The set of all words over $\mathrm{\Sigma }$ is denoted ${\mathrm{\Sigma }}^{\ast }$. Finally, $ϵ$ denotes the empty word and ${\mathrm{\Sigma }}^{+}={\mathrm{\Sigma }}^{\ast }-\{ϵ\}.$ For any word $w=a_1{a}_2\mathrm{\cdots }{a}_n$, the reverse of $w$ is the word $w^{rev}=a_n{a}_{n-1}\mathrm{\cdots }{a}_1$. If $x\in \mathrm{\Sigma }$, $\overline{x}$ denotes the opposite of $x$, i.e $\overline{x}=1$ if $x=0$ and vice versa. Then we define the complement of $w$ the word $\overline{w}={\overline{a}}_1{\overline{a}}_2\mathrm{\cdots }{\overline{a}}_n$.

Let $w[i]$ denote the symbol of $w$ in position $i$, i.e. $w[i]=a_i$. Then, $w[i..j]=a_i\mathrm{\dots }{a}_j$, for $1\le i\le j\le n$, denotes a factor $u$ of $w$ of length $j-i+1$ placed from the $i$-th to the $j$th position of $w$. We say that $I=[i..j]$ is the interval where the factor $u$ occurs in $w$. The prefix (resp. suffix) of $w$ of length $l$, with $1\le l\le n-1$ is ${\mathrm{pre}}_l(w)=w[1..l]$ (resp. ${\mathrm{suf}}_l(w)=w[n-l+1..n]$). When ${\mathrm{pre}}_l(w)={\mathrm{suf}}_l(w)=u$ then $u$ is here referred to as an overlap of $w$ of length $l$; in other frameworks, it is also called the border, or bifix of $w$ (cf. [30]). A word $w$ avoids a word $f$ if $w$ does not contain $f$ as a factor: we also say that $w$ is $f$-free.

An edit operation is a function $O:{\mathrm{\Sigma }}^{\ast }\to {\mathrm{\Sigma }}^{\ast }$ that transforms a word into another one. Let $OP$ be a set of edit operations. The edit distance of words $u,v\in {\mathrm{\Sigma }}^{\ast }$, with respect to the set $OP$, is the minimum number of edit operations in $OP$ needed to transform $u$ into $v$.

In this paper, we consider the edit distance that uses only swap and replacement operations. Note that these operations preserve the length of the word.

Note that one swap corresponds to two replacements of consecutive symbols.

The Hamming distance ${\mathrm{dist}}_H(u,v)$ of equal-length words $u,v\in {\mathrm{\Sigma }}^{\ast }$ is defined as the minimum number of replacements needed to obtain $v$ from $u$.

Let $G=(V(G),E(G))$ be a graph, $V(G)$ be the set of its nodes and $E(G)$ be the set of its edges. The distance of $u,v\in V(G)$, ${\mathrm{dist}}_G(u,v)$, is the length of the shortest path that connects $u$ and $v$ in $G$. A subgraph $S=(V(S),E(S))$ of a (connected) graph $G$ is an isometric subgraph if for any $u,v\in V(S)$, ${\mathrm{dist}}_S(u,v)={\mathrm{dist}}_G(u,v)$.

The $n$-hypercube, or binary $n$-cube, $Q_n$, is a graph with $2^n$ vertices, labeled with the words of length $n$ and edges connecting two vertices $u$ and $v$ in $Q_n$ when their labels differ exactly in $1$ position, i.e. when ${\mathrm{dist}}_H(u,v)=1$. Therefore, ${\mathrm{dist}}_{Q_n}(u,v)={\mathrm{dist}}_H(u,v)$.

Denote by $f_n$ the $n$-th Fibonacci number, defined by $f_1=1,f_2=1$ and $f_i=f_{i-1}+f_{i-2}$, for $i\ge 3$. The Fibonacci cube (cf. [22]) $F_n$ of order $n$ is the subgraph of $Q_n$ whose vertices are binary words of length $n$ avoiding the factor $11$. It is well known that $F_n$ is an isometric subgraph of $Q_n$ (cf. [24]).

One of the main properties of $Q_n$ and $F_n$ is their recursive structure that have been extensively studied (cf. [21, 28, 26, 24]).

The following results are well-known, but are hereby stated for future reference.

In other terms, if the number of vertices $N=2^n$ of the hypercube is taken as main parameter, the number of edges of a hypercube with $N$ vertices is $(N\log N)/2$.

The sequence $|E(F_n)|$ is Sequence A001629 in [31]. Hence, the number of edges of a Fibonacci cube with $N$ vertices, $N=f_{n+2}$, is $O(N\log N)$, asymptotically equal to the number of edges of a hypercube with the same number of vertices.

In order to generalize the notion of Fibonacci cube, one can consider the subgraphs of the $n$-hypercube whose nodes are $f$-free, for some word $f\in {\mathrm{\Sigma }}^{\ast }$, denoted by $Q_n(f)$, called generalized Fibonacci cubes. Of course, if , then $Q_n(f)=Q_n$; so it makes sense to consider $n\ge |f|$. Unfortunately, not all the words $f$ make $Q_n(f)$ an isometric subgraph of $Q_n$. The words having this property have been widely studied (cf. [23, 25, 35, 38, 39]). These words are in fact called isometric words, because they reflect on this isometry property on the corresponding graphs.

Under the combinatorial point of view, isometric words are defined as follows. A word $f\in {\mathrm{\Sigma }}^{\ast }$ is Ham-isometric (or simply isometric) if and only if $Q_n(f)$ is an isometric subgraph of $Q_n$. A word that is not Ham-isometric is said to be Ham-non-isometric. In terms of transformations, isometric words can be characterized by the following:

A word $w$ has a $2$-error overlap if there exists $l\le |w|$ such that ${\mathrm{pre}}_l(w)$ and ${\mathrm{suf}}_l(w)$ have Hamming distance $2$. Then, the following characterization of Ham-non-isometric words is proved (cf. [35]).

In this section, the edit distance based on swap and replacement operations is considered. In [3] it is called tilde-distance and denoted by $dis{t}_{\sim }$ . According to this definition one can define the $n$-tilde-hypercube. We start with the definition of tilde-distance.

Note that for all $u,v\in {\mathrm{\Sigma }}^{\ast }$, ${\mathrm{dist}}_{\sim }(u,v)\le {\mathrm{dist}}_H(u,v)$, since a swap is a shortcut for two adjacent replacements.

In order to describe the sequence of the operations that are used to compute the tilde-distance of two words, we need the following definition of a tilde-transformation:

A tilde-transformation $(w_0,w_1,\mathrm{\dots },w_d)$ from $u$ to $v$ with $dis{t}_{\sim }(u,v)=d$ is associated to a sequence of $d$ operations $(O_{i_1},O_{i_2},\mathrm{\dots },O_{i_d})$ such that, for any $k=1,\mathrm{\dots },d$, $O_{i_k}\in \{R_{i_k},S_{i_k}\}$ and $w_k=O_{i_k}(w_{k-1})$; it can be graphically represented as follows:

With a little abuse of notation, in the sequel we will refer to a tilde-transformation both as a sequence of words and as a sequence of operations. Furthermore, as a consequence of the definition, in a tilde-transformation, the positions $i_1$, $i_2$, $\mathrm{\dots }$, $i_d$ are all distinct.
In the following we give some examples that show some special features of tilde-transformations, which never occur when transformations using only replacements are considered. This highlights, on the one hand, the richness of new situations that arise from introducing the swap operation, and on the other hand, it anticipates the need for new and more sophisticated techniques to handle these increasingly complex scenarios. First of all, we point out that when only replacements are used, the different transformations from $u$ to $v$ use the same set of operations, possibly applied in a different order. This is not the case for the different tilde-transformations between two words. The following two examples show two singular cases of different tilde-transformations which use different sets of operations.

Based on the definition of tilde-distance, a natural extension of the concept of $n$-hypercube is given in [2] as follows:

Figure 1 shows the tilde-hypercubes of order $1,2,3,4$.

The following lemma is the main tool for exhibiting a recursive definition of the tilde-hypercube, in analogy with the classical hypercube.

In analogy with the $n$-hypercube avoiding a word based on the Hamming distance, referred to as generalized Fibonacci cube in [22], in this section, we consider the $n$-tilde-hypercube avoiding a word, based on the tilde-distance, here named generalized tilde-Fibonacci cubes.

In [2] the following definition is given:

We are interested in those words $f$ such that ${\tilde{Q}}_n(f)$ is an isometric subgraph of ${\tilde{Q}}_n$, i.e. the distance of two vertices of ${\tilde{Q}}_n(f)$ is equal to the tilde-distance of the corresponding labels.

The following proposition characterizes isometric words re-stating the definition of isometric word under a combinatorial point of view.

In order to show that a word is tilde-non-isometric it is sufficient to exhibit a pair $(u,v)$ of $f$-free words such that all the tilde-transformations from $u$ to $v$ are not $f$-free. Such pair of words is called a pair of tilde-witnesses. More challenging is to prove that a word is tilde-isometric.

The following straightforward property of tilde-isometric binary words is very helpful to simplify proofs and computations.

In view of Remark 22 , we will focus on words starting with 1.

The characterization of Ham-isometric words given in [38] and here reported as Proposition 5, uses the notion of $2$-error overlap. In this section we introduce the corresponding definition that refers to the tilde-distance. Tilde-error overlaps will have a main role in the characterization of tilde-isometric words but the presence of swap operations will force us to handle them with care.

For our proofs, given a word $f$ with a $q$-tilde-error overlap of length $\mathrm{\ell }$, we will study the tilde-transformations $\tau$ from ${\mathrm{pre}}_{\mathrm{\ell }}(f)$ to ${\mathrm{suf}}_{\mathrm{\ell }}(f)$ with $q$ operations. For this reason, it is useful to refer to the alignment of the two strings ${\mathrm{pre}}_{\mathrm{\ell }}(f)$ to ${\mathrm{suf}}_{\mathrm{\ell }}(f)$. Furthermore, for our purpose, it is relevant to consider also the bits adjacent to a tilde-error overlap of a word. For this reason, we introduce the following notation.

Let $f$ be a word in ${\{0,1\}}^{\ast }$ and $\$$ be a symbol different from $0,1$, here used as delimiter of a word, that by definition “matches” any symbol of the word. Consider $f$ with its delimiters $\$f\$$. A $q$-tilde-error overlap of length $\mathrm{\ell }$ is denoted by $\left(\genfrac{}{}{0pt}{}{\$xb}{ay\$}\right)$ where $xb$, $ay$ are a prefix and a suffix, respectively, of $f$, $a,b\in \mathrm{\Sigma }$, $x,y\in {\mathrm{\Sigma }}^{\ast }$ with $|x|=|y|=\mathrm{\ell }$, and ${\mathrm{dist}}_{\sim }(\$xb,ay\$)={\mathrm{dist}}_{\sim }(x,y)=q$. This notation makes evident the fact that in $f$ the prefix $x$ is followed by $b$ and the suffix $y$ is preceded by $a$. Moreover, a $q$-tilde-error overlap $\left(\genfrac{}{}{0pt}{}{\$xb}{ay\$}\right)$ is sometimes factorized into blocks to highlight the significant parts. For example, the $2$-tilde-error overlap in Example 24 is denoted by $\left(\genfrac{}{}{0pt}{}{\$1}{01}\right)\left(\genfrac{}{}{0pt}{}{1011}{0110}\right)\left(\genfrac{}{}{0pt}{}{10}{1\$}\right)$ because ${\mathrm{dist}}_{\sim }(110111,101101)=2={\mathrm{dist}}_{\sim }(1011,0110)$.

In the sequel, we will be interested in the specific case of $1$-tilde-error overlap where the single error in the alignment is a swap and in all the cases of $2$-tilde-error overlaps. Consider a $2$-tilde-error overlap of $f$ of shift $r$, length $\mathrm{\ell }=n-r$, and let $(O_i,O_j)$, , be a tilde-transformation from ${\mathrm{pre}}_{\mathrm{\ell }}(f)$ to ${\mathrm{suf}}_{\mathrm{\ell }}(f)$. Observe that the positions in ${\mathrm{pre}}_{\mathrm{\ell }}(f)$ modified by $O_i$ are either $i$ or both $i$ and $i+1$, following that $O_i$ is a replacement or a swap. Hence, the number of the positions modified by $O_i$ and $O_j$ may be 2, 3 or 4. Fig. 2 shows a word $f$ with its $2$-tilde-error overlap of shift $r$ and length $\mathrm{\ell }=n-r$. With our notation, the $2$-tilde-error overlap is $\left(\genfrac{}{}{0pt}{}{\$w_{2}1w1w_{3}b}{a{w}_{2}0w0w_3\$}\right)$ in the figure on the left and $\left(\genfrac{}{}{0pt}{}{\$w_{2}10w1w_{3}b}{a{w}_{2}01w0w_3\$}\right)$ in the figure on the right, where $b$ is the first letter of $w_4$ and $a$ the last letter of $w_1$. A tilde-transformation from ${\mathrm{pre}}_{\mathrm{\ell }}(f)$ to ${\mathrm{suf}}_{\mathrm{\ell }}(f)$ is given by $(O_i,O_j)=(R_i,R_j)$ in the first case and by $(O_i,O_j)=(S_i,R_j)$ in the second case. We say that a $2$-tilde-error overlap has non-adjacent errors when there is at least one character interleaving the positions modified by $O_i$ and those modified by $O_j$.

The $2$-tilde-error overlap $\left(\genfrac{}{}{0pt}{}{\$x}{ax}\right)\left(\genfrac{}{}{0pt}{}{100}{001}\right)\left(\genfrac{}{}{0pt}{}{yb}{y\$}\right)$ is also considered as having non-adjacent errors because it admits the tilde-transformation $(O_i,O_j)=(R_i,R_{i+2})$, despite it has also the other tilde-transformation $(O_i,O_j)=(S_i,S_{i+1})$.

In all the other cases, we say that the $2$-tilde-error overlap has adjacent errors.

Let us state the characterization of tilde-isometric words in terms of special configurations in their overlap proved in [5].

Thanks to Theorem 25, we can classify any word as isometric or non-isometric. In the following, several examples are given. The following are two examples of words with a $2$-tilde-error overlap with adjacent errors; the first one is tilde-isometric, the second one is tilde-non-isometric.

The following example shows an infinite family of words that are tilde-isometric and Ham-non-isometric.

The next corollary shows that there exist Ham-isometric words that are not tilde-isometric. This fact, together with Example 28, proves that the families of Ham-isometric and tilde-isometric words are incomparable.

Theorem 25 allows also to give light to isometric subgraphs of ${\tilde{Q}}_n$ avoiding a word. In fact they are those avoiding a tilde-isometric word.

In analogy with the definition of Fibonacci cubes introduced by Hsu [21], we give the following:

Figure 3 shows the tilde-Fibonacci cube of order $1,2,3,4$.

From Theorem 25 and Proposition 19, the following corollary derives.

Further, about other hypercubes avoiding words of length 2, we have the following:

The tilde Fibonacci cube admits also a recursive construction that allows one to enumerate its edges.

By Proposition 2, $|V({\tilde{F}}_n)|=|V(F_n)|=f_{n+2}$. Among these vertices, $f_{n+1}$ end with a $0$ and $f_n$ end with a $1$. Figure 3 shows the tilde-Fibonacci cube of order $4$.

The paper surveys some recent results on isometric words with respect to the edit distance that allows swap and replacement operations, here referred to as tilde-distance. Moreover, the tilde-hypercube and the tilde-Fibonacci cube are presented as a generalization of the corresponding classical notions, with the tilde-distance in place of the Hamming distance.

Compared with the setting of Hamming distance, all the problems appear to be more complicated since, when using swaps, the order of performing the operations does matter. Nevertheless, isometric words and generalized Fibonacci cubes based on this tilde-distance open up new scenarios and present interesting new situations that surely deserve further investigation as it can serve as base for string and graph algorithmic developments.