The bounded complexity of DNA computing

This paper proposes a new approach to analyzing DNA-based algorithms in mol ecular computation. Such protocols are characterized abstractly by: encodin g, tube operations and extraction. Implementation of these approaches invol ves 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 realis tic definitions of these elementary operations, we define complexity of a D NA-based algorithm using the physico-chemical property of each operation. W e show that new algorithms for Hamiltonian path are about twice as efficien t as Adleman's original one and that a recent algorithm for Max-Clique prov ides a similar increase in efficiency. Consequences of this approach to tub e complexity and DNA computing are discussed. (C) 1999 Elsevier Science Ire land Ltd. AU rights reserved.