论文标题
具有拓扑分子存储的运行长度约束的小组测试
Group Testing with Runlength Constraints for Topological Molecular Storage
论文作者
论文摘要
在基于拓扑DNA的数据存储中的应用中，我们介绍并研究了在测试矩阵的列上具有运行长度约束的非自适应组测试（NAGT）的新颖设置，因为任何两个1必须通过至少D D 0的运行进行分离。我们描述和分析了零错误和消失的误差设置中运行长度约束方案的概率构造，并证明该构建所需的测试数量是最佳的，可最佳，直到两种情况下，在Runlength约束D和缺陷d的数量中，对数因子的数量是对数因素的最佳选择。令人惊讶的是，我们的结果表明，当d = o（k）时，运行length-rength-rengtion限制的nagt并不比无限的nagt更高，并且对于D和K的几乎所有选择，它的要求都比只有圆柱锤击重量约束的nagt更高。为了获得具有良好参数的Runlength-Length-Lengention-Loctiative NAGT（QNAGT）方案，我们还为此设置提供了下限，并提供了具有柱锤重量约束的QNAGT方案的几乎最佳概率构造。
Motivated by applications in topological DNA-based data storage, we introduce and study a novel setting of Non-Adaptive Group Testing (NAGT) with runlength constraints on the columns of the test matrix, in the sense that any two 1's must be separated by a run of at least d 0's. We describe and analyze a probabilistic construction of a runlength-constrained scheme in the zero-error and vanishing error settings, and show that the number of tests required by this construction is optimal up to logarithmic factors in the runlength constraint d and the number of defectives k in both cases. Surprisingly, our results show that runlength-constrained NAGT is not more demanding than unconstrained NAGT when d=O(k), and that for almost all choices of d and k it is not more demanding than NAGT with a column Hamming weight constraint only. Towards obtaining runlength-constrained Quantitative NAGT (QNAGT) schemes with good parameters, we also provide lower bounds for this setting and a nearly optimal probabilistic construction of a QNAGT scheme with a column Hamming weight constraint.
