Three dimensional DNA structures in computing.
We show that 3-dimensional graph structures can be used for solving computational problems with DNA molecules. Vertex building blocks consisting of k-armed (k = 3 or 4) branched junction molecules are used to form graphs. We present procedures for the 3-SAT and 3-vertex-colorability problems. Construction of one graph structure (in many copies) is sufficient to determine the solution to the problem. In our proposed procedure for 3-SAT, the number of steps required is equal to the number of variables in the formula. For the 3-vertex-colorability problem, the procedure requires a constant number of steps regardless of the size of the graph.
Jonoska
N
N
Department of Mathematics, University of South Florida, Tampa 33620, USA. jonoska@math.usf.edu
Karl
S A
SA
Saito
M
M
D000818:Animals; D019295:Computational Biology; D003198:Computer Simulation; D004247:DNA / Q000032:analysis* / Q000737:chemistry*; D006801:Humans; D008958:Models, Molecular; D009690:Nucleic Acid Conformation
D004247:DNA