Error-Resilient Tile Sets for DNA Self-Assembly

Experiments have demonstrated that DNA molecules can compute like a machine to solve mathematical problems, which is significant because of their parallel computa-tion ability. However, due to the nature of biochemical reactions, DNA computation suffers from errors, which are its main limitation. The abstract and kinetic Tile As-sembly Models are now commonly used to simulate real DNA computing experiments, and to look for new methods to advance the accuracy of DNA-based computation. One means of controlling errors is through proofreading tile sets. Several such tile sets have been proposed in the literature, such as Chen and Goel’s snaked proofreading tile sets, the 2-way and 3-way overlay tile sets of Reif et al., and Rothemund and Cook’s n-way overlay tile sets. In the first part of this thesis, we analyze the performance of the Rothemund-Cook n-way overlay tile sets. We prove that the n-way overlay tile set contains n2 +3n+4 rule tiles. Simulation results show that these tile sets clearly perform better than tile sets without any error-control mechanism, and the performance improves as