On Sequence Reconstruction Problem for q-ary Deletion Channels
Abstract
The sequence reconstruction problem for q-ary deletion channels, introduced by Levenshtein in 2001, concerns the minimum number of channels required to uniquely recover a transmitted sequence when each channel introduces exactly t deletions. Combinatorially, it is equivalent to determining Nq(n,d,t), the maximum intersection size of two t-deletion balls with centers at Levenshtein distance at least d, for q-ary sequences of length n over the alphabet Σq={0,1,…,q−1}. Levenshtein solved the uncoded case Nq(n,1,t) for all n≥ t; subsequently, Gabrys and Yaakobi determined N2(n,2,t), and Wang et al. extended the result to N3(n,2,t). In this paper, we study the problem for q-ary sequences under minimum Levenshtein distance d=2 with channels that introduce exactly t deletions. We determine the exact value of Nq(n,2,t) for all t≥ 2, q≥ 4, and for sufficiently large n, and construct explicit pairs of sequences attaining the maximum intersection. Furthermore, for each q≥3, we characterize all extremal sequence pairs. In particular, if the intersection size matches the first two terms of Nq(n,2,t), then the two center sequences must contain, at the same positions, length-5 blocks of the forms (a,b,c,a,b) and (b,a,c,b,a) for some distinct a,b,c∈Σq; for t≥ q+2, the exact maximum Nq(n,2,t) is attained precisely by 2q! unordered pairs of sequences with a specific block structure. Asymptotically, we prove that for q≥ 4 and t≥ 2, Nq(n,2,t)=6/((t−2)!)nt−2−(3t+13)/((t−3)!)nt−3+(3t2+25t+64)/(4(t−4)!)nt−4+O(nt−5). Moreover, Nq(n,2,t) and Nq−1(n,2,t) share their first q−1 terms, and for t≥ q the coefficient of nt−q in their difference is (6t−6q+5)/((t−q)!).
Related
- Maximal input entropy for binary two-deletion and two-insertion channels
- Orbit Reduction and Learned Run Distributions for Finite-Blocklength Binary Deletion Channels
- NP-Hardness of the H-Free Edge-Deletion Problem
- Denominators in the Farey Sequence, the Stern Sequence, and the Frobenius Problem with Relatively Prime Multipliers
- Fundamental Limits of Sequence Reconstruction Problems in Immunogenomics
BibTeX
@misc{wang2026sequence,
title = {{On Sequence Reconstruction Problem for q-ary Deletion Channels}},
author = {Xiang Wang and Han Li and Fang-Wei Fu},
howpublished = {arXiv},
year = {2026},
month = sep,
doi = {10.48550/arxiv.2609.16837},
eprint = {2609.16837},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2609.16837},
}
RIS
TY - UNPB
TI - On Sequence Reconstruction Problem for q-ary Deletion Channels
AU - Xiang Wang
AU - Han Li
AU - Fang-Wei Fu
PY - 2026
DA - 2026/09/15
PB - arXiv
DO - 10.48550/arxiv.2609.16837
UR - https://arxiv.org/abs/2609.16837
AB - The sequence reconstruction problem for q-ary deletion channels, introduced by Levenshtein in 2001, concerns the minimum number of channels required to uniquely recover a transmitted sequence when each channel introduces exactly t deletions. Combinatorially, it is equivalent to determining N_q(n,d,t), the maximum intersection size of two t-deletion balls with centers at Levenshtein distance at least d, for q-ary sequences of length n over the alphabet Σ_q={0,1,…,q−1}. Levenshtein solved the uncoded case N_q(n,1,t) for all n≥ t; subsequently, Gabrys and Yaakobi determined N_2(n,2,t), and Wang et al. extended the result to N_3(n,2,t). In this paper, we study the problem for q-ary sequences under minimum Levenshtein distance d=2 with channels that introduce exactly t deletions. We determine the exact value of N_q(n,2,t) for all t≥ 2, q≥ 4, and for sufficiently large n, and construct explicit pairs of sequences attaining the maximum intersection. Furthermore, for each q≥3, we characterize all extremal sequence pairs. In particular, if the intersection size matches the first two terms of N_q(n,2,t), then the two center sequences must contain, at the same positions, length-5 blocks of the forms (a,b,c,a,b) and (b,a,c,b,a) for some distinct a,b,c∈Σ_q; for t≥ q+2, the exact maximum N_q(n,2,t) is attained precisely by 2q! unordered pairs of sequences with a specific block structure. Asymptotically, we prove that for q≥ 4 and t≥ 2, N_q(n,2,t)=6/((t−2)!)n^t−2−(3t+13)/((t−3)!)n^t−3+(3t^2+25t+64)/(4(t−4)!)n^t−4+O(n^t−5). Moreover, N_q(n,2,t) and N_q−1(n,2,t) share their first q−1 terms, and for t≥ q the coefficient of n^t−q in their difference is (6t−6q+5)/((t−q)!).
ER -