Trace Reconstruction with Bounded Edit Distance
- Creators
- Sima, Jin
- Bruck, Jehoshua
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.
Attached Files
Submitted - etr152.pdf
Files
Name | Size | Download all |
---|---|---|
md5:ea1a0611b4fe27c453a50210a77a4641
|
320.3 kB | Preview Download |
Additional details
- Eprint ID
- 109575
- Resolver ID
- CaltechAUTHORS:20210624-215307865
- Created
-
2021-06-25Created from EPrint's datestamp field
- Updated
-
2021-11-10Created from EPrint's last_modified field
- Caltech groups
- Parallel and Distributed Systems Group
- Series Name
- Parallel and Distributed Systems Group Technical Reports
- Series Volume or Issue Number
- etr152