Sequence Reconstruction for Substitution Channel: New Sufficient Conditions and Algorithms
It offers a more flexible sufficient condition for unique reconstruction, benefiting coding theory and DNA storage applications.
The paper proposes a new framework for unique sequence reconstruction from noisy reads over a substitution channel, considering both the number of reads and their pairwise distances, and provides efficient reconstruction algorithms.
In the sequence reconstruction problem, a codeword $\x$ is transmitted through several identical channels where each channel produces a noisy read of $\x$, and the problem is to analyze how to uniquely reconstruct $\x$ based on these noisy reads. Levenshtein has studied the minimum number of reads which guarantees unique reconstruction of $\x$, which is one sufficient condition for unique reconstruction. In this paper, we move on to a different perspective and propose a new framework for unique reconstruction. Our new sufficient condition for unique reconstruction takes both the number of reads and the distances among the reads into consideration. We offer both theoretical analysis and corresponding efficient reconstruction algorithms for our reconstruction framework.