How to Find Simple Conditions for Successful Sequence Reconstruction?

We study a model in which a codeword <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">$x$</tex> is transmitted through several identical channels, where each channel produces a noisy read of <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">$x$</tex>. The sequence reconstruction problem, proposed by Levenshtein, asks for how to uniquely re-construct <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">$x$</tex> based on these noisy reads. Most of previous works focused on the minimum number of reads which guarantees unique reconstruction of <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">$x$</tex> in the worst case. In this paper, we move on to a new perspective on the sequence reconstruction problem, and propose a different sufficient condition for unique reconstruction which takes both the number of reads and the distances among the reads into consideration. We offer both theoretical analysis and corresponding efficient reconstruction algorithms.