Reconstruction of Sequences in DNA Storage
Reconstruction of Sequences in DNA Storage
复制标题
DNA 存储中的序列重建
DOI：
--
复制
发表时间：
2019
期刊：
影响因子：
--
通讯作者：
Eitan Yaakobi
中科院分区：
文献类型：
--
作者：
M. Sini;Eitan Yaakobi
序列重构问题对应于一个模型，在该模型中，来自某个码的序列在几个有噪声的信道上传输。这些通道几乎是独立的，因为只需要它们的输出不同即可。该范例下的主要问题是确定重建传输序列所需的最小信道数。这个问题等价于求任意两个输入的两个球之间的最大交集大小，其中球都是可能的通道输出。受DNA存储通道中的错误行为的启发，本工作将这项研究扩展到通道容易发生替换、插入和缺失的情况。对于只有替换的情况，我们还提出了一个最优复杂度的解码器，它改进了最近构造的这样一个解码器。最后，还研究了在信道数目超过最小要求数目的情况下如何简化解码器。
The sequence reconstruction problem corresponds to a model in which a sequence from some code is transmitted over several noisy channels. The channels are almost independent as it is only required that their outputs are different. The main problem under this paradigm is to determine the minimum number of channels required to reconstruct the transmitted sequence. This problem is equivalent to finding the maximum intersection size between two balls of any possible two inputs, where the balls are all possible channel outputs. Motivated by the error behavior in the DNA storage channel, this work extends this study to the case where the channels are prone to substitutions, insertions, and deletions. For the case of only substitutions, we also present a decoder of optimal complexity, which improves upon a recent construction of such a decoder. Lastly, it is also studied how the decoder is simplified in case there are more channels than the minimum required number.