Reconstruction algorithms for DNA-storage systems
Reconstruction algorithms for DNA-storage systems
复制标题
DNA 存储系统的重建算法
DOI：
10.1101/2020.09.16.300186
复制
发表时间：
2020
影响因子：
4.6
通讯作者：
Eitan Yaakobi
中科院分区：
文献类型：
--
作者：
Omer Sabary;Alexander Yucovich;Guy Shapira;Eitan Yaakobi
在迹重建问题中，长度为n的字符串x产生一组噪声副本，称为迹，y1，…，yt，其中每个yi都是通过删除通道从x独立获得的，该通道以一定的固定概率删除每个符号。该范例的主要目标是确定所需的最小i.i.d迹线数量，以便高概率地重建x。跟踪重建问题可以扩展到模型，其中每个跟踪都是x通过删除-插入-替换通道的结果，该通道还引入了插入和替换。受DNA存储通道的启发，本研究的重点是DNA重构问题的另一种变体。DNA重建算法是一种映射，它接收t条轨迹y1，…，yt作为输入，并产生x的估计。DNA重建问题的目标是最小化原始字符串与算法估计之间的编辑距离。对于缺失通道，问题涉及到缺失DNA重构问题，目标是最小化Levenshtein距离。在这项工作中，我们提出了几个新的算法来解决这些重建问题。我们的算法着眼于整个轨迹序列的全局，并使用动态规划算法，这是用于最短公共超序列和最长公共子序列问题，以解码原始序列。我们的算法不需要输入和跟踪数的任何限制，更重要的是，即使错误概率高达0.27，它们也表现良好。这些算法已经在模拟数据和以前的DNA实验数据上进行了测试，并被证明优于以前所有的算法。
In the trace reconstruction problem a length-n string x yields a collection of noisy copies, called traces, y1, …, yt where each yi is independently obtained from x by passing through a deletion channel, which deletes every symbol with some fixed probability. The main goal under this paradigm is to determine the required minimum number of i.i.d traces in order to reconstruct x with high probability. The trace reconstruction problem can be extended to the model where each trace is a result of x passing through a deletion-insertion-substitution channel, which introduces also insertions and substitutions. Motivated by the storage channel of DNA, this work is focused on another variation of the trace reconstruction problem, which is referred by the DNA reconstruction problem. A DNA reconstruction algorithm is a mapping which receives t traces y1, …, yt as an input and produces , an estimation of x. The goal in the DNA reconstruction problem is to minimize the edit distance between the original string and the algorithm’s estimation. For the deletion channel case, the problem is referred by the deletion DNA reconstruction problem and the goal is to minimize the Levenshtein distance . In this work, we present several new algorithms for these reconstruction problems. Our algorithms look globally on the entire sequence of the traces and use dynamic programming algorithms, which are used for the shortest common supersequence and the longest common subsequence problems, in order to decode the original sequence. Our algorithms do not require any limitations on the input and the number of traces, and more than that, they perform well even for error probabilities as high as 0.27. The algorithms have been tested on simulated data as well as on data from previous DNA experiments and are shown to outperform all previous algorithms.
DOI：
10.1109/isit.2018.8437519
发表时间：
2018-06
期刊：
2018 IEEE International Symposium on Information Theory (ISIT)
影响因子：
--
作者：
Sundara Rajan Srinivasavaradhan;M. Du;S. Diggavi;C. Fragouli
通讯作者：
Sundara Rajan Srinivasavaradhan;M. Du;S. Diggavi;C. Fragouli