Space-time Trade-offs for the LCP Array of Wheeler DFAs

The problem of computing matching statistics on a Wheeler DFA is defined as follows: given a pattern of length $m$ and a Wheeler DFA with $n$ states, determine the longest suffix of each prefix of $m$ that occurs in the graph (that is, that can be read by following some edges on the graph and concatenating the labels). This problem is a natural generalization of the problem of computing matching statistics on strings. Conte et al. [7] proved the following result:

We will show that if we only want to use linear space, then we can use Theorem 1.1 to obtain the following trade-off.

Wheeler graphs are a generalization of de Bruijn graphs; in particular, the compact representation of a Wheeler graph is a generalization of the BOSS representation of a de Bruijn graph [5], and our results on the LCP array also apply to a de Bruijn graph. Many assemblers [3, 24, 19, 27] consider all $k$-mers occurring in a set of reads and build a $k$-th order de Bruijn graph (on the alphabet $\Sigma=\{A,C,G,T\}$) to perform Eulerian sequence assembly [18, 25]. However, the choice of the parameter $k$ impacts the assembly quality, so some assemblers try several choices for $k$ [3, 24], which slows down the process because several de Bruijn graphs need to be built. In [4] it was shown that the $k$-order de Bruijn graph of $\mathcal{S}$ can be used to implicitly store the $k^{\prime}$-th order de Bruijn graph of $\mathcal{S}$ for every $k^{\prime}\leq k$, thus leading to a variable-order de Bruijn graph. The challenge is to navigate this implicit representation (that is, how to follow edges in a forward or backward fashion). In [4], it was shown that the navigation is possible by storing or by simulating an array $\overline{\mathsf{LCP}}_{G}$ which can be seen as a simplification of the LCP array of the Wheeler graph $G$. More precisely, we have the following result (see [4]; we assume $\sigma=O(1)$).

Essentially, the first solution in Theorem 1.4 explicitly stores $\overline{\mathsf{LCP}}_{G}$, while the second solution in Theorem 1.4 computes the entries of $\overline{\mathsf{LCP}}_{G}$ by exploiting the BOSS representation. In general, a big $k$ (close to the size of the reads) allows to retrieve the expressive power on an overlap graph [11], so in Theorem 1.4 we cannot assume that $k$ is small. On the one hand, the space required for the first solution can be too large, because a de Bruijn graph can be stored by using only $O(n)$ bits. On the other hand, the time bound in the second solution increases substantially. We can now improve the second solution by providing a data structure that achieves the best of both worlds. As we did in Theorem 1.1, we can conveniently sample some entries of $\overline{\mathsf{LCP}}_{G}$. We will prove the following result.

Let $V$ be a set. A total order on $V$ is a binary relation $\leq$ which is reflexive, antisymmetric and transitive. We say that $U$ is a $\leq$-interval (or simply an interval) if for all $v_{1},v_{2},v_{3}\in V$, if $v_{1},v_{3}\in U$ and $v_{1}<v_{2}<v_{3}$, then $v_{2}\in U$. If $u,v\in V$, with $u\leq v$, we denote by $[u,v]$ the smallest interval containing $u$ and $v$, that is $[u,v]=\{z\in V\;|\;u\leq z\leq v$ }. In particular, if $V$ is the set of integers, then we assume that $\leq$ is the standard total order, hence $[u,v]=\{u,u+1,\dots,v-1,v\}$.

Let $\Sigma$ be a finite alphabet, with $\sigma=|\Sigma|$. Let $\Sigma^{*}$ be the set of all finite strings on $\Sigma$ and let $\Sigma^{\omega}$ be the set of all (countably) infinite strings on $\Sigma$. If $\alpha\in\Sigma^{*}$, then $\alpha^{R}$ is the reverse string of $\alpha$. If $\alpha,\beta\in\Sigma^{*}\cup\Sigma^{\omega}$, we denote by $\mathop{\mathsf{lcp}}(\alpha,\beta)$ the length of longest common prefix between $\alpha$ and $\beta$. In particular, if $\alpha\in\Sigma^{*}$, then $\mathop{\mathsf{lcp}}(\alpha,\beta)\leq|\alpha|$ and if $\alpha,\beta\in\Sigma^{\omega}$ with $\alpha=\beta$, then $\mathop{\mathsf{lcp}}(\alpha,\beta)=\infty$. Let $\preceq$ be a fixed total order on $\Sigma$. We extend the total order $\preceq$ from $\Sigma$ to $\Sigma^{*}\cup\Sigma^{\omega}$ lexicographically.

