Background
DNA data storage offers exceptional density and longevity, but its practicality is hampered by the high cost and low throughput of de novo DNA synthesis. A key cost driver in array-based synthesis is the length of a common supersequence required to encode a batch of DNA strands.
Objective
This study aims to address this cost bottleneck by investigating the optimal batch partitioning of DNA sequences. Our goal is to minimize the total synthesis cost, which is defined as the sum of the lengths of the shortest common supersequences (SCS) across all batches.
Results
Given a large pool \(\mathcal {S}\) of balanced binary sequences, which is partitioned into k batches with almost equal size, we define the total cost of \(\mathcal {S}\) to be the sum of lengths of the shortest common supersequence (SCS) of all sequences in each batch. The central problem is to determine the minimum total cost of \(\mathcal {S}\) , denoted by \(cost_k(\mathcal {S})\) , among all partitions into k batches.
Conclusions
When \(\mathcal {S}\) is the set of all balanced binary sequences of length 2n, we use combinatorial methods to obtain \(cost_2(\mathcal {S})=7n-2\) for any positive n, and \((3k+1)n-kC(k)\sqrt{n}<cost_k(\mathcal {S})\le (3k+1)n-\lfloor \frac{k}{2}\rfloor -1\) for \(k\ge 3\) and large n with C a constant depending on k. Similarly, we get \(6kn-O(k\sqrt{n})\le cost_k(\mathcal {S}')\le 2(3k+1)n-2\lfloor \frac{k}{2}\rfloor -2\) for \(k\ge 2\) and large n when \(\mathcal {S}'\) is the set of all balanced DNA sequences of length 2n. Previously, the probabilistic model of this problem was studied by Makarychev et al. (IEEE Trans Inf Theory 68:7454–7470, 2022), where strings are unconstrained or without consecutive identical letters.
