Sequence Reconstruction Under Single-Burst-Insertion/Deletion/Edit Channel
Yubo Sun, Yuanxiao Xi, Gennian Ge
Abstract
Motivated by applications in modern storage devices such as DNA storage and racetrack memories, we study the sequence reconstruction problem which involves two important issues. One is determining the maximum intersection size between two error balls. The other is designing reconstruction codes in which each transmitted sequence can be reconstructed from a given number of noisy reads with redundancy as small as possible. In this paper, we focus on channels that introduce single-burst-insertion/deletion error. We fully determine the maximum intersection size between two burst-insertion/deletion balls for both fixed-length and variable-length models. Then we characterize a pair of sequences when their burst-insertion/deletion balls have intersection of a certain size. Using these characterizations, we design reconstruction codes for all values <inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"> <tex-math notation="LaTeX">$N$ </tex-math></inline-formula> of the number of noisy reads and analyze their lower bounds. In addition, we extend our results to the burst-edit channel.