In this paper a classical AI problem is proposed to be solved by DNA computing: theorem proving. Since the complexity grows exponentially with the size of the problem, the solving process should be done in parallel. Massive parallelism is one of the advantages of DNA computers. It will be shown that the resolution refutation proof can be readily implemented by DNA hybridisation and ligation. Microreactors lend themselves to a relatively simple implementation of DNA computing. Not only is the design of the DNA critical for the success of the system but also the architecture of the microfluidic structure. Here the DNA performs the computation, while the microfluidics aids the biochemical steps necessary to manipulate the DNA, i.e. hybridisation and ligation.
DNA computing is an interdisciplinary field accessing the possibility for the use of biomolecules, such as DNA, RNA and proteins, as a computational or control tool. Traditionally, DNA computers were thought to compete with electronic computers to solve, for example, NP-complete problems. However recently, there has been a focus shift to biomedical applications.
One form of DNA computing is performed in microfluidics. A network of microreactors decides the computational aspects and DNA is the tool for selection procedures. To control complex microflow systems like this, a series of pneumatic valves are used to control the flow direction, i.e. the information direction, and to contain DNA functionalised beads in the microreactors.
The goal of this research is to improve the modular stability and programmability of DNA-based computers and in a second step towards optical programmable DNA computing. The main focus here is on hydrodynamic stability. Clockable microreactors can be connected in various ways to solve combinatorial optimisation problems, such as Maximum Clique or 3-SAT. This work demonstrates by construction how one micro-reactor design can be programmed to solve any instance of Maximum Clique up to its given maximum size (N). It reports on an implementation of the architecture proposed previously. This contrasts with conventional DNA computing where the individual sequence of biochemical operations depends on the specific problem. In this pilot study we are tackling a graph for the Maximum Clique problem with N<EQ12, with a special emphasis for Nequals6. Furthermore, the design of the DNA solution space will be presented, which is symbolized by a set of bit-strings (words).
Access to the requested content is limited to institutions that have purchased or subscribe to SPIE eBooks.
You are receiving this notice because your organization may not have SPIE eBooks access.*
*Shibboleth/Open Athens users─please
sign in
to access your institution's subscriptions.
To obtain this item, you may purchase the complete book in print or electronic format on
SPIE.org.
INSTITUTIONAL Select your institution to access the SPIE Digital Library.
PERSONAL Sign in with your SPIE account to access your personal subscriptions or to use specific features such as save to my library, sign up for alerts, save searches, etc.