DNA plays tic-tac-toe

By Kimberly Patch, Technology Research News

During the time they knew each other as kids in Belgrade, Serbia, Milan Stojanovic and Darko Stefanovic didn't play tic-tac-toe, according to Stojanovic. Things are different now that they are scientists at Columbia University and the University of New Mexico.

The researchers have fashioned a device that uses pieces of artificial DNA to automatically play tic-tac-toe. And as long as it makes the first move, the device cannot be beat.

The device is made of nine wells containing solutions where DNA can react. DNA in the wells acts like logic gates. "The distribution of logic gates in wells is such that it implements a perfect [tic-tac-toe] strategy," said Stojanovic. "Tic-tac-toe is a game of perfect information and guarantees a victory or draw for the first player," he said.

This makes it a good test for an automaton -- a machine that operates on its own, without human control. The device, dubbed Molecular Array of YES and ANDANDNOT gates (MAYA), is simpler than a computer, which is generally capable of storing, organizing and processing data, or controling other machines, said Stojanovic.

The researchers' method could eventually be used to control nano devices and in automata that educate people about science, said Stojanovic.

MAYA contains 24 logic gates distributed in the nine wells of solution. Some of the logic gates in each well perform Boolean calculations when short single-stranded DNA sequences, or oligonucleotides, are added. The addition triggers an enzyme to react with DNA. Depending on the result, the reaction may expose a fluorescent molecule.

DNA is formed from four types of bases - adenine, cytosine, guanine and thymine -- connected to a sugar-phosphate backbone. Strands of DNA can combine to form double-stranded DNA when their base sequences match up: adenine across from thymine, and cytosine across from guanine.

The researchers' device contains two types of gates that perform two types of Boolean calculations. The DNA molecule that makes up a YES logic gate has two states, one of which is fluorescent, or active. The more complicated DNA molecule that makes up a combination ANDANDNOT gate contains eight physical states, one of which is active.

YES gates change from nonactive to active when a complementary DNA sequence combines with the DNA in the well to release a loop in the DNA, which triggers a second reaction that exposes a fluorescent molecule. The ANDANDNOT gate contains three groups and is activated only if two of three possible inputs are provided.

MAYA always goes first and always starts in the center. Then the human challenger adds a DNA sequence to all the wells to represent the second move. The DNA sequence triggers a positive reaction with the DNA contained in only one of the wells -- the reaction exposes a fluorescent molecule, which makes the well glow to indicate the move.

"The game is played like this," said Stojanovic. "[The] human moves by adding oligonucleotide, takes a fluorescence reading, and adds [the] next oligonucleotide," he said. The game continues until the automaton wins, or there are no more spaces on the board, resulting in a draw.

The researchers' method differs from standard DNA computing, which is aimed at tapping DNA's massively parallel nature. In theory DNA could be used to test all possible answers to a problem at once in order to identify those that fit certain criteria. The goal of this type of DNA computing is to compete with silicon in certain applications that have large numbers of possibilities, like code-cracking.

In contrast, the researchers' method is aimed at adding relatively simple logic to nano devices. "We're not taking advantage of massively parallel processing capabilities," said Stojanovic. "Our approach is silicomimetic," he said. The researchers use molecules that behave as logic gates, and arrange these logic gates into more complicated circuits by mixing them in solution.

The researchers are aiming to eventually use the method to control nano devices in the human body, said Stojanovic. "We hope... in some distant... future, to use similar [devices] to make decisions in vivo [about] whether to release a toxic compound or not, [or] to kill a cell not," he said. Such devices could also be used to monitor in vivo disease signatures of astronauts on long space flights, he said.

Such uses are probably several decades away, Stojanovic added.

The research is also aimed at constructing automata that could help popularize science and familiarize young people with advanced concepts in nanotechnology, said Stojanovic.

The researchers are currently working on improving the tic-tac-toe device and on connecting DNA networks to sensors, said Stojanovic.

The work appeared in the August 17, 2003 issue of Nature Biotechnology. The research was funded by the National Aeronautics and Space Administration (NASA), and the National Science Foundation (NSF).

Timeline:   Several decades
Funding:   Government
TRN Categories:  Biological, Chemical, DNA and Molecular Computing
Story Type:   News
Related Elements:  Technical paper, "A deoxyribosome-Based Molecular Automation," August 17, 2003.


August 27/September 3, 2003

Page One

Software speeds modeling

DNA plays tic-tac-toe

Email updates six degrees theory

Cellophane turns LCDs 3D

News briefs:
Detector senses single DNA
Crystal shortens infrared waves
Tool sketches quantum circuits
Nanotubes spark gas detector
Metal process makes heat chips
Light makes molecule shine


Research News Roundup
Research Watch blog

View from the High Ground Q&A
How It Works

RSS Feeds:
News  | Blog  | Books 

Ad links:
Buy an ad link


Ad links: Clear History

Buy an ad link

Home     Archive     Resources    Feeds     Offline Publications     Glossary
TRN Finder     Research Dir.    Events Dir.      Researchers     Bookshelf
   Contribute      Under Development     T-shirts etc.     Classifieds
Forum    Comments    Feedback     About TRN

© Copyright Technology Research News, LLC 2000-2006. All rights reserved.