论文标题
与部分重叠的子字符串重建
Reconstruction from Substrings with Partial Overlap
论文作者
论文摘要
本文介绍了一个新的重建代码系列，该家族是由DNA数据存储和测序中的应用中的。在这种应用中，通过阅读其子字节的某些子集对DNA链进行测序。虽然先前的作品考虑了两种极端情况，其中读取了一些固定长度的\ emph {All} substring，或者没有重叠而读取子字符串，但此工作考虑了以某些给定的最小重叠读取连续的子字符串的设置。首先，在可实现的代码速率上提供了上限，以保证独特的重建。然后，我们提出了符合上限的渐近最佳代码的有效构造。
This paper introduces a new family of reconstruction codes which is motivated by applications in DNA data storage and sequencing. In such applications, DNA strands are sequenced by reading some subset of their substrings. While previous works considered two extreme cases in which \emph{all} substrings of some fixed length are read or substrings are read with no overlap, this work considers the setup in which consecutive substrings are read with some given minimum overlap. First, upper bounds are provided on the attainable rates of codes that guarantee unique reconstruction. Then, we present efficient constructions of asymptotically optimal codes that meet the upper bound.
