Levenshtein’s sequence reconstruction model plays an essential role in information retrieval in DNA-based storage systems. In this model, a word ${\text{x}} \in {\mathbb{Z}}_q^n$ is transmitted through N noisy channels, and the goal is to recover the original word exactly, or with a small uncertainty ${\mathcal{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 ${\mathcal{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.

In this article, we study the cardinality of the intersection of multiple q-ary Hamming balls for q ≥ 3. The problem has previously been studied in the binary case and for two balls in the case of q ≥ 3. When each ball has radius t and they are centered at words of a set S, we present a link between the asymptotic size of the cardinality and the center of the set S. For exactly three balls, we consider the largest and smallest possible intersection sizes and possible sets S leading to them. The intersections of Hamming balls have been the focus of multiple studies recently, due to their connections to Levenshtein’s sequence reconstruction problem and DNA memory systems, where the information is stored into DNA strands. The case with q = 4 is especially important for applications related to DNA due to the four nucleotides of DNA.