Towards Optimal DNA-Templated Computing

Using DNA-templated synthesis, reactants are attached to DNA strands and complementary DNA strands are used to control the reaction towards a goal compound. This very general, simple, and still efficient approach has proven to be successful for the design of complex one-pot synthesis for a large variety of compounds. For a given goal compound many different synthesis plans may exist, and all of them can potentially be implemented with many different DNA-templated programs. This raises the issue of how to automatically infer optimal low-level programs based on a high-level synthesis plan or a goal compound only. In this paper we will introduce a computational approach for DNAtemplated synthesis based on graph rewriting approaches and the systematic exploration of chemical spaces. We will use them for verification of correctness of real-world synthesis plans as well as to illustrate the non-triviality of finding an optimal DNA assembler program.