On Levenshtein’s Reconstruction Problem Under Insertions, Deletions, and Substitutions
Maria Abu-Sini, Eitan Yaakobi
Abstract
The <italic xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">sequence reconstruction problem</i> corresponds to the model in which a sequence from some code is transmitted over several noisy channels that produce distinct outputs. Then, the channels’ outputs, received by the decoder, are used to recover the transmitted sequence, and the main problem under this paradigm is to calculate the minimum number of channels that enables unique reconstruction of the transmitted word. This problem is equivalent to finding the size of the largest intersection of channels’ outputs sets received after transmitting distinct codewords. Motivated by the error behavior observed in DNA storage systems, the present work extends the study of the reconstruction model to the case in which a binary word is transmitted over channels prone to substitutions, insertions, and deletions. Furthermore, we also study the size of the error balls generated by either one deletion and at most a fixed number of substitutions or one insertion and at most one substitution in a binary word. For the case of only substitutions, we present a decoder of optimal complexity, which improves upon a recent construction of such a decoder. Lastly, a simplification of that decoder is studied in case there are more channels than the minimum required number.