Rank-Modulation Codes for DNA Storage With Shotgun Sequencing
Rank-Modulation Codes for DNA Storage With Shotgun Sequencing
复制标题
使用鸟枪测序进行 DNA 存储的等级调制代码
DOI：
--
复制
发表时间：
2019
影响因子：
2.5
通讯作者：
Eitan Yaakobi
中科院分区：
文献类型：
--
作者：
Netanel Raviv;Moshe Schwartz;Eitan Yaakobi
DNA分子的合成为存储技术带来了前所未有的进步。然而，这些分子所处的微观世界引起的错误模式与它们的数字对应物根本不同。因此，为了保持阅读和写的可靠性，必须开发新的编码方案。在称为鸟枪测序的阅读技术中，以滑动窗口方式读取长DNA串，并产生轮廓载体。Kiah等人最近提出，这样的向量可以表示由其条目引起的置换，因此出现了秩调制方案。虽然这种解释表明高容错性，但尚不清楚哪些排列是可行的，以及如何产生其轮廓向量诱导给定排列的DNA串。本文通过满足一些必要条件，给出了可行置换个数的一个上界。此外，设计了一种用于确定置换的可行性的技术。通过使用这种技术的见解，一个算法产生了相当数量的可行的排列，它适用于任何字母表的大小和任何窗口长度。
Synthesis of DNA molecules offers unprecedented advances in storage technology. Yet, the microscopic world in which these molecules reside induces error patterns that are fundamentally different from their digital counterparts. Hence, to maintain reliability in reading and writing, new coding schemes must be developed. In a reading technique called shotgun sequencing, a long DNA string is read in a sliding window fashion, and a profile vector is produced. It was recently suggested by Kiah et al. that such a vector can represent the permutation which is induced by its entries, and hence a rank-modulation scheme arises. Although this interpretation suggests high error tolerance, it is unclear which permutations are feasible and how to produce a DNA string whose profile vector induces a given permutation. In this paper, by observing some necessary conditions, an upper bound for the number of feasible permutations is given. Furthermore, a technique for deciding the feasibility of a permutation is devised. By using insights from this technique, an algorithm for producing a considerable number of feasible permutations is given, which applies to any alphabet size and any window length.