Sequence Reconstruction for the Single-Deletion Single-Substitution Channel

The central problem in sequence reconstruction is to find the minimum number of distinct channel outputs required to uniquely reconstruct the transmitted sequence. According to Levenshtein’s work in 2001, this number is determined by the size of the maximum intersection between the error balls of any two distinct input sequences of the channel. In this work, we study the sequence reconstruction problem for the q-ary single-deletion single-substitution channel for any fixed integer <inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"> <tex-math notation="LaTeX">$q\geq 2$ </tex-math></inline-formula>. First, we prove that if two q-ary sequences of length n have a Hamming distance <inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"> <tex-math notation="LaTeX">$d\geq 2$ </tex-math></inline-formula>, then the intersection size of their error balls is upper bounded by <inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"> <tex-math notation="LaTeX">$2qn-3q-2-\delta _{q,2}$ </tex-math></inline-formula>, where <inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"> <tex-math notation="LaTeX">$\delta _{i,j}$ </tex-math></inline-formula> is the Kronecker delta, and this bound is achievable. Next, we prove that if two q-ary sequences have a Hamming distance <inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"> <tex-math notation="LaTeX">$d\geq 3$ </tex-math></inline-formula> and a Levenshtein distance <inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"> <tex-math notation="LaTeX">$d_{\text {L}}\geq 2$ </tex-math></inline-formula>, then the intersection size of their error balls is upper bounded by <inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"> <tex-math notation="LaTeX">$3q+11$ </tex-math></inline-formula>, and we show that the gap between this bound and the tight bound is at most 2.