The bounded complexity of DNA computing.
This paper proposes a new approach to analyzing DNA-based algorithms in molecular computation. Such protocols are characterized abstractly by: encoding, tube operations and extraction. Implementation of these approaches involves encoding in a multiset of molecules that are assembled in a tube having a number of physical attributes. The physico-chemical state of a tube can be changed by a prescribed number of elementary operations. Based on realistic definitions of these elementary operations, we define complexity of a DNA-based algorithm using the physico-chemical property of each operation. We show that new algorithms for Hamiltonian path are about twice as efficient as Adleman's original one and that a recent algorithm for Max-Clique provides a similar increase in efficiency. Consequences of this approach to tube complexity and DNA computing are discussed.
Garzon
M H
MH
Department of Computer Science, University of Memphis, TN 38152, USA. garzonm@memphis.edu
Jonoska
N
N
Karl
S A
SA
D000465:Algorithms; D000818:Animals; D019295:Computational Biology / Q000379:methods*; D003198:Computer Simulation; D004247:DNA / Q000032:analysis* / Q000235:genetics; D006801:Humans; D008958:Models, Molecular; D008962:Models, Theoretical
D004247:DNA