TU1.R6.3

Sequence Reconstruction over 3-Deletion Channels

Di Zhang, Shandong University, China; Gennian Ge, Capital Normal University, China; Yiwei Zhang, Shandong University, China

Session:
Biology: sequence reconstruction

Track:
17: Information and Coding in Biology

Location:
Sigma/Delta

Presentation Time:
Tue, 9 Jul, 10:25 - 10:45

Session Chair:
Netanel Raviv, Washington University in St. Louis
Abstract
In 2001, Levenshtein proposed the sequence reconstruction problem under various channels, indicating that the core problem is to determine the maximum size of the intersection of two error balls centered at two distinct codewords from a certain codebook. For the 3-deletion channel, let $\mathcal{D}_3(\bm{x})$ be the the error ball centered at $\bm{x}\in\{0,1\}^n$. In this paper, we consider the sequence reconstruction problem for the 3-deletion channel, when the codebook is an arbitrary 2-deletion correcting code. Pham et al. [IEEE ISIT2022, pp. 992-997] has shown that the maximum size of the intersection of two error balls in this setting is upper bounded by 20, and thus 21 distinct reads are sufficient for unique reconstruction. Our main contribution is to explicitly characterize the pair of codewords $(\bm{x},\bm{y})$ such that $\mathcal{D}_3(\bm{x})\cap\mathcal{D}_3(\bm{y})\in\{19,20\}$, which will shed light on the design of reconstruction codes for a smaller number of reads.
Resources