Sequence Reconstruction over the Deletion Channel

2025/11/02 by Zhu, Fengxing
Biochemistry, Genetics and Molecular Biology · Computer Science · #DNA and Biological Computing #Cellular Automata and Applications #semigroups and automata theory

paper · pdf · doi:10.48550/arxiv.2511.01071

Abstract

In this paper, we consider the Levenshtein's sequence reconstruction problem in the case where the transmitted codeword is chosen from \0,1\ⁿ and the channel can delete up to t symbols from the transmitted codeword. We determine the minimum number of channel outputs (assuming that they are distinct) required to reconstruct a list of size ℓ-1 of candidate sequences, one of which corresponds to the original transmitted sequence. More specifically, we determine the maximum possible size of the intersection of ℓ ≥ 3 deletion balls of radius t centered at x₁, x₂, …, x_ℓ, where x_i ∈ \0,1\ⁿ for all i ∈ \1,2,…,ℓ\ and x_i ≠ x_j for i ≠ j, with n ≥ t+ ℓ-1 and t ≥ 1.

Citations

• Levenshtein's Sequence Reconstruction Problem and Results for Larger Alphabet Sizes
• The Levenshtein's Sequence Reconstruction Problem and the Length of the List
• Sequence Reconstruction Problem for Deletion Channels: A Complete Asymptotic Solution
• Exact Reconstruction from Insertions in Synchronization Codes
• DNA-Based Storage: Trends and Methods
• A characterization of the number of subsequences obtained via the deletion channel

Related

• Sequence Reconstruction Problem for Ternary Deletion Channels
• Sequence Reconstruction Problem for Deletion Channels: A Complete Asymptotic Solution
• Sequence Reconstruction under Channels with Multiple Bursts of Insertions or Deletions
• Optimal Reconstruction Codes for Deletion Channels
• Sequence Reconstruction for the Single-Deletion Single-Substitution Channel