With this project we propose use of three dimensional structures for solving computational problems with DNA molecules. The formation of three dimensional structures and the preservation of information within three dimensional structures in space is a capability of DNA that has been exploited by nature (for example in gene activation). We believe that a better understanding of when, how and what three dimensional DNA structures can be formed and used would lead to a more profound understanding of natural processes in vivo and also to potentially developing a new concept of computation, computation with three dimensional structures (knots or graphs), unavailable to our electronic computers.
In many theories and experiments, the DNA computing has used linear segments of DNA molecules for the computational tools. This was also the beginning of our biomolecular computation efforts. However, DNA molecules form 3 dimensional (3D) structures and we are developing methods for using such structures in DNA based computations. For example, building blocks of k-armed branched junction molecules can be used to form graphs to solve the Hamiltonian Cycle problem, the 3-vertex colorability problem, and the satisfiability problem, potentially reducing the number of laboratory (computational) steps.
Based on the knowledge of in vitro and in vivo DNA topology, our long term goal is to systematically develop theories of DNA computing that use 3D structures. For this goal, several specific short term goals for the next few years are formulated. In particular, realization problem of single stranded DNA inside graphs, and the graph theoretic complexities for DNA computing are discussed here.