On DNA Synthesis Using Shortmers and the Capacity of Non-Deterministic Costly Constrained Graphs

In conventional DNA synthesis machines, usually many strands are synthesized in parallel by iterating through a supersequence <inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"> <tex-math notation="LaTeX">$\boldsymbol {s}$ </tex-math></inline-formula> and adding in each cycle the next nucleotide to a programmable subset of the strands. The length of <inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"> <tex-math notation="LaTeX">$\boldsymbol {s}$ </tex-math></inline-formula> determines the number of the cycles, hence the time and the cost of the synthesis process. Recently, in order to reduce the number of synthesis cycles, researchers have suggested to append in each cycle a shortmer, i.e., a sequence of nucleotides, instead of a single one. The present work studies this synthesis technique from a theoretical point of view. In particular, it discusses which shortmers are the best to use (in order to reduce the number of cycles), and how to calculate the number of cycles required to synthesize in parallel a set of strands using a given set of shormers. Lastly, and following a previously described connection between the DNA synthesis problem and costly constrained graphs, this paper investigates calculating the capacity of non-deterministic costly constrained graphs.