A4 Refereed article in a conference publication

On Levenshtein’s Reconstruction Problem for Channels with Unique Insertion Error Patterns




AuthorsJunnila, Ville; Laihonen, Tero K.; Lehtilä, Tuomo; Padavu Devaraj, Pavan

EditorsEl Gamal, Hesham; Evans, Jamie; Sadeghi, Parastoo; Shirvanimoghaddam, Mahyar

Conference nameIEEE Information Theory Workshop

Publication year2025

Journal: Proceedings: Information Theory Workshop

Book title 2025 IEEE Information Theory Workshop (ITW)

ISBN979-8-3315-3143-0

eISBN979-8-3315-3142-3

ISSN2475-420X

eISSN2475-4218

DOIhttps://doi.org/10.1109/ITW62417.2025.11240278

Publication's open availability at the time of reportingNo Open Access

Publication channel's open availability No Open Access publication channel

Web address https://doi.org/10.1109/itw62417.2025.11240278


Abstract

Levenshtein’s sequence reconstruction model plays an essential role in information retrieval in DNA-based storage systems. In this model, a word x∈Znq is transmitted through N noisy channels, and the goal is to recover the original word exactly, or with a small uncertainty L, using the outputs from these channels. Errors occurring in the channels usually involve substitutions, insertions or deletions. In this paper, we focus on insertion errors, which we represent using (so-called) insertion vectors. One of the main questions in this context is determining the minimum number of channels N required to recover the word either unambiguously or within a given precision L. The original formulation of Levenshtein’s reconstruction problem requires that all the outputs from the channels are distinct. However, different channels may produce the same output word even when different errors occur. In this paper, we investigate two generalized reconstruction models where the channels are allowed to produce the same output word as long as, in each channel, different errors occur (that is, the errors correspond to different insertion vectors). Our objective is to determine the number of channels N required to uniquely recover the transmitted word x under these conditions. We present several results in this direction, some of which are optimal.


Funding information in the publication
The authors were funded in part by the Research Council of Finland grants 338797 and 358718.


Last updated on 2025-24-11 at 11:58