Deletion-Correcting Codes for the ℓ \ell -Symbol Read Channel

Zuo Ye, Gennian Ge · 2026

Read Deletion-Correcting Codes for the ℓ \ell -Symbol Read Channel by Zuo Ye, Gennian Ge (2026) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2606-26434.txt.

Introduction

Zuo Ye and Gennian Ge study error-correcting codes for a special reading channel. Some devices read a sequence through overlapping windows. Nanopore sequencing and racetrack memories work this way. The output is the list of all short consecutive blocks in the sequence. An adversary deletes some of those blocks, and the code must still recover the original sequence.

Ye and Ge first characterise what deletions do to the read list. After the fewest repairs, the damage localises to certain repeating substrings. They then build codes using check patterns and power-sum syndromes. A syndrome is a compact fingerprint used to locate errors. Their single-deletion codes use redundancy, meaning extra stored symbols, close to the theoretical minimum. Multi-deletion codes follow for a range of settings, with redundancy growing in a controlled way.

Catalog record

CREATORZuo Ye, Gennian Ge
YEAR2026
COLLECTIONPAPERS
FORMATTXT
FILE SIZE126 KB
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2606.26434

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

Deletion-Correcting Codes for the ℓ \ell -Symbol Read Channel Zuo Ye, Gennian Ge Abstract This paper studies deletion-correcting codes for the ℓ \ell -symbol read channel, whose noiseless output is the vector of all consecutive ℓ \ell -mers of a transmitted sequence. This model is motivated by overlapping-read mechanisms arising in nanopore sequencing, racetrack memories with consecutive read heads, and related sequence-labeling problems. We consider an adversarial setting in which a fixed number of ℓ \ell -mers are deleted from the read vector. Our first contribution is a structural characterization of the effect of such deletions: after a minimum number of ℓ \ell -mers are inserted to restore consistency, the resulting sequence is obtained from the transmitted sequence by deleting symbols from certain periodic substrings; when t ≤ ℓ − 2 t\leq\ell-2 , these deletions correspond to complete minimum periods. Based on this characterization, we introduce check patterns and construct ℓ \ell -read deletion-correcting codes via power-sum syndromes. For every ℓ ≥ 2 \ell\geq 2 , we obtain single-deletion correcting codes with redundancy log ⁡ ⌊ ( n + 2 ​ ℓ ) / ( ℓ − 1 ) ⌋ \log\lfloor(n+2\ell)/(\ell-1)\rfloor . For 2 ≤ t ≤ ℓ / 2 2\leq t\leq\ell/2 , we construct q q -ary ℓ \ell -read t t -deletion correcting codes with redundancy t ​ log ⁡ n + O ⁡ ( 1 ) t\log n+O(1) , and for ℓ = 2 ​ t − 1 \ell=2t-1 with t ≥ 3 t\geq 3 , we construct codes with redundancy ( 2 ​ t − 1 ) ​ log ⁡ n + O ⁡ ( 1 ) (2t-1)\log n+O(1) . We also study the sporadic parameter pairs ( ℓ , t ) ∈ { ( 2 , 2 ) , ( 3 , 2 ) , ( 3 , 3 ) } (\ell,t)\in\{(2,2),(3,2),(3,3)\} and obtain improved constructions, including binary ℓ \ell -read 2 2 -deletion correcting codes with redundancy 2 ​ log ⁡ n + O ⁡ ( 1 ) 2\log n+O(1) for ℓ = 2 , 3 \ell=2,3 , a non-binary 3 3 -read 2 2 -deletion correcting code with redundancy 3 ​ log ⁡ n + O ⁡ ( 1 ) 3\log n+O(1) , a binary 3 3 -read 3 3 -deletion correcting code with redundancy 5 ​ log ⁡ n + O ⁡ ( 1 ) 5\log n+O(1) , and a non-binary 3 3 -read 3 3 -deletion correcting code with redundancy 7 ​ log ⁡ n + O ⁡ ( 1 ) 7\log n+O(1) . I Introduction We consider an abstract readout model in which a sequence is observed through overlapping windows of length \ell . More precisely, for a sequence \bm{x}=x_{1}x_{2}\cdots x_{n} , the noiseless channel output is the vector \mathcal{R}_{\ell}(\bm{x})\triangleq\left(\bm{x}_{[1,\ell]},\bm{x}_{[2,\ell+1]},\ldots,\bm{x}_{[n-\ell+1,n]}\right), where \bm{x}_{[i,j]}\triangleq x_{i}x_{i+1}\cdots x_{j} for all i\leq j . We study an adversarial deletion model for this channel: the decoder receives a subvector of \mathcal{R}_{\ell}(\bm{x}) , obtained by deleting a prescribed number, say t , of \ell -symbol reads, and aims to recover the original sequence. A code capable of correcting such errors is called an \ell -read t -deletion correcting code. Throughout the paper, \ell and t are treated as constants. This model is motivated by several readout mechanisms in sequencing and storage systems. In nanopore sequencing, the measured signal depends on a local block of consecutive nucleotides rather than on a single nucleotide. In symbol-pair and b -symbol read channels, adjacent or consecutive groups of symbols are read together. In DNA labeling, using a sufficiently rich set of labels allows one to identify local substrings of a DNA strand. In racetrack memory, multiple read heads can observe local groups of stored symbols, while shift errors may delete or repeat read positions. These different settings lead to the same basic mathematical object: an overlapping read vector followed by synchronization errors. We next discuss these motivations and the most relevant prior work. I-A Motivation and Related Work I-A 1 Nanopore Sequencing DNA has emerged as a promising medium for archival data storage owing to its exceptionally high storage density and long-term stability [ 1 , 2 ] . In a DNA-based data storage system, data is first encoded into sequences over the DNA nucleotide alphabet \left\{A,C,G,T\right\} . The corresponding DNA strands are then synthesized and stored. To access the original data, the stored DNA strands are sequenced and converted back into nucleotide sequences. Among available sequencing technologies, nanopore sequencing is particularly attractive because of its advantages including relatively low cost, high portability, and the ability to produce much longer reads [ 1 , 3 ] . In a nutshell, nanopore sequencing reads a single-stranded DNA molecule by driving it through a nanopore and recording ionic-current measurements as the nucleotides translocate through the pore. These measurements are subsequently processed by a basecalling algorithm to infer the underlying DNA sequence. Importantly, each measurement is typically influenced not by a single nucleotide, but by several, say \ell , consecutive nucleotides within the sensing region of the pore. This local-context dependence is commonly abstracted by a function f:\left\{A,C,G,T\right\}^{\ell}\rightarrow\mathcal{Y} , where \mathcal{Y} is the output alphabet. Under this abstraction, the noiseless readout corresponding to an input DNA sequence \bm{x}=x_{1}x_{2}\cdots x_{n} is the vector \mathcal{R}_{f}(\bm{x})\triangleq\left(f(\bm{x}_{[1,\ell]}),f(\bm{x}_{[2,\ell+1]}),\ldots,f(\bm{x}_{[n-\ell+1,n]})\right) [ 4 , 1 ] . In practice, the observed readout corresponding to \mathcal{R}_{f}(\bm{x}) may be affected by various errors, including deletions, tandem duplications, and substitutions [ 5 ] . The goal is to reconstruct \bm{x} from such a corrupted version of \mathcal{R}_{f}(\bm{x}) . The preceding channel model naturally extends to arbitrary q -ary alphabets. Coding problems for this channel have been studied under different choices of the map f and different error models. For example, when f maps an \ell -mer to to its composition, several works have considered the correction of substitution [ 6 , 7 , 8 , 9 ] , deletion [ 10 ] , or duplication errors [ 11 ] in \mathcal{R}_{f}(\bm{x}) . Chee et al [ 12 ] studied constrained coding schemes for correcting deletions or duplications in \mathcal{R}_{f}(\bm{x}) , without specifying the map f . The works most directly related to the present paper are the two papers by Xie and Chen [ 13 , 14 ] , where it is assumed that one has access to a sequence of \ell -mers inferred by basecallers. Under this assumption, the noiseless channel output corresponding to \bm{x} is \mathcal{R}_{\ell}(\bm{x}) . Notice that \mathcal{R}_{\ell}(\bm{x}) is equivalent to \mathcal{R}_{f}(\bm{x}) when f is injective. They further assume that \bm{x} is prefixed with a known \ell -mer \bm{u} and suffixed with a known \ell -mer \bm{v} before entering the nanopore. Thus, the exact transmitted sequence is \bm{u}\bm{x}\bm{v} . This assumption is practically reasonable in nanopore sequencing, where adapter sequences are commonly attached to DNA strands before sequencing [ 5 , Section II] . The goal of their works is to design large codes enabling the recovery of \bm{x} even when t components of \mathcal{R}_{\ell}\left(\bm{u}\bm{x}\bm{v}\right) are deleted. For t=2 , Xie and Chen in [ 13 ] constructed a q -ary code with redundancy 3\log(n)+O(1) for constant \ell\geq 4 . Later, in [ 14 ] , they constructed a q -ary code with redundancy 2t\log(n)+o(\log(n)) for general t , under the

Read the complete text