CS Paper Radar

Correcting Burst Errors with Applications to DNA-Based Data Storage

Yuan-Pon Chen, Olgica Milenkovic

cs.IT ·submitted 2026-10-11 15:37 UTC · v1
theory

Abstract

We introduce the problem of permutation burst error-correction, motivated by applications in molecular data storage with nanopore sequencing read platforms. A permutation burst of length $k$ is an error that affects a substring of length $k$ of a string of length $n$ by permuting its entries. Permutation burst errors can be corrected using classical burst error-correcting codes, such as Fire and Reed-Solomon codes. Here, we study how to reduce the redundancy of these classical codes by taking into account that the burst error preserves the weight of the substring. In addition, we further restrict our model to handle cyclic permutation bursts only, which are of independent practical and mathematical interest. Our main results include proving/establishing the following: a) for $k=o(\sqrt{n}),$ the redundancy of any permutation burst error correcting code is at least $\log n-k+\log \binom{2k-2}{k-2}+o(1).$ This result follows from McDiarmid's concentration bound; b) for $k \geq 9$ and $k=o\left(\sqrt{\frac{n}{\log n}}\right)$, the redundancy of any cyclic permutation burst error correcting code is at least $\log n +\log (k(k-1)-56)-\log\,80+o(1).$ c) the asymptotic redundancy upper bounds for the two types of substring errors that are twice the lower bound; d) constructions for both permutation burst and cyclic permutation burst errors that involve Varshamov-Tenegoltz type constraints or represent generalizations and extensions of Fire and other codes. In particular, we exhibit polynomially encodable and decodable codes that can correct cyclic bursts of length $\leq k$ using $\log n + k + 49\log k + O(\log \log k)$ redundant bits.

Comment
19 pages, 2 figures, 3 tables

Closest papers

Nearest neighbours by meaning across the whole index.

One Burst of t-Deletion and One Burst of t-Substitution Error-Correcting Codes

cs.IT ·2026-08-25 ·Yajuan Liu, Han Cai, Tolga M. Duman
published similarity 0.65
Abstract

Synchronization errors, including insertions, deletions, and substitutions, may occur in bursts in communication systems such as DNA data storage, file synchronization, and magnetic recording. In this paper, we study an error model con?sisting of one burst of t-deletions and one burst of t-substitutions. By reformulating the original sequence into a matrix form, we propose an explicit construction of error-correcting codes capable of correcting one burst of t-deletions and one burst of t-substitutions with O(log n) redundancy.

0.57

Substring Edit Correcting Codes and Optimal Single Burst-Deletion Correcting Codes

cs.IT ·2026-10-05 ·Zuo Ye, Gennian Ge
similarity 0.62
Abstract · 35 pages

A $k$-substring edit in a sequence first deletes a substring of length at most $k$, and then inserts a sequence of length at most $k$ at the same position. A code that can correct a $k$-substring edit is called a $k$-substring edit code. In this paper, we develop a new localization method and use it to construct a $q$-ary $k$-substring edit correcting code with $\log n+8\log\log n+o(\log\log n)$ bits of redundancy for any fixed $q\ge2$ and $k\ge1$, where $n$ is the code length. For the binary alphabet, this improves upon the redundancy $\log n+16k\log\log n+o(\log\log n)$ obtained by Li \emph{et al}. When the deleted substring and the inserted sequence have different lengths, we further construct codes with redundancy $\log n+O_{q,k}(1)$, which is optimal up to an additive constant. As corollaries, for all fixed $q\ge2$ and $1\le t\le T$, we obtain $q$-ary $(\le t)$-burst-deletion correcting codes and $(t,T)$-localized deletion correcting codes with redundancies $\log n+O_{q,t}(1)$ and $\log n+O_{q,T}(1)$, respectively. To the best of our knowledge, these are the first constructions attaining optimal redundancy up to an additive constant for these two deletion models over the full range of fixed parameters. For $(\le t)$-burst-deletion correction with $t\ge2$, such redundancy had previously been achieved only for $q=t=2$ by Levenshtein in 1967.

0.17

The Coverage Depth Problem in Distributed DNA Data Storage

cs.IT math.CO ·2026-10-02 ·Xiangliang Kong, Ohad Elishco, Chen Wang, Tolga M. Duman
theoryhighly cited similarity 0.61
Abstract · 33 pages, 2 figures

