Coded Trace Reconstruction
Coded Trace Reconstruction
复制标题
DOI：
10.1109/tit.2020.2996377
复制
发表时间：
2020-10-01
影响因子：
2.5
通讯作者：
Ribeiro, Joao
中科院分区：
文献类型：
--
作者：
Cheraghchi, Mahdi;Gabrys, Ryan;Ribeiro, Joao
由平均案例痕量重建和针对便携式DNA的存储系统进行编码的动机，我们启动了编码的痕量重建研究，高速率有效编码代码的设计和分析，可以有效地解码，从少数读取中有很高的可能性（也是如此）称为痕迹）被编辑错误损坏。具有纳米孔测序仪的当前基于便携式DNA的存储系统中使用的代码很大程度上基于启发式方法，即使对于I.I.D的错误模型，也没有可证明的鲁棒性或性能保证。删除和恒定删除概率。我们的工作是朝着设计高效代码的第一步，并为此类系统提供了可证明的保证。我们认为恒定速率为I.D.删除并对基于标记的代码构建的分析。这引起了具有冗余o（n/ log n）（resp。O（n/ log log n））的代码，可以从EXP（O（log（log（2/3）n））进行有效重建（exp。 o（log log n）（2/3）））痕迹，其中n是消息长度。然后，我们给出一个具有O（log n）冗余位的代码的构造，如果删除概率足够小，则可以从poly（n）痕迹有效地重建。最后，我们展示了如何结合两种方法，从而使有效的代码与o（n/ log n）的冗余位相结合，可以从poly（log n）痕迹重建，以获得小恒定的删除概率。
Motivated by average-case trace reconstruction and coding for portable DNA-based storage systems, we initiate the study of coded trace reconstruction, the design and analysis of high-rate efficiently encodable codes that can be efficiently decoded with high probability from few reads (also called traces) corrupted by edit errors. Codes used in current portable DNA-based storage systems with nanopore sequencers are largely based on heuristics, and have no provable robustness or performance guarantees even for an error model with i.i.d. deletions and constant deletion probability. Our work is the first step towards the design of efficient codes with provable guarantees for such systems. We consider a constant rate of i.i.d. deletions, and perform an analysis of marker-based code-constructions. This gives rise to codes with redundancy O(n/ log n) (resp. O(n/ log log n)) that can be efficiently reconstructed from exp(O(log(2/3) n)) (resp. exp(O(log log n)(2/3))) traces, where n is the message length. Then, we give a construction of a code with O(log n) bits of redundancy that can be efficiently reconstructed from poly(n) traces if the deletion probability is small enough. Finally, we show how to combine both approaches, giving rise to an efficient code with O(n/ log n) bits of redundancy which can be reconstructed from poly(log n) traces for a small constant deletion probability.