Correcting Multiple Substitutions in Nanopore-Sequencing Reads Thanks: The research was Funded by the European Union (ERC, DNAStorage, 101045114 and EIC, DiDAX 101115134). Views and opinions expressed are however those of the authors only and do not necessarily reflect those of the European Union or the European Research Council Executive Agency. Neither the European Union nor the granting authority can be held responsible for them. It was also partially funded by UKRI BBSRC grant BB/Y007638/1, the Department for Science, Innovation and Technology (DSIT) and the Royal Academy of Engineering for a Chair in Emerging Technologies award. Anisha Banerjee 1 , Yonatan Yehezkeally 2 , Antonia Wachter-Zeh 1 , and Eitan Yaakobi 3 Abstract Despite their significant advantages over competing technologies, nanopore sequencers are plagued by high error rates, due to physical characteristics of the nanopore and inherent noise in the biological processes. It is thus paramount not only to formulate efficient error-correcting constructions for these channels, but also to establish bounds on the minimum redundancy required by such coding schemes. In this context, we adopt a simplified model of nanopore sequencing inspired by the work of Mao et al. , accounting for the effects of intersymbol interference and measurement noise. For an input sequence of length n n , The vector that is produced, designated as the read vector , may additionally suffer at most t t substitution errors. We employ the well-known graph-theoretic clique-cover technique to establish that at least t ​ log ⁡ n − O ⁡ ( 1 ) t\log n-O(1) bits of redundancy are required to correct multiple ( t ⩾ 2 t\geqslant 2 ) substitutions. While this is surprising in comparison to the case of a single substitution, that necessitates at most log ⁡ log ⁡ n − O ⁡ ( 1 ) \log\log n-O(1) bits of redundancy, a suitable error-correcting code that is optimal up to a constant follows immediately from the properties of read vectors. I Introduction DNA as a potential data storage medium holds great promise. However, significant advancements in synthesis and sequencing technologies are still necessary to make it feasible for commercial use. Among the various sequencing technologies, nanopore sequencing outshines its contenders due to its portability and ability to support longer reads. This technology sequences a DNA strand by allowing it to pass through a microscopic pore that contains \ell nucleotides at any given time instant. By analyzing the variations in the ionic current, which are influenced by the different nucleotides passing through the pore, we can infer the sequence of nucleotides in the original DNA strand. This readout, however, is plagued by distortions due to the noise inherent in the different physical aspects of this process. To begin with, because the pore can hold multiple nucleotides ( \ell>1 ) simultaneously, the observed current is influenced by several nucleotides rather than just onecreating inter-symbol interference (ISI) in the channel output. Additionally, the irregular movement of the DNA fragment through the pore can often lead to backtracking or to skipping a few nucleotides. These irregularities appear as duplications or deletions in the channel output, respectively. Furthermore, the random noise that affects the measured current can be effectively modeled as substitution errors. Initial work in this area focused on devising accurate mathematical models for the sequencer or formulating efficient error-correcting codes that incorporate these models. Notably, [ 1 , 2 , 3 , 4 ] examined the channel from an information-theoretic perspective in an effort to understand its capacity. In particular, the authors of [ 1 ] proposed a channel model that considers ISI, deletions, and random measurement noise and also derived suitable upper bounds for the capacity of this channel. On the contrary, [ 2 ] used a more deterministic model and developed an algorithm to calculate its capacity. The authors of [ 3 , 4 ] studied a finite-state semi-Markov channel (FSMC)–based model for nanopore sequencing that accounts for ISI, duplications, and noisy measurements. They estimated the achievable information rates of this noisy nanopore channel by formulating efficient algorithms to perform this computation. Another exciting direction seeks to facilitate the accurate decoding of DNA fragments, despite sample duplications and background noise, by designing codes directly based on the current signals produced by the nanopore for each sequence of nucleotides [ 5 , 6 , 7 ] . A subset of prior work [ 8 , 9 , 10 , 11 ] studied a specific channel model of the nanopore sequencer inspired by [ 1 ] . In particular, these works considered the nanopore sequencer to be the concatenation of three distinct channels, as depicted in Fig. 1. The first component that emulates the ISI effect is parameterized by \ell and demonstrates how the observed current is influenced by the \ell>1 consecutive nucleotides present in the pore at any moment. This stage is conceptualized as a window of length \ell that slides over an input sequence, shifting by a single position after each time step. This produces a sequence of \ell -mers, or a string of \ell symbols, which is then fed to a discrete memoryless channel (DMC) that transforms each \ell -mer into a discrete voltage level based on a deterministic function, assumed to be the Hamming weight when the input is binary, and the composition function otherwise. The final stage introduces errors, such as substitutions, deletions, or duplications, that corrupt the sequence of discrete voltage levels. While [ 8 , 9 ] assumed that the error component introduces either at most one substitution or at most one deletion in the final channel output, [ 11 ] considered multiple substitutions and investigated bounds and constructions of suitable substitution-correcting codes for this channel, when \ell=2 . In contrast, [ 10 ] proposed constrained codes for this channel to combat duplication and deletion errors. This model is also similar to the transverse-read channel [ 12 , 13 ] , which is important for racetrack memories. We now state the problem formally. Question 1 For a given input {\boldsymbol{x}} , let \mathcal{R}_{\ell}({\boldsymbol{x}}) denote the error-free output from the channel (as defined in Definition 2 ). What is the minimum redundancy required to correct t substitution errors in \mathcal{R}_{\ell}({\boldsymbol{x}}) (rather than in {\boldsymbol{x}} )? The primary contribution of this work is to demonstrate that for \ell\geqslant 2 , the minimum redundancy required for any code of length n that can correct t\geqslant 2 substitutions in \ell -read vectors is at least t\log_{2}n-O(1) bits (Theorem 17 ), which starkly contrasts with the minimum redundancy bound of \log_{2}\log_{2}n-o(1) [ 9 ] for the case of t=1 . Following the introduction of essential notations and definitions in Section II , we present the proof of this lower bound, based on the clique cover technique [ 14 , 15 ] , in Section III . With this unfortunate result, we show in A that a naive construction achieves this bound up to a constant. Nucleotides {\boldsymbol{x}} ISI \ell DMC Substitution \ell -mers Discrete voltage levels \mathcal{R}({\boldsymbol{x}}) \mathcal{R}({\boldsymbol{x}})^{\prime} Figure 1 : Simplified model of a nanopore sequencer II Preliminaries For any q\geqslant 2 , we let \Sigma_{q} represent the q -ary alphabet \{0,1,\ldots,q-1\} . The set of all q -ary sequences of length n is indicated by \Sigma_{q}^{n} , with \Sigma_{q}^{0} meant to indicate the empty set. Additionally, we let \Sigma_{q}^{\geqslant n}=\cup_{i=n}^{\infty}\Sigma_{q}^{i} . For any two integers a,b such that a\leqslant b , [a,b] is used to denote the set \{a,a+1,\ldots,b\} , and [b]\triangleq[1,b] for b\geqslant 1 . We also use the following notation to denote element-wise modulo operation on a vector {\boldsymbol{y}}\in\Sigma_{q}^{n} . \displaystyle{\boldsymbol{y}}\bmod a\triangleq\big(y_{1}\bmod a,y_{2}\bmod a,\ldots,y_{n}\bmod a\big). Given any vector {\boldsymbol{x}}=(x_{1},\ldots,x_{n}) , its substring (x_{i},x_{i+1},\ldots,x_{j}) is indicated concisely as {\boldsymbol{x}}_{i}^{j} . The operator \wt({\boldsymbol{x}}) indicates the Hamming weight of {\boldsymbol{x}} , while |{\boldsymbol{x}}| refers to its length, i.e., |{\boldsymbol{x}}|=n . We also indicate the Hamming distance between any two vectors {\boldsymbol{x}},{\boldsymbol{y}}\in\Sigma_{q}^{n} as d_{H}({\boldsymbol{x}},{\boldsymbol{y}})=|\{i:i\in[n],x_{i}\neq y_{i}\}|. Throughout this work, we focus on {q=2} , and the output of the channel we consider is a sequence of readings of a sliding window moved across {\boldsymbol{x}} , as defined below. Definition 2 [ 8 , 16 ] The \ell - read vector of any {{\boldsymbol{x}}\in{{\Sigma}}_{\!2}^{n}} is of length n+\ell-1 over \Sigma_{\ell+1} , and is defined as \mathcal{R}_{\ell}({\boldsymbol{x}})\triangleq(\wt({\boldsymbol{x}}_{2-\ell}^{1}),\wt({\boldsymbol{x}}_{3-\ell}^{2}),\ldots,\wt({\boldsymbol{x}}_{n}^{n+\ell-1})), where for any i\not\in[n] , we set x_{i}=0 . The i -th element of \mathcal{R}_{\ell}({\boldsymbol{x}}) is denoted as \mathcal{R}_{\ell}({\boldsymbol{x}})_{i} ; that is, \mathcal{R}_{\ell}(\boldsymbol{x})_{i}=\wt({\boldsymbol{x}}_{i-\ell+1}^{i}) . We will omit \ell from the subscript of \mathcal{R}_{\ell}({\boldsymbol{x}}) whenever it is clear from the context. It is worth pointing out that Definition 2 can be extended to the non-binary alphabet, by considering compositions instead of Hamming weights [ 9 ] . The composition of a vector q -ary {\boldsymbol{x}} refers to the count of each symbol in \Sigma_{q} as it appears in {\boldsymbol{x}} . Example 3 The 3 -read vector of {\boldsymbol{x}}=(0,1,1,0,1,0) is \mathcal{R}({\boldsymbol{x}})=(0,1,2,2,2,1,1,0) . Its fourth element is \mathcal{R}(\boldsymbol{{\boldsymbol{x}}})_{4}=2 . As mentioned previously, [ 12 , 13 ] examine a similar model, wherein the output sequence, called the transverse-read vector, is essentially a substring of the \ell -read vector for specific parameter choices. Since we are interested in codes that correct up to t substitutions in \ell -read vectors, it is essential to precisely define what is meant by an error-correcting code in the framework of our channel. Similarly to [ 9 ] , a code is said to be a t -substitution \ell -read code if for any distinct {\boldsymbol{x}},{\boldsymbol{y}} from this code, it holds that d_{H}(\mathcal{R}({\boldsymbol{x}}),\mathcal{R}({\boldsymbol{y}}))>2t . III Correcting Multiple Substitutions This section aims to establish an upper bound on the size of a code that corrects t substitutions in \ell -read vectors, where t\geqslant 2 is constant; the case t=1 was thoroughly analysed in [ 9 ] . To accomplish this, we apply the clique cover technique, which was also used in [ 15 , 9 ] for the case of t=1 . This method considers a graph \mathcal{G}(n) that contains vertices corresponding to all vectors in \Sigma^{n}_{2} . In this graph, any two vertices representing distinct binary vectors, say {\boldsymbol{x}} and {\boldsymbol{y}} in \Sigma^{n}_{2} , are considered adjacent if and only they satisfy d_{H}(\mathcal{R}({\boldsymbol{x}}),\mathcal{R}({\boldsymbol{y}}))\leqslant 2t . Consequently, any subset of vertices in \mathcal{G}(n) where no two vertices are adjacent (namely, an independent set ) constitutes a t -substitution \ell -read code. In contrast, a clique in the graph is a set of vertices that are all pair-wise adjacent. The formal definition of a clique cover is stated below. Definition 4 A clique cover \mathcal{Q} is a collection of cliques in a graph \mathcal{G} , such that every vertex in \mathcal{G} belongs to at least one clique in \mathcal{Q} . From [ 17 , 14 ] , the following result is widely known. Theorem 5 If \mathcal{Q} is a clique cover in a graph \mathcal{G} , then the size of any independent set is at most |\mathcal{Q}| . This theorem implies that the size of a clique cover is also an upper bound on the cardinality of a t -substitution \ell -read code. Hence, we seek to define an appropriate clique cover \mathcal{Q} for the remainder of this section. To proceed along these lines, we first define the following permutation, which serves to simplify the presentation of the technical results laid out in Lemma III and Lemma III . Definition 6 [ 16 , Definition 3] For a positive integer p , define a permutation \pi_{p} on {{\Sigma}}_{\!2}^{n} as follows. For all {\boldsymbol{x}}\in{{\Sigma}}_{\!2}^{n} , arrange the coordinates of {\boldsymbol{x}}_{1}^{p\ell\lfloor n/(p\ell)\rfloor} in a matrix X\in\Sigma^{p\lfloor n/(p\ell)\rfloor\times\ell} , by row (first fill the first row from left to right, then the next, etc.). Next, partition X into sub-matrices of dimension p\times 2 (if \ell is odd, we ignore X ’s right-most column). Finally, going through each sub-matrix (from left to right, and then top to bottom), we concatenate its rows , to obtain \pi_{p}({\boldsymbol{x}}) (where unused coordinates from {\boldsymbol{x}} are appended arbitrarily). More precisely, for all 0\leqslant i<\lfloor\frac{n}{p\ell}\rfloor , 0\leqslant j<\lfloor\frac{\ell}{2}\rfloor and 0\leqslant k

