title: The bounded complexity of DNA computing.
abstract: 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.
authors.affiliation: Department of Computer Science, University of Memphis, TN 38152, USA. garzonm@memphis.edu
authors.forename: M H
authors.initials: MH
authors.lastname: Garzon
authors.forename: N
authors.initials: N
authors.lastname: Jonoska
authors.forename: S A
authors.initials: SA
authors.lastname: Karl
mesh_terms: 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
chemical_list: D004247:DNA