2021/07/24 by Xi Chen, Chen, Xi, Anindya De +7
Arts and Humanities · Biochemistry, Genetics and Molecular Biology · Environmental Science · #68Q17 #68Q25 (Primary) 68Q32 #68Q87 #68W32 #68W40 (Secondary) #Data Structures and Algorithms (cs.DS) #Digital and Traditional Archives Management #Discrete Mathematics (cs.DM) #Environmental DNA in Biodiversity Studies #F.2.0 #FOS: Computer and information sciences #G.3 #Molecular Biology Techniques and Applications
paper · pdf · doi:10.48550/arxiv.2107.11530
openalex publication_date 2021/07/24 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
In the standard trace reconstruction problem, the goal is to exactly reconstruct an unknown source string x ∈ \0,1\n from independent "traces", which are copies of x that have been corrupted by a δ-deletion channel which independently deletes each bit of x with probability δ and concatenates the surviving bits. We study the approximate trace reconstruction problem, in which the goal is only to obtain a high-accuracy approximation of x rather than an exact reconstruction. We give an efficient algorithm, and a near-matching lower bound, for approximate reconstruction of a random source string x ∈ \0,1\n from few traces. Our main algorithmic result is a polynomial-time algorithm with the following property: for any deletion rate 0 < δ< 1 (which may depend on n), for almost every source string x ∈ \0,1\n, given any number M ≤ Θ(1/δ) of traces from Delδ(x), the algorithm constructs a hypothesis string \widehatx that has edit distance at most n ⋅ (δM)Ω(M) from x. We also prove a near-matching information-theoretic lower bound showing that given M ≤ Θ(1/δ) traces from Delδ(x) for a random n-bit string x, the smallest possible expected edit distance that any algorithm can achieve, regardless of its running time, is n ⋅ (δM)O(M).