Backend
Minimum Synthesis Time for Single-Deletion Correcting Codes of Prescribed Size
arXiv math.IT0 views
arXiv:2611.13434v1 Announce Type: new Abstract: 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 $q$-ary differential VT codes. For fixed $q\geq3$, $A>0$, and $R\in(0,1)$, we determine the minimum synthesis time up to an $O(1)$ term when the code size is $M_n=\lfloor Aq^{Rn}\rfloor$. The corresponding redundancy is $(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$, and we determine its coefficient. We also derive upper and lower bounds for code sizes $\lfloor q^n/(nq^{s_n})\rfloor$, where $s_n\to\infty$ and $s_n=o(n)$. These sizes correspond to redundancy $\log_2 n+s_n\log_2q+o(1)$ bits. For code sizes $\lfloor q^n/(nq^c)\rfloor$ with fixed constant $c$, the redundancy is $\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 $n$, 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.
Source:https://arxiv.org/abs/2611.13434PreviousThe Optimal Constant for One-Shot Channel Simulation and Strong Functional Representation LemmaNextEuclidean Hulls of Double Cyclic Codes of Arbitrary Block Lengths
Related posts
Postgres 14 hits end of life on November 12
0dev.to

MySQL to Snowflake: Binlog CDC Without Kafka or Debezium, Step by Step
0dev.to
Node.js Template Ownership: 3 PDF Watermark API Decisions Before Sharing SaaS Reports
0dev.to
I Built an Open-Source Tool to Test What Happens When MCP Servers Fail
0dev.to
Streamlining complex Helm tooling reduces team overhead and administrative friction
0dev.to

100% annotation agreement can mean one labelled record out of twelve
0dev.to