Related Experiment Video
Updated: Oct 18, 2026

DNA-Tethered RNA Polymerase for Programmable In vitro Transcription and Molecular Computation
Published on: December 29, 2021
The bounded complexity of DNA computing
M H Garzon1, N Jonoska, S A Karl
1Department of Computer Science, University of Memphis, TN 38152, USA. garzonm@memphis.edu
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.
Related Concept Videos
The Nucleosome
In a chromosome, DNA is wound twice around a protein complex called a histone octamer core, which consists of 8 histone proteins. This...
The Nucleosome
DNA is wound twice around a protein complex called histone core, that consist of 8 histone proteins. This complex...
DNA Packaging
Chromatin Packaging
Chromatin Packaging
The chromatin
In combination with specialized DNA binding protein called Histones, the DNA double helix forms a compact DNA: protein complex called chromatin. The chromatin itself is further compacted into higher-order structures.
Genomic DNA in Eukaryotes
