Narayanan, Shyam ;
Ren, Michael
Circular Trace Reconstruction
Abstract
Trace reconstruction is the problem of learning an unknown string x from independent traces of x, where traces are generated by independently deleting each bit of x with some deletion probability q. In this paper, we initiate the study of Circular trace reconstruction, where the unknown string x is circular and traces are now rotated by a random cyclic shift. Trace reconstruction is related to many computational biology problems studying DNA, which is a primary motivation for this problem as well, as many types of DNA are known to be circular.
Our main results are as follows. First, we prove that we can reconstruct arbitrary circular strings of length n using exp(Õ(n^{1/3})) traces for any constant deletion probability q, as long as n is prime or the product of two primes. For n of this form, this nearly matches what was the best known bound of exp(O(n^{1/3})) for standard trace reconstruction when this paper was initially released. We note, however, that Chase very recently improved the standard trace reconstruction bound to exp(Õ(n^{1/5})). Next, we prove that we can reconstruct random circular strings with high probability using n^O(1) traces for any constant deletion probability q. Finally, we prove a lower bound of Ω̃(n³) traces for arbitrary circular strings, which is greater than the best known lower bound of Ω̃(n^{3/2}) in standard trace reconstruction.
BibTeX  Entry
@InProceedings{narayanan_et_al:LIPIcs.ITCS.2021.18,
author = {Shyam Narayanan and Michael Ren},
title = {{Circular Trace Reconstruction}},
booktitle = {12th Innovations in Theoretical Computer Science Conference (ITCS 2021)},
pages = {18:118:18},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783959771771},
ISSN = {18688969},
year = {2021},
volume = {185},
editor = {James R. Lee},
publisher = {Schloss DagstuhlLeibnizZentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/opus/volltexte/2021/13557},
URN = {urn:nbn:de:0030drops135573},
doi = {10.4230/LIPIcs.ITCS.2021.18},
annote = {Keywords: Trace Reconstruction, Deletion Channel, Cyclotomic Integers}
}
04.02.2021
Keywords: 

Trace Reconstruction, Deletion Channel, Cyclotomic Integers 
Seminar: 

12th Innovations in Theoretical Computer Science Conference (ITCS 2021)

Issue date: 

2021 
Date of publication: 

04.02.2021 