Throughout the paper, let $\mathcal{A}=(Q,E,s_{0},F)$ be a deterministic finite automaton (DFA), where $Q$ is the set of states, $E\subseteq Q\times Q\times\Sigma$ is the set of labeled edges, $s_{0}\in Q$ is the initial state and $F\subseteq Q$ is the set of final states. The alphabet $\Sigma$ is effective, that is, every $c\in\Sigma$ labels some edge. Since $\mathcal{A}$ is deterministic, for every $u\in Q$ and for every $a\in\Sigma$ there exists at most one edge labeled $a$ leaving $u$. Following [1], we assume that (i) $s_{0}$ has no incoming edges, (ii) every state is reachable from the initial state and (iii) all edges entering the same state have the same label (input-consistency). For every $u\in Q\setminus\{s_{0}\}$, let $\lambda(u)\in\Sigma$ be the label of all edges entering $u$. We define $\lambda(s_{0})=\#$, where $\#\not\in\Sigma$ is a special character such that $\#\prec a$ for every $a\in\Sigma$ (the character $\#$ plays the same role as the termination character $\$$ in suffix arrays, suffix trees and Burrows-Wheeler transforms). As a consequence, an edge $(u^{\prime},u,a)$ can be simply written as $(u^{\prime},u)$, because it must be $a=\lambda(u)$.

Let $A$ be an array of length $n$ containing elements from a finite totally-ordered set. A range minimum query on $A$ is defined as follows: given $1\leq i\leq j\leq n$, return one of the indices $k$ with $1\leq k\leq n$ such that (i) $i\leq k\leq j$ and $A[k]=\min\{A[i],A[i+1],\dots,A[j-1],A[j]\}$. We write $k=RMQ_{A}(i,j)$. Then, there exists a data structure of $2n+o(n)$ such that in $O(1)$ time we can compute $RMQ_{A}(i,j)$ for every $1\leq i\leq n$, without the need to access $A$ [15, 16]. This result is essentially optimal, because every data structure solving range minimum queries on $A$ requires at least $2n-\Theta(\log n)$ bits [16, 20].

Let $A$ be a bitvector of length $n$. Let $rank(A,i)=|\{j\in\{1,2,\dots,i-1,i\}\;|\;A[j]=1\}|$ be the number of $1$’s among the first $i$ bits of $A$. Then, there exists a data structure of $n+o(n)$ bits such that in $O(1)$ time we can compute $rank(A,i)$ for $1\leq i\leq n$ [23].

Let $G=(V,H)$ be a finite (unlabeled) directed graph such that every node has at most one incoming edge. For every $v\in V$ and for every $i\geq 0$, there exists at most one node $v^{\prime}\in V$ such that there exists a directed path from $v^{\prime}$ to $v$ having $i$ edges; if $v^{\prime}$ exists, we denote it by $v(i)$. Fix a parameter $h\geq 1$. Let us prove that there exists $V(h)\subseteq V$ such that (i) $|V(h)|\leq\frac{|V|}{h}$ and (ii) for every $v\in V$ there exists $0\leq i\leq 2h-2$ such that $v(i)$ is defined and either $v(i)\in V(h)$ or $v(i)$ has no incoming edges or $v(i)=v(j)$ for some $0\leq j<i$. We build $V(h)$ incrementally following Algorithm 1. Let us prove that, at the end of the algorithm, properties (i) and (ii) are true. For every $v\in V(h)$, define $S_{v}=\{v,v(1),v(2)\dots,v(h-1)\}$, which is possible because by construction if $v\in V(h)$, then $v(i)$ is defined for every $0\leq i\leq h-1$. It must be $v(i)\not=v(j)$ for $0\leq i<j\leq h-1$, so $|S_{v}|=h$. If $v,v^{\prime}\in V(h)$ and $v\not=v^{\prime}$, then by construction $S_{v}$ and $S_{v^{\prime}}$ are disjoint. As a consequence, $|V|\geq\sum_{v\in V(h)}|S_{v}|=\sum_{v\in V(h)}h=h|V_{h}|$ and so $|V_{h}|\leq\frac{|V|}{h}$, which proves property (i). Let us prove property (ii). Pick $v\in V$; we must prove that there exists $0\leq i\leq 2h-2$ such that $v(i)$ is defined and either $v(i)\in V(h)$ or $v(i)$ has no incoming edges or $v(i)=v(j)$ for some $0\leq j<i$. We distinguish three cases:

