Abstract
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 [Formula: see text] of balanced binary sequences, which is partitioned into k batches with almost equal size, we define the total cost of [Formula: see text] 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 [Formula: see text], denoted by [Formula: see text], among all partitions into k batches. CONCLUSIONS: When [Formula: see text] is the set of all balanced binary sequences of length 2n, we use combinatorial methods to obtain [Formula: see text] for any positive n, and [Formula: see text] for [Formula: see text] and large n with C a constant depending on k. Similarly, we get [Formula: see text] for [Formula: see text] and large n when [Formula: see text] 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.