Random sampling in DNA sequencing produces repeated reads, increasing retrieval latency and sequencing cost. We study the coverage-depth problem for full-message recovery in distributed DNA storage under noiseless uniform sampling, where strands are partitioned among $M$ containers and one strand is independently sampled with replacement from each container per round. For arbitrary linear codes and ordered partitions, we derive exact formulas for the recovery-time distribution and expectation. We prove that MDS codes, whenever they exist, are optimal for every fixed partition, and establish a universal lower bound on the expected total read cost together with its equality conditions. For MDS codes, we identify container-size regimes that yield genuine savings in total reads and regimes that provide only parallelism without changing the asymptotic sequencing cost. For simplex codes, we prove that the $q$-ary simplex code is, up to isomorphism, the unique single-container minimizer among codes with the same parameters, resolving a recent conjecture by Bertuzzo, Ravagnani, and Yaakobi. We further construct a partition attaining the minimum total read cost and derive bounds for intermediate and balanced partitions. These results clarify when distributed sampling reduces latency alone and when it also reduces sequencing cost.

0.49

Orbit Reduction and Learned Run Distributions for Finite-Blocklength Binary Deletion Channels

cs.IT ·2026-09-21 ·Hassan Khodaiemehr, Chen Feng
theory similarity 0.61
Abstract · 13 pages, 4 figures, 9 tables. v2: corrected orbit reduction (complement-reversal theorem); ORD values recomputed with numerical certificate…

In DNA data storage, racetrack memories, and packet networks, data are written as many short strands of fixed length. The receiver knows where each strand begins and ends, and deletions occur only inside a strand. The relevant limit for such systems is the block capacity $C_N(d)$, the largest mutual information between a length-$N$ input and the output of a binary deletion channel with deletion probability $d$. Because the boundaries are known, $C_N(d)/N$ is never smaller than the classical capacity $C(d)$. Computing $C_N(d)$ is hard because the input takes $2^N$ values. For $0\le d<1$, we show that the optimal input is unique, gives positive probability to every string, and is unchanged by complementing or reversing the strings. We then introduce the optimized run distribution (ORD), which assigns one probability to each number of runs; it is optimal for $N\le3$ and is solved with a numerical optimality certificate up to $N=16$. For longer strands, an exact recursion for the output distribution gives unbiased rate estimates, and an empirical Bernstein inequality turns them into confidence intervals. Within the statistical precision, a one-parameter Markov input performs as well as the best inputs found. For strands of 100-200 bits, known boundaries increase the rate by up to 0.026 bits per symbol beyond the best certified upper bound on the capacity of the unsegmented channel. Via Fano's inequality, the block capacity also bounds the rate of any code that uses a single strand; in the tabulated case, this bound is tighter than the best known finite-length bound for strands longer than about 90 bits. Conversely, block rates yield lower bounds on $C(d)$; at $d=0.1$, the bound is within $1.1\times10^{-4}$ bits/use of the best certified lower bound. Finally, InfoNCE estimates, even with the optimal critic, empirically lose most of their ability to rank inputs as the strand length grows.

0.24

MacKay-Neal Codes for DNA Channels under Block-MAP Decoding

cs.IT ·2026-10-28 ·Kenta Kasai
theory similarity 0.60
Abstract · 14 pages

We prove achievability below the symmetric information rate (SIR) under block maximum a posteriori (MAP) decoding for a fixed-degree MacKay-Neal (MN) socket ensemble on the quaternary insertion-deletion-substitution channel used to model DNA reads. For every integer $\ell\ge4$, the $(\ell,3,3)$ socket ensemble, with one transmitted bit fixed and an independent uniform known offset, has limiting rate $r_\star=6/\ell$ bits per stored nucleotide. If the joint SIR $J_t$ of a fixed number $t$ of reads under independent, uniformly distributed input nucleotides exceeds $r_\star$, the ensemble-average full extended-word block error is $O(1/n)$, and deterministic graph-offset sequences attain the same limiting rate and message-average error bound. This result concerns the discrete rate family $6/\ell$, not arbitrary rates approaching a given SIR. The channel permits arbitrarily many insertions and unbounded drift, with no alignment supplied to the receiver. The proof combines established MN parity and distance estimates with a strict arbitrary-candidate-list bound and a list construction that accounts for hidden output boundaries.