1. 1.

   there exists $i$ with $1\leq i\leq h-1$ such that $v(i-1)$ is defined but $v(i)$ is not defined. Then, $v(i-1)$ has no incoming edges.

2. 2.

   there exist $i,j$ with $0\leq j<i\leq h-1$ such that $v(j)$ and $v(i)$ are defined and $v(i)=v(j)$. In this case, the conclusion is immediate.

3. 3.

   $v(i)$ is defined for every $0\leq i\leq h$ and $v(i)\not=v(j)$ for $0\leq j<i\leq h-1$. Since Algorithm 1 has terminated, then there exists $0\leq j\leq h-1$ such that $v(j)\in U$. The construction of $U$ implies that there exists $v^{\prime}\in V$ and $0\leq j\leq h-1$ such that $v(j)=v^{\prime}(j^{\prime})$ and $v^{\prime}(h-1)\in V(h)$. As a consequence $v(h-1+j-j^{\prime})=v(j)(h-1-j^{\prime})=(v^{\prime}(j^{\prime}))(h-1-j^{\prime})=v^{\prime}(h-1)\in V(h)$. Since $j\leq h-1$ and $j^{\prime}\geq 0$, we conclude $h-1+j-j^{\prime}\leq 2h-2$ and we are done.

First, let us store a data structure of $O(n)$ bits which in $O(1)$ time determines $RMQ_{\mathsf{LCP}_{\mathcal{A}}}(i,j)$ for every $2\leq i\leq j\leq 2n$.

Notice that $\mathsf{LCP}_{\mathcal{A}}[2i]\geq 1$ for $1\leq i\leq n$ because the first character of $\min_{i}$ and the first character of $\max_{i}$ are equal to $\lambda(u_{i})$. Moreover, we have $\mathsf{LCP}_{\mathcal{A}}[2i-1]\geq 1$ if and only if $\lambda(u_{i-1})=\lambda(u_{i})$, for $2\leq i\leq n$.

Consider the entry $\mathsf{LCP}_{\mathcal{A}}[2i-1]=\mathop{\mathsf{lcp}}(\max_{i-1},\min_{i})$, for $2\leq i\leq n$, and assume that $\mathsf{LCP}_{\mathcal{A}}[2i-1]\geq 1$. Let $k=p_{\max}(i-1)$ and $k^{\prime}=p_{\min}(i)$. Since $\mathsf{LCP}_{\mathcal{A}}[2i-1]\geq 1$, then there exists $a\in\Sigma$ such that $\max_{i-1}=a\max_{k}$ and $\min_{i-1}=a\min_{k^{\prime}}$. In particular, $(u_{k},u_{i-1},a)\in E$ and $(u_{k^{\prime}},u_{i},a)\in E$, so from Axiom 2 we obtain $k<k^{\prime}$. Moreover, we have $\mathsf{LCP}_{\mathcal{A}}[2i-1]=\mathop{\mathsf{lcp}}(\max_{i-1},\min_{i})=\mathop{\mathsf{lcp}}(a\max_{k},a\min_{k^{\prime}})=1+\mathop{\mathsf{lcp}}(\max_{k},\min_{k^{\prime}})$. Notice that:

Let $j=RMQ_{\mathsf{LCP}_{\mathcal{A}}}(2k+1,2k^{\prime}-1)$. Then, $\mathsf{LCP}_{\mathcal{A}}[j]=\min\{\mathsf{LCP}_{\mathcal{A}}[2k+1],\mathsf{LCP}_{\mathcal{A}}[2k+2],\dots,\mathsf{LCP}_{\mathcal{A}}[2k^{\prime}-2],\mathsf{LCP}_{\mathcal{A}}[2k^{\prime}-1]\}$, so $\mathsf{LCP}_{\mathcal{A}}[2i-1]=1+\mathsf{LCP}_{\mathcal{A}}[j]$ (we assume $t+\infty=\infty$ for every $t\geq 0$), and we have reduced the problem of computing $\mathsf{LCP}_{\mathcal{A}}[2i-1]$ to the problem of computing $\mathsf{LCP}_{\mathcal{A}}[j]$. In the following, let $\mathcal{R}(2i-1)=j$. Given $2\leq i\leq n$, we can compute $j=\mathcal{R}(2i-1)$ in $O(\log\log\sigma)$ time, because we can compute $k=p_{\max}(i-1)$ and $k^{\prime}=p_{\min}(i)$ in $O(\log\log\sigma)$ time and we can compute $j$ in $O(1)$ time by means of a range minimum query.