2pm-\ell+1 and r is odd, since x_{i}=y_{i}=0 for all i\not\in[2pm] . On the contrary, when r is even, similar arguments lead us to \displaystyle\mathcal{R}(\boldsymbol{{\boldsymbol{x}}})_{r+\ell-1}\!-\!\mathcal{R}(\boldsymbol{{\boldsymbol{y}}})_{r+\ell-1}\! \displaystyle= \displaystyle\!\wt({\boldsymbol{x}}_{r}^{r+\ell-1})-\wt({\boldsymbol{y}}_{r}^{r+\ell-1}) (1) \displaystyle= \displaystyle\!x_{r+\ell-1}-y_{r+\ell-1}\!-x_{r}+y_{r}. To specify the set of indices in [2pm+\ell-1] at which \mathcal{R}({\boldsymbol{x}}) and \mathcal{R}({\boldsymbol{y}}) disagree, we let the index at which the substring ({\boldsymbol{\alpha}}_{h})^{m_{h}} (or ({\boldsymbol{\beta}}_{h})^{m_{h}} ) starts in \pi_{p}({\boldsymbol{x}}) (or \pi_{p}({\boldsymbol{y}}) ) be given by c_{h} , for all h\in[s] . Thus, the starting and ending indices of each ({\boldsymbol{\alpha}}_{h})^{m_{h}} (or ({\boldsymbol{\beta}}_{h})^{m_{h}} ) in \pi_{p}({\boldsymbol{x}}) (or \pi_{p}({\boldsymbol{y}}) ) are c_{h} and c_{h}+2m_{h}-1 , which map to the positions f_{\pi}(c_{h}) and f_{\pi}(c_{h}+2m_{h}-1) in {\boldsymbol{x}} (or {\boldsymbol{y}} ), respectively. Since for all i\in\bigcup_{h\in[s]}\{f_{\pi}(c_{h}),\ldots,f_{\pi}(c_{h}+2m_{h}-1)\} , x_{i}\neq y_{i} , it is possible that for certain instances of r , \mathcal{R}(\boldsymbol{{\boldsymbol{x}}})_{r+\ell-1}\neq\mathcal{R}(\boldsymbol{{\boldsymbol{y}}})_{r+\ell-1} . Observe from Remark III , that for any r\in\bigcup_{h\in[s]}\{f_{\pi}(c_{h}+1),f_{\pi}(c_{h}+3),\ldots,f_{\pi}(c_{h}+2m_{h}-3)\} (even integers when \ell is even and equivalent to r+\ell-1\in\bigcup_{h\in[s]}\{f_{\pi}(c_{h}+2),f_{\pi}(c_{h}+4),\ldots\} ), we have x_{r}+x_{r+\ell-1}=y_{r}+y_{r+\ell-1}=1 . Thus, the only interesting cases that remain, are when either r\in\bigcup_{h\in[s]}\{f_{\pi}(c_{h}+2m_{h}-1)\} or when r+\ell-1\in\bigcup_{h\in[s]}\{f_{\pi}(c_{h})\} . In other words, we have \mathcal{R}(\boldsymbol{{\boldsymbol{x}}})_{r+\ell-1}\neq\mathcal{R}(\boldsymbol{{\boldsymbol{y}}})_{r+\ell-1} only if r\in\bigcup_{h\in[s]}\{f_{\pi}(c_{h}+2m_{h}-1),f_{\pi}(c_{h})-\ell+1\} , which is a set of size 2s . Consequently, d_{H}(\mathcal{R}({\boldsymbol{x}}),\mathcal{R}({\boldsymbol{y}}))\leqslant 2s . To prove the same for odd values of \ell , we infer from Definition III that for all r\in[2pm] satisfying r\equiv 0\pmod{\ell} , we have x_{r}=y_{r} . We continue as before, by noting that for any r\leqslant(\lfloor 2m/\ell\rfloor p-1)\ell+1 that satisfies r\bmod\ell\in\{0,1,3,\ldots,\ell-2\} , there exist integers i_{1},\ldots,i_{\lfloor\ell/2\rfloor},j_{1},\ldots,j_{\lfloor\ell/2\rfloor},k_{1},\ldots,k_{\lfloor\ell/2\rfloor} , that satisfy \displaystyle\mathcal{R}(\boldsymbol{{\boldsymbol{x}}})_{r+\ell-1}=\wt({\boldsymbol{x}}_{r}^{r+\ell-1}) \displaystyle= \displaystyle x_{\lceil r/\ell\rceil\ell}+\wt({\boldsymbol{x}}^{(i_{1},j_{1},k_{1})})+\cdots+\wt({\boldsymbol{x}}^{(i_{\lfloor{\ell}/{2}\rfloor},j_{\lfloor\ell/2\rfloor},k_{\lfloor\ell/2\rfloor})}) \displaystyle= \displaystyle y_{\lceil r/\ell\rceil\ell}+\wt({\boldsymbol{y}}^{(i_{1},j_{1},k_{1})})+\cdots+\wt({\boldsymbol{y}}^{(i_{\lfloor{\ell}/{2}\rfloor},j_{\lfloor\ell/2\rfloor},k_{\lfloor\ell/2\rfloor})}) \displaystyle= \displaystyle\mathcal{R}(\boldsymbol{{\boldsymbol{y}}})_{r+\ell-1}. The same holds when r>(\lfloor 2m/\ell\rfloor p-1)\ell+1 and r\bmod\ell\in\{0,1,3,\ldots,\ell-2\} as x_{i}=y_{i}=0 for all i\not\in[2pm] , and similarly so r\geqslant\lfloor 2m/\ell\rfloor p\ell+1 . The remaining case to examine is when r\bmod\ell\in\{2,4,\ldots,\ell-1\} , we deduce upon applying similar arguments that ( 1 ) holds also for odd values of \ell , and ultimately conclude similarly from Remark III that d_{H}(\mathcal{R}({\boldsymbol{x}}),\mathcal{R}({\boldsymbol{y}}))\leqslant 2s . ∎ Example 11 For \ell=3 , p=2 and the vectors {\boldsymbol{x}}=(0,1,1,0,1,0) and {{\boldsymbol{y}}=(1,0,1,1,0,0)} (from Example III ), the substring (01)^{2} (or (10)^{2} ) starts in \pi_{p}({\boldsymbol{x}}) (or \pi_{p}({\boldsymbol{y}}) ) at index c=1 . Observe that s=1 and for r\in\{f_{\pi}(c)-\ell+1,f_{\pi}(c+3)\}=\{-1,5\} , we have \mathcal{R}(\boldsymbol{{\boldsymbol{x}}})_{r+\ell-1}\neq\mathcal{R}(\boldsymbol{{\boldsymbol{y}}})_{r+\ell-1} , i.e., d_{H}(\mathcal{R}({\boldsymbol{x}}),\mathcal{R}({\boldsymbol{y}}))=2s=2 . With the assistance of Lemma III , we are now ready to show that \mathcal{Q}(m,p) is a clique cover of the smaller graph \mathcal{G}(2pm) , where m=\lfloor\frac{\ell}{2}\rfloor\lfloor\frac{n}{p\ell}\rfloor . Lemma 12 Letting m=\lfloor\frac{\ell}{2}\rfloor\lfloor\frac{n}{p\ell}\rfloor , \displaystyle\left\{\pi_{p}^{-1}(Q):Q\in\mathcal{Q}(m,p)\right\} is a clique cover of \mathcal{G}(2pm) . (Here, we abuse notation to let \pi_{p} also act on {{\Sigma}}_{\!2}^{2pm} , in the natural way.) Proof: While the singletons forming the set \left\{\left\{{\boldsymbol{x}}\right\}:\pi_{p}({\boldsymbol{x}})\in\widetilde{\Lambda}_{p}^{m}\right\} are evidently cliques, Lemma III implies that for all i\in[2,t],\gamma\in\Gamma_{i} , and 0\leqslant j<2^{i} , \displaystyle\left\{{\boldsymbol{x}}\in{{\Sigma}}_{\!2}^{2pm}:\pi_{p}({\boldsymbol{x}})\in Q_{\gamma}^{(j)}\right\} is also a clique (the case i=1 was already proven in [ 16 ] ). It now remains to show that \pi_{p}({\boldsymbol{x}}) belongs to at least one clique in \mathcal{Q}(m,p) for any {\boldsymbol{x}}\in{{\Sigma}}_{\!2}^{2pm} . For simplicity, we use the fact that \pi_{p} is a permutation to show instead that any such {\boldsymbol{x}} is itself a member. To this end, consider a {\boldsymbol{x}}\in{{\Sigma}}_{\!2}^{2pm} and the set \mathcal{I}=\{i_{1},\ldots,i_{|\mathcal{I}|}\} where i_{1}<\cdots2t . \Box Evidently, A requires t\log_{2}n redundant bits. Thus, for t\geqslant 2 and \ell\geqslant 2 , it is a t -substitution \ell -read code that is optimal up to a constant. IV Conclusion This work uses a simplified model of a nanopore sequencer and establishes a lower bound on the redundancy needed to correct up to t substitutions in the output of this simplified channel. Our findings indicate that for t\geqslant 2 , the minimal redundancy for a suitable code is comparable to that of a classical substitution channel. This prompts the question of whether these results would still hold if the channel model assigned non-uniform weights to the bits in each window, i.e., \mathcal{R}(\boldsymbol{{\boldsymbol{x}}})_{i}=\sum_{h=1}^{\ell}w_{h}x_{i-\ell+h} and {\boldsymbol{w}}\neq(1,\ldots,1) .