← 研踪 PaperTrailarXiv: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
摘要
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 -ary differential VT codes. For fixed , , and , we determine the minimum synthesis time up to an term when the code size is . The corresponding redundancy is 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 , and we determine its coefficient. We also derive upper and lower bounds for code sizes , where and . These sizes correspond to redundancy bits. For code sizes with fixed constant , the redundancy is bits. We give conditions under which single-deletion correcting codes exist or do not exist for all sufficiently large , 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.
观测到的版本
相邻记录可能跳过中间版本;首次发现 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 -ary differential VT codes. For fixed , , and , we determine the minimum synthesis time up to an term when the code size is . The corresponding redundancy is 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 , and we determine its coefficient. We also derive upper and lower bounds for code sizes , where and . These sizes correspond to redundancy bits. For code sizes with fixed constant , the redundancy is bits. We give conditions under which single-deletion correcting codes exist or do not exist for all sufficiently large , 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.
查看此版本解读 →查看此版本原文 ↗