We proceed analogously with the entries $\mathsf{LCP}_{\mathcal{A}}[2i]=\mathop{\mathsf{lcp}}(\min_{i},\max_{i})$, for $1\leq i\leq n$ (it must necessarily be $\mathsf{LCP}_{\mathcal{A}}[2i]\geq 1$). Let $k=p_{\min}(i)$ and $k^{\prime}=p_{\max}(i)$; by the definitions of $p_{\min}$ and $p_{\max}$ it must be $k\leq k^{\prime}$. Hence, $\mathsf{LCP}_{\mathcal{A}}[2i]=1+\mathop{\mathsf{lcp}}(\min_{k},\max_{k^{\prime}})$ and similarly $\mathop{\mathsf{lcp}}(\min_{k},\max_{k^{\prime}})=\min\{\mathsf{LCP}_{\mathcal{A}}[2k],\mathsf{LCP}_{\mathcal{A}}[2k+1],\dots,\mathsf{LCP}_{\mathcal{A}}[2k^{\prime}\leavevmode\nobreak\ -1],\mathsf{LCP}_{\mathcal{A}}[2k^{\prime}]\}$. Let $j=RMQ_{\mathsf{LCP}_{\mathcal{A}}}(2k,2k^{\prime})$. In the following, let $\mathcal{R}(2i)=j$. Given $1\leq i\leq n$, we can compute $j=\mathcal{R}(2i)$ in $O(\log\log\sigma)$ time. See Figure 1 for an example.

Now, consider the (unlabeled) directed graph $G=(V,H)$ defined as follows. Let $V$ be a set of $2n-1$ nodes $v_{2}$, $v_{3}$, $\dots$, $v_{2n}$. Moreover, $v_{i}\in V$ has no incoming edge in $G$ if $\mathcal{R}(i)$ is not defined, which happens if $\mathsf{LCP}_{\mathcal{A}}[i]=0$ (and so $i$ is odd and $\lambda(u_{i-1})\not=\lambda(u_{i})$); $v_{i}\in V$ has exactly one incoming edge if $\mathcal{R}(i)$ is defined, namely, $(v_{\mathcal{R}(i)},v_{i})$. Note that $v_{2i}$ has an incoming edge for every $1\leq i\leq n$. Let $h\geq 1$ be a parameter. We know that there exists $V(h)\subseteq V$ such that (i) $|V(h)|\leq\frac{|V|}{h}$ and (ii) for every $v_{i}\in V$ there exists $0\leq k\leq 2h-2$ such that $v_{i}(k)$ is defined and either $v_{i}(h)\in V(h)$ or $v_{i}(h)$ has no incoming edges or $v_{i}(h)=v_{i}(l)$ for some $0\leq l<h$. Notice that if $v_{i}(h)=v_{i}(l)$ for some $0\leq l<h$, then $\mathsf{LCP}_{\mathcal{A}}[i]=\infty$ (because there is a cycle and so $v_{i}(h^{\prime})$ is defined for every $h^{\prime}\geq 0$). Let $n^{\prime}=|V(h)|$, and let $\mathsf{LCP}^{*}_{\mathcal{A}}[1,n^{\prime}]$ an array storing the value $\mathsf{LCP}_{\mathcal{A}}[i]$ for each $v_{i}\in V(h)$, sorted by increasing $i$. Since $n^{\prime}\leq\frac{|V|}{h}=\frac{2n-1}{h}$, storing $\mathsf{LCP}^{*}_{\mathcal{A}}[1,n^{\prime}]$ takes $n^{\prime}O(\log n)=O(\frac{n\log n}{h})$ bits. We store a bitvector $C[2,2n]$ such that $C[i]=1$ if and only if $v_{i}\in V(h)$ for every $2\leq i\leq 2n$; we augment $C$ with $o(n)$ bits so that it supports rank queries in $O(1)$ time. For every $2\leq i\leq 2n$, in $O(1)$ time we can check whether $\mathsf{LCP}_{\mathcal{A}}[i]$ has been stored in $\mathsf{LCP}^{*}_{\mathcal{A}}$ by checking whether $C[i]=1$, and if $C[i]=1$ it must be $\mathsf{LCP}_{\mathcal{A}}[i]=\mathsf{LCP}^{*}_{\mathcal{A}}[rank(C,i)]$.