论文标题
循环痕量重建
Circular Trace Reconstruction
论文作者
论文摘要
跟踪重建是从$ x $的独立痕迹中学习一个未知字符串$ x $的问题，其中通过使用一些删除概率$ q $独立删除$ x $的每一点来生成轨迹。在本文中，我们启动了循环痕量重建的研究，其中未知字符串$ x $是圆形的，现在通过随机循环移动旋转迹线。痕量重建与许多研究DNA的计算生物学问题有关，这也是该问题的主要动机，因为已知许多类型的DNA都是圆形的。 我们的主要结果如下。首先，我们证明我们可以使用$ \ exp \ big（\ tilde {o}（n^{1/3}）\ big）$ trace的任意$ n $（\ tilde {o}（n^{1/3}）$ q $ q $，只要$ n $就是$ n $是质量或两个primes的产物，就可以重建任意循环字符串。对于此表单的$ n $，这几乎与$ \ exp \ big（o（n^{1/3}）\ big）$的最著名界限是标准跟踪重建时，本文最初发行时。但是，我们注意到Chase最近改善了绑定到$ \ exp \ big（\ tilde {o}（n^{1/5}）\ big）$的标准跟踪重建。接下来，我们证明我们可以使用$ n^{o（1）} $ traces thrace to to to $ q $重建具有高概率的随机圆字符串。最后，我们证明了$ \tildeΩ（n^3）$ trace的下限，用于任意圆字符串，大于标准跟踪重建中$ \tildeΩ（n^{3/2}）$的最著名的下限。
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\big(\tilde{O}(n^{1/3})\big)$ 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\big(O(n^{1/3})\big)$ 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\big(\tilde{O}(n^{1/5})\big)$. 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 $\tildeΩ(n^3)$ traces for arbitrary circular strings, which is greater than the best known lower bound of $\tildeΩ(n^{3/2})$ in standard trace reconstruction.
