MAYA II, a second-generation tic-tac-toe playing automaton
Publication: Joanne Macdonald
, Yang Li, Marko Sutovic, Harvey Lederman, Kiran Pendri, Wanhong Lu, Benjamin L. Andrews, Darko Stefanovic, and Milan N. Stojanovic (2006) Medium Scale Integration of Molecular Logic Gates in an Automaton Nano Letters
ASAP Web Release Date: 07-Oct-2006.
MAYA-II is a second-generation molecular automaton
that plays a complete (i.e. non-symmetry pruned game) of tic-tac-toe. MAYA-II is more user-friendly than its predecessor MAYA-I
as it signals both players move in a two-color output system and imposes no constraints on the position of the human player’s first move.
- The automaton always goes first in the middle well.
- The human player is unrestricted in their first move - they may choose to play in any of the 8 remaining wells.
- There are 76 permissible game plays using this arrangement.
- MAYA-II signals both players' moves in a two-color output system. Human moves are displayed in a "green" channel (fluorescein fluorescence) and Automaton moves are displayed in a "red" channel (TAMRA) fluorescence.
- The human player makes a move by adding one of 32 input DNA sequences to all of the wells.
- The 32 input DNA sequences are coded, and tell the automaton which well the human has chosen and which move the human is playing (their first, second, third, or fourth move).
- The inputs are labelled I[NM] where N is the board position and M is the order of the humans move. For instance, to play into well 9 for their first move, the human would add input I91, but to play into well 9 on a second move the human would add input I92. Similarly, to play into well 9 in their second move the human would add input I82.
- MAYA-II uses a network of 128 logic gates distributed in the remaining 8 wells. These gates react to the human players input DNA causing a single well to fluoresce in the green channel - indicating the human's chosen well, and a different single well to fluoresce in the red channel - indicating the automaton's chosen well.
- The automaton remains undefeated as it plays according to a perfect strategy.
MAYA-II gate distribution and example game
Below is the gate distribution of MAYA-II, and an example game.
Medium scale integration
MAYA-II integrates 128 molecular logic gates
, 32 input DNA sequences, and eight two-channel fluorescent outputs in solution, which more than quadruples the number of gates by any previous system. By integrating more than 100 logic gates, MAYA-II represents the first medium scale integration of molecular logic gates in solution. The significance of this is similar to the significance of early silicon chips and semi-conductors. 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.
Deoxyribozyme logic gates and nucleotide inputs as computing tools
The success of MAYA-II indicates the maturity of our deoxyribozyme-based logic gates
as a plug and play integrated system. The increased complexity of MAYA-II has enabled refinement of our deoxyribozyme logic gate model, allowing the development of design principles for optimizing digital gate behavior and the generation of a library of known input sequences.
Practical applications for MAYA-II
We 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, our 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, 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 detection and viral lineage attribution.
Finally, 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. 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.
Molecular automaton as educational tools
MAYA-II was constructed with significant contributions from our NSF-funded high school internship participants, Yang Li, Marko Sutovic, Kiran Pendri, Harvey Lederman and Wanhong Lu, and full credit goes to them for their remarkable efforts!
Over the course of 3 summers, and Saturdays throughout two years, these extremely talented students designed and tested logic gates by modelling DNA sequences, computer-analyzing their folding structures, ordering custom-synthesized DNA, diluting the DNA to appropriate concentrations, testing gate acitivity, analyzing data, and remodelling the DNA based on the results. Once the logic gates were designed, they mixed the gates according to the predetermined MAYA-II strategy, tested all possible games multiple times, and re-designed gates where alterations were required. By doing so, they enabled us to learn much more about our logic gate structures and input sequences (i.e. what works and doesn't work).
The significance of both their contributions and achievements show that the construction of molecular automaton not only contributes to leading-edge scientific development, but is also an excellent educational tool to get students excited about science, and learn fundamental scientific knowledge in an interesting and challenging environment.
Congratulations to Yang, Marko, Kiran, Harvey and Wanhong for your outstanding contribution to scientific research!!
Larger versions of these pictures are supplied as an attachment on this page.
The future of MAYA
With the help of our next NSF-funded high school participants, we envisage several more versions of MAYA. We 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. We 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.