Shin MPP 2011
Logical Verification of DNA-Based Chemical Reaction Network Implementations
- Seung Woo Shin
- California Institute of Technology
A goal of molecular programming and synthetic biology is to build chemical circuits to control chemical processes at the molecular level. Remarkably, carefully designed DNA molecules can be used to construct complex chemical circuits that operate without any enzymes or cellular components. However, designing DNA molecules at the sequence level can be difficult and laborious. To reduce the difficulties, chemical reaction networks (CRNs) have recently been studied as a promising candidate for a higher-level programming language for DNA computing. Several general-purpose schemes for implementing CRNs with DNA molecules have already been proposed, and many more are being actively investigated. In the course, however, it has also been discovered that such schemes can harbor errors that may not be so conspicuous. To facilitate research in this domain, here we propose a method of algorithmically verifying such DNA-based CRN implementations. Although it was originally motivated by the DNA-based implementations, it is also applicable to any CRN implementation provided the reaction network of the implementation can be generated in some way. We hope this result will provide researchers with more confidence in the logical correctness of their implementations so that they can concentrate more on the experimental issues."