0.26

Polynomially larger deletion codes by linear hashing of substring counts

cs.IT math.CO ·2026-09-16 ·Eyal En Gad
highly cited similarity 0.60
Abstract · Extended to arbitrary fixed alphabets, mixed edits, and bounded substring edits; simplified proof using binary linear hashing

We reduce the leading redundancy coefficient for binary codes correcting any fixed number $t\ge2$ of deletions from $2t$ to $2t-1$. This is the first improvement to that coefficient since Levenshtein's 1965 bound. More generally, over every fixed alphabet of size $q\ge2$, codes of length $n$ correcting any combination of at most $t$ insertions, deletions and substitutions exist with redundancy $(2t-1)\log_q n+O_t(\log_q\log_q n)$. For two deletions, the upper-bound coefficient drops from $4$ to $3$, halving the gap to the lower-bound coefficient $2$. The leading coefficient $2t-1$ also holds for $t$ bounded substring edits, where both the removed and inserted strings have bounded length. The proof combines random binary linear hashing of substring counts with a two-colouring argument. A linear dependence among differences of substring-count vectors forces their local changes to overlap, and this overlap lowers the redundancy coefficient from $2t$ to $2t-1$. The result provides an edit-distance analogue of Varshamov's 1957 bound in the Hamming metric, both in the leading redundancy coefficient and in the role of linear independence in the proof.

0.51

Minimum Synthesis Time for Single-Deletion Correcting Codes of Prescribed Size

cs.IT ·2026-11-10 ·Yuling Li, Wenjun Yu, Gennian Ge
similarity 0.59
Abstract

DNA is a promising medium for data storage, but the high cost of DNA synthesis remains a major obstacle to its widespread deployment. In the reference-based synthesis model, synthesis time is measured by the length of the reference sequence. Previous studies have analyzed code sizes under synthesis-time constraints and constructed cost-constrained codes, including codes that correct deletions. In this paper, we study the minimum synthesis time for codes of prescribed size, considering both unrestricted codes and single-deletion correcting codes. We establish finite-length lower bounds valid for arbitrary reference sequences and upper bounds using existing $q$-ary differential VT codes. For fixed $q\geq3$, $A>0$, and $R\in(0,1)$, we determine the minimum synthesis time up to an $O(1)$ term when the code size is $M_n=\lfloor Aq^{Rn}\rfloor$. The corresponding redundancy is $(1-R)n\log_2q-\log_2A+o(1)$ bits. In particular, for these code sizes, the minimum synthesis time for single-deletion correcting codes exceeds that for unrestricted codes by a term proportional to $\ln n$, and we determine its coefficient. We also derive upper and lower bounds for code sizes $\lfloor q^n/(nq^{s_n})\rfloor$, where $s_n\to\infty$ and $s_n=o(n)$. These sizes correspond to redundancy $\log_2 n+s_n\log_2q+o(1)$ bits. For code sizes $\lfloor q^n/(nq^c)\rfloor$ with fixed constant $c$, the redundancy is $\log_2 n+c\log_2q+o(1)$ bits. We give conditions under which single-deletion correcting codes exist or do not exist for all sufficiently large $n$, together with bounds on the minimum synthesis time. These results show how code size and the single-deletion correcting constraint affect synthesis time and provide theoretical guidance for the construction of cost-constrained codes.

0.24

Parity and Pattern Detection in Permutation Streams

cs.DS ·2026-09-08 ·Mark Braverman, Or Zamir
similarity 0.58
Abstract

Consider a permutation of $[n]$ whose values arrive one at a time. We resolve two questions about the space needed to decide natural properties of such input: First, computing the parity of the permutation requires $Θ(n)$ bits, even with randomization and constant error, and a constant number of passes. Second, every permutation pattern of length three can be detected deterministically in one pass using $O(\log n)$ bits. Together with the 2026 lower bounds of Berendsohn, this completes the classification of fixed permutation patterns; The optimal space complexity is $Θ(\log n)$ for monotone patterns and patterns of length at most three, and $Θ(n)$ for every other pattern. As a consequence, we observe that we can verify BST traversals in streaming with logarithmic memory.

0.43