title: Three dimensional DNA structures in computing.
abstract: 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.
authors.affiliation: Department of Mathematics, University of South Florida, Tampa 33620, USA. jonoska@math.usf.edu
authors.forename: N
authors.initials: N
authors.lastname: Jonoska
authors.forename: S A
authors.initials: SA
authors.lastname: Karl
authors.forename: M
authors.initials: M
authors.lastname: Saito
mesh_terms: D000818:Animals; D019295:Computational Biology; D003198:Computer Simulation; D004247:DNA / Q000032:analysis* / Q000737:chemistry*; D006801:Humans; D008958:Models, Molecular; D009690:Nucleic Acid Conformation
chemical_list: D004247:DNA