跳到正文
研踪PaperTrail
← 研踪 PaperTrail

arXiv:2611.13434 · v1

Minimum Synthesis Time for Single-Deletion Correcting Codes of Prescribed Size

首次提交 2026-11-10 09:16
版本更新 2026-11-10 09:16
雷达观测 2026-11-11 11:04
arXiv ↗PDF ↗

摘要

DNA is a promising medium for data storage, but the high cost of DNA synthesis remains a major obstacle to its widespread deployment. In the reference-based synthesis model, synthesis time is measured by the length of the reference sequence. Previous studies have analyzed code sizes under synthesis-time constraints and constructed cost-constrained codes, including codes that correct deletions. In this paper, we study the minimum synthesis time for codes of prescribed size, considering both unrestricted codes and single-deletion correcting codes. We establish finite-length lower bounds valid for arbitrary reference sequences and upper bounds using existing qq-ary differential VT codes. For fixed q≥3q\geq3, A>0A>0, and R∈(0,1)R\in(0,1), we determine the minimum synthesis time up to an O(1)O(1) term when the code size is Mn=⌊AqRn⌋M_n=\lfloor Aq^{Rn}\rfloor. The corresponding redundancy is (1−R)nlog⁡2q−log⁡2A+o(1)(1-R)n\log_2q-\log_2A+o(1) bits. In particular, for these code sizes, the minimum synthesis time for single-deletion correcting codes exceeds that for unrestricted codes by a term proportional to ln⁡n\ln n, and we determine its coefficient. We also derive upper and lower bounds for code sizes ⌊qn/(nqsn)⌋\lfloor q^n/(nq^{s_n})\rfloor, where sn→∞s_n\to\infty and sn=o(n)s_n=o(n). These sizes correspond to redundancy log⁡2n+snlog⁡2q+o(1)\log_2 n+s_n\log_2q+o(1) bits. For code sizes ⌊qn/(nqc)⌋\lfloor q^n/(nq^c)\rfloor with fixed constant cc, the redundancy is log⁡2n+clog⁡2q+o(1)\log_2 n+c\log_2q+o(1) bits. We give conditions under which single-deletion correcting codes exist or do not exist for all sufficiently large nn, together with bounds on the minimum synthesis time. These results show how code size and the single-deletion correcting constraint affect synthesis time and provide theoretical guidance for the construction of cost-constrained codes.

AI 论文解读

基于摘要 · 非全文审阅

此版本尚未生成 AI 解读。解读由后台任务生成并按论文版本保存,登录后共享已有结果。

版本差异

目前只收录了一个版本。收录下一版后,可以对照标题、作者、分类和摘要。

观测到的版本

相邻记录可能跳过中间版本;首次发现 v2 及以上也会标为版本更新。

v1 · 2026-11-10 09:16 · 最新观测版本

Minimum Synthesis Time for Single-Deletion Correcting Codes of Prescribed Size

DNA is a promising medium for data storage, but the high cost of DNA synthesis remains a major obstacle to its widespread deployment. In the reference-based synthesis model, synthesis time is measured by the length of the reference sequence. Previous studies have analyzed code sizes under synthesis-time constraints and constructed cost-constrained codes, including codes that correct deletions. In this paper, we study the minimum synthesis time for codes of prescribed size, considering both unrestricted codes and single-deletion correcting codes. We establish finite-length lower bounds valid for arbitrary reference sequences and upper bounds using existing qq-ary differential VT codes. For fixed q≥3q\geq3, A>0A>0, and R∈(0,1)R\in(0,1), we determine the minimum synthesis time up to an O(1)O(1) term when the code size is Mn=⌊AqRn⌋M_n=\lfloor Aq^{Rn}\rfloor. The corresponding redundancy is (1−R)nlog⁡2q−log⁡2A+o(1)(1-R)n\log_2q-\log_2A+o(1) bits. In particular, for these code sizes, the minimum synthesis time for single-deletion correcting codes exceeds that for unrestricted codes by a term proportional to ln⁡n\ln n, and we determine its coefficient. We also derive upper and lower bounds for code sizes ⌊qn/(nqsn)⌋\lfloor q^n/(nq^{s_n})\rfloor, where sn→∞s_n\to\infty and sn=o(n)s_n=o(n). These sizes correspond to redundancy log⁡2n+snlog⁡2q+o(1)\log_2 n+s_n\log_2q+o(1) bits. For code sizes ⌊qn/(nqc)⌋\lfloor q^n/(nq^c)\rfloor with fixed constant cc, the redundancy is log⁡2n+clog⁡2q+o(1)\log_2 n+c\log_2q+o(1) bits. We give conditions under which single-deletion correcting codes exist or do not exist for all sufficiently large nn, together with bounds on the minimum synthesis time. These results show how code size and the single-deletion correcting constraint affect synthesis time and provide theoretical guidance for the construction of cost-constrained codes.

查看此版本解读 →查看此版本原文 ↗