Correcting Burst Errors with Applications to DNA-Based Data Storage
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(√n), the redundancy of any permutation burst error correcting code is at least log n−k+log binom2k−2k−2+o(1). This result follows from McDiarmid's concentration bound; b) for k ≥ 9 and k=o(√(n/(log n))), 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 ≤ k using log n + k + 49log k + O(log log k) redundant bits.
Related
- Substring Edit Correcting Codes and Optimal Single Burst-Deletion Correcting Codes
- Posterior Consistency under dependent errors in non-linear inverse problems with applications to time evolution equations
- Learning Coarse Spaces for Two-Grid Methods from Smoothed Errors with Applications to High-Contrast Porous Media Flow
- Plotkin-Like Bound and Explicit Function-Correcting Code Constructions for Lee Metric Channels
- Four New Single-Error-Correcting Binary Codes
BibTeX
@misc{chen2026correcting,
title = {{Correcting Burst Errors with Applications to DNA-Based Data Storage}},
author = {Yuan-Pon Chen and Olgica Milenkovic},
howpublished = {arXiv},
year = {2026},
month = oct,
doi = {10.48550/arxiv.2610.15701},
eprint = {2610.15701},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2610.15701},
}
RIS
TY - UNPB
TI - Correcting Burst Errors with Applications to DNA-Based Data Storage
AU - Yuan-Pon Chen
AU - Olgica Milenkovic
PY - 2026
DA - 2026/10/11
PB - arXiv
DO - 10.48550/arxiv.2610.15701
UR - https://arxiv.org/abs/2610.15701
AB - 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(√n), the redundancy of any permutation burst error correcting code is at least log n−k+log binom2k−2k−2+o(1). This result follows from McDiarmid's concentration bound; b) for k ≥ 9 and k=o(√(n/(log n))), 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 ≤ k using log n + k + 49log k + O(log log k) redundant bits.
ER -