Paper detail

Efficient Synthesis for Two-Dimensional Strand Arrays with Row Constraints

We study the theoretical problem of synthesizing multiple DNA strands under spatial constraints, motivated by large-scale DNA synthesis technologies. In this setting, strands are arranged in an array and synthesized according to a fixed global synthesis sequence, with the restriction that at most one strand per row may be synthesized in any synthesis cycle. We focus on the basic case of two strands in a single row and analyze the expected completion time under this row-constrained model. By decomposing the process into a Markov chain, we derive analytical upper and lower bounds on the expected synthesis time. We show that a simple laggard-first policy achieves an asymptotic expected completion time of (q+3)L/2 for any alphabet of size q, and that no online policy without look-ahead can asymptotically outperform this bound. For the binary case, we show that allowing a single-symbol look-ahead strictly improves performance, yielding an asymptotic expected completion time of 7L/3. Finally, we present a dynamic programming algorithm that computes the optimal offline schedule for any fixed pair of sequences. Together, these results provide the first analytical bounds for synthesis under spatial constraints and lay the groundwork for future studies of optimal synthesis policies in such settings.