A Caltech Library Service

Trace Reconstruction with Bounded Edit Distance

Sima, Jin and Bruck, Jehoshua (2021) Trace Reconstruction with Bounded Edit Distance. Parallel and Distributed Systems Group Technical Reports, etr152. California Institute of Technology , Pasadena, CA. (Unpublished)

[img] PDF - Submitted Version
See Usage Policy.


Use this Persistent URL to link to this item:


The trace reconstruction problem studies the number of noisy samples needed to recover an unknown string x ∈ {0, 1}^n with high probability, where the samples are independently obtained by passing x through a random deletion channel with deletion probability p. The problem is receiving significant attention recently due to its applications in DNA sequencing and DNA storage. Yet, there is still an exponential gap between upper and lower bounds for the trace reconstruction problem. In this paper we study the trace reconstruction problem when x is confined to an edit distance ball of radius k, which is essentially equivalent to distinguishing two strings with edit distance at most k. It is shown that n O(k) samples suffice to achieve this task with high probability.

Item Type:Report or Paper (Technical Report)
Related URLs:
URLURL TypeDescription Report ItemIEEE Conference Paper
Sima, Jin0000-0003-4588-9790
Bruck, Jehoshua0000-0001-8474-0812
Group:Parallel and Distributed Systems Group
Series Name:Parallel and Distributed Systems Group Technical Reports
Issue or Number:etr152
Record Number:CaltechAUTHORS:20210624-215307865
Persistent URL:
Usage Policy:No commercial reproduction, distribution, display or performance rights in this work are provided.
ID Code:109575
Deposited By: George Porter
Deposited On:25 Jun 2021 14:55
Last Modified:10 Nov 2021 15:38

Repository Staff Only: item control page