CaltechAUTHORS
  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) https://resolver.caltech.edu/CaltechAUTHORS:20210624-215307865

[img] PDF - Submitted Version
See Usage Policy.

320kB

Use this Persistent URL to link to this item: https://resolver.caltech.edu/CaltechAUTHORS:20210624-215307865

Abstract

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
http://www.paradise.caltech.edu/papers/etr152.pdfAuthorTechnical Report
ORCID:
AuthorORCID
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:https://resolver.caltech.edu/CaltechAUTHORS:20210624-215307865
Usage Policy:No commercial reproduction, distribution, display or performance rights in this work are provided.
ID Code:109575
Collection:CaltechAUTHORS
Deposited By: George Porter
Deposited On:25 Jun 2021 14:55
Last Modified:25 Jun 2021 14:55

Repository Staff Only: item control page