PubMed · 10636031
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.
Explore related subjects
Keep this discovery
Explore connections, maps & timelines
M H Garzon, N Jonoska, S A Karl. 1999. The bounded complexity of DNA computing.. https://doi.org/10.1016/s0303-2647(99)00033-7. https://pubmed.health/record/pubmed%3A10636031/the-bounded-complexity-of-dna-computing
Citations retain the original authors and DOI and include this site’s record URL. If this discovery service contributed to your research, you can also cite PubMed Health by Indiciae: BibTeX · RIS.