2021/07/14 by Zachary Chase, Yuval Peres, Chase, Zachary +1
Biochemistry, Genetics and Molecular Biology · Computer Science · #Advanced Data Storage Technologies #Algorithms and Data Compression #DNA and Biological Computing #FOS: Mathematics #Probability (math.PR)
paper · pdf · doi:10.48550/arxiv.2107.06454
openalex publication_date 2021/07/14 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
In the trace reconstruction problem, the goal is to reconstruct an unknown string x of length n from multiple traces obtained by passing x through the deletion channel. In the relaxed problem of approximate trace reconstruction, the goal is to reconstruct an approximation \widehatx of x which is close (within εn) to x in edit distance. We show that for most strings x, this is possible with high probability using only a constant number of traces. Crucially, this constant does not grow with n, and only depends on the deletion probability and ε.