Molecular automaton plays tic-tac-toe

(Nanowerk Spotlight) DNA computing is a form of computing which uses DNA and molecular biology instead of the traditional silicon-based computer technologies. Molecular computation is currently focused on building molecular networks analogous to electrical engineering designs. These networks consist of logic gates, which perform Boolean logical operations such as AND, NOT, and OR on one or more inputs to produce an output. While individual molecular gates and small networks have previously been constructed, these gates are yet to be integrated at higher levels of complexity. Such integration in electrical engineering arises from massive parallelism and interconnections, rather than fundamental component complexity. The ability to truly integrate molecular components remains crucial for the construction of next-generation molecular devices. Researchers have now succeeded in building a medium- scale integrated molecular circuit, integrating 128 deoxyribozyme-based logic gates, 32 input DNA molecules, and 8 two-channel fluorescent outputs across 8 wells.
Automata are self-operating machines, or robots, that are able to analyze a series of "inputs" in a meaningful fashion. Researchers at Columbia University and the University of New Mexico are exploring DNA (deoxyribonucleic acid) as a medium for building automata on a molecular scale.
"The significance of this is similar to the significance of early silicon chips and semi-conductors" says Joanne Macdonald, a virologist and molecular biologist in the Division of Experimental Therapeutics and Clinical Pharmacology, Department of Medicine, Columbia University. "By using these integrated gates to play tic-tac-toe we show that large-scale, higher level, computing using molecular logic gates is now a reality, and that even larger molecular computers are feasible."
Game playing is often used as an unbiased test of new computation media. Macdonald and her colleagues have focused on tic-tac-toe: one of the simplest games of perfect information, and yet a surprisingly complex combinatorial problem, with 2.65 x 10103 non-losing strategies for a complete version of tic-tac-toe.
A representative game. Inputs were added in sequence into each well to signal the human players move. Results are expressed as the slope of signal increase over time (dF min-1). (Source: Joanne Macdonald)
Macdonald explained to Nanowerk that they previously constructed a deoxyribozyme-based molecular automaton (MAYA, a molecular array of YES and AND gates) that plays a simplified symmetry-pruned game of tic-tac-toe encompassing 19 permissible game plays, using an array of 23 logic gates distributed over 8 wells.
"We now report the development of the first solution-phase molecular assembly comprising over 100 molecular logic gates, which more than quadruples the complexity performed by any previous system" says Macdonald. "Expanding from our original automaton, MAYA-II is a second generation molecular automaton capable of playing a complete game of tic-tac-toe against a human opponent, and encompasses 76 permissible game plays."
A description of MAYA-II was recently published in a paper titled "Medium Scale Integration of Molecular Logic Gates in an Automaton".
Darko Stefanovic from the University of New Mexico first proposed building the larger automaton, which was implemented by Macdonald and Milan Stojanovic.
The success of MAYA-II indicates the maturity of deoxyribozyme-based logic gates as a plug and play integrated system. The increased complexity of MAYA-II has enabled refinement of this logic gate model, allowing the development of design principles for optimizing digital gate behavior and the generation of a library of known input sequences.
The researchers point out that they do not expect MAYA to compete with silicon computing. The speed of the reaction is comparatively slow - with MAYA-II taking 30 minutes between each move. However, MAYA-II has significant advantages over silicon computing in several applications where speed is not paramount. In particularly, the logic gates work in solution, and will be useful for any computing required to be performed in fluids – such as in a sample of blood or in the body, where decisions could be made at the level of a single cell.
"Moreover" Macdonald says, "since our gates are made of DNA, we expect them to be extremely useful in oligonucleotide analysis. The ability to detect and analyze combinations of multiple DNA sequences within minutes has direct applications in microarray style diagnostics. Based on MAYA-II, we are currently developing several systems for multiplex SNP (single nucleotide polymorphism) detection and viral lineage attribution."
The versatility of the input and output system allows coupling of logic gate processing to both upstream and downstream events, such as the detection and release of small molecules and the inhibition of enzymatic activity.
"We are investigating the depth to which serial connectivity can be achieved and are considering a reset function to allow gates to perform multiple tasks" says Macdonald. "These developments should allow for the application of deoxyribozyme logic gate technology in bidirectional signaling events and pave the way for the next generation of fully autonomous molecular devices."
The researchers envisage several more versions of MAYA. They are planning to develop "trainable" automata that can play any tic-tac-toe strategy, and MAYA versions that only require input to be added into the well the human player chooses, with a series of cascades sending the signal for responses in other wells. They would also like to develop a colorimetric output system where moves are displayed in a more visually appealing manner that is visible to the naked eye.
Michael Berger By – Michael is author of three books by the Royal Society of Chemistry:
Nano-Society: Pushing the Boundaries of Technology,
Nanotechnology: The Future is Tiny, and
Nanoengineering: The Skills and Tools Making Technology Invisible
Copyright © Nanowerk LLC

Become a Spotlight guest author! Join our large and growing group of guest contributors. Have you just published a scientific paper or have other exciting developments to share with the nanotechnology community? Here is how to publish on