Toehold DNA Languages are Regular (Extended Abstract)

Biological organisms perform complex information processing and control tasks using sophisticated biochemical circuits, yet the engineering of such circuits remains ineffective compared with that of electronic circuits. To systematically create complex yet reliable circuits, electrical engineers use digital logic, wherein gates and subcircuits are composed modularly and signal restoration prevents signal degradation. We report the design and experimental implementation of DNA-based digital logic circuits. We demonstrate AND, OR, and NOT gates, signal restoration, amplification, feedback, and cascading. Gate design and circuit construction is modular. The gates use single-stranded nucleic acids as inputs and outputs, and the mechanism relies exclusively on sequence recognition and strand displacement. Biological nucleic acids such as microRNAs can serve as inputs, suggesting applications in biotechnology and bioengineering.

Artificial biochemical circuits are likely to play as large a role in biological engineering as electrical circuits have played in the engineering of electromechanical devices. Toward that end, nucleic acids provide a designable substrate for the regulation of biochemical reactions. However, it has been difficult to incorporate signal amplification components. We introduce a design strategy that allows a specified input oligonucleotide to catalyze the release of a specified output oligonucleotide, which in turn can serve as a catalyst for other reactions. This reaction, which is driven forward by the configurational entropy of the released molecule, provides an amplifying circuit element that is simple, fast, modular, composable, and robust. We have constructed and characterized several circuits that amplify nucleic acid signals, including a feedforward cascade with quadratic kinetics and a positive feedback circuit with exponential growth kinetics.

DNA experiments are proposed to solve the famous "SAT" problem of computer science. This is a special case of a more general method that can solve NP-complete problems. The advantage of these results is the huge parallelism inherent in DNA-based computing. It has the potential to yield vast speedups over conventional electronic-based computers for such search problems.