Team:UT-Tokyo/Sudoku abstract

From 2010.igem.org

(Difference between revisions)
m (→How to solve Sudoku?)
(→Abstract)
Line 15: Line 15:
[[Image:What_Sudoku_99.png|200px|thumb|What's Sudoku?]]
[[Image:What_Sudoku_99.png|200px|thumb|What's Sudoku?]]
-
Sudoku is a puzzle game with the objective of filling a 9x9 grid of cells with the numbers 1~9 without entering the same number in a column, row or “block (see figure).”
+
Sudoku is a puzzle game with the objective of filling a 9x9 grid of cells with the numbers 1~9 without entering the same number in a column, row or “block (see figure).” A player is given a grid in which some of the cells are filled in from the beginning and must complete filling in the grid by entering the remaining numbers. The rules are simple, but some puzzles can get very difficult, and it attracts fans from all over the world. For simplicity, here we solve a 4x4 grid version. However, expanding on the same principles, our E. coli can theoretically solve larger grids, for example 9x9 grids.
-
A player is given a grid in which some of the cells are filled in from the beginning and must complete filling in the grid by entering the remaining numbers.
+
-
==='''Solution unique to the microbe: parallel computing'''===
+
 
 +
==='''Solving Sudoku with our E. coli'''===
[[Image:Parallel_computing.png|200px|thumb|Every cells "consider" independently]]
[[Image:Parallel_computing.png|200px|thumb|Every cells "consider" independently]]
-
When we solve Sudoku, either manually or by using a calculator, we usually enter random numbers in the grid one by one and look for the correct combination by trial-and-error. On the other hand, our E. coli are each capable of independently filling in the boxes simultaneously. In other words, our E. coli perform parallel computing.
+
Now, we explain how to make E. coli solve Sudoku. First, we make 16 kinds E. coli corresponding to each cell.
-
 
+
(図！)
-
 
+
Our E. coli are in one of two states, which we designate “differentiated” or “undifferentiated.” There are four differentiated states corresponding to the numbers one to four.
-
==='''How to solve Sudoku?'''===
+
(図！)
-
[[Image:E.coli_info.png|200px|thumb|Each E.coli possesses two information]]
+
Differentiated E. coli have the ability to inform other bacteria what number they are, so that relevant bacteria do not differentiate into that number. Some E. coli are differentiated from the beginning. These bacteria set in action a chain of transmission events that result in the differentiation of bacteria corresponding to all 16 cells.
-
[[Media:Sudoku_presentation_Overall_flow.swf]]
+
These events take place in a flask which contains a co-culture of the 16 types of bacteria. Each of these 16 types interacts with detection bacteria on a plate which in turn inform the viewer the number the 16 cells have differentiated into with the use of fluorescent proteins.
-
 
+
-
Instead of the traditional 9x9 grid of cells, we use E. coli possessing information of its location within the grid, in a liquid mixture.
+
-
 
+
-
At the beginning, most of the bacteria are not designated a number while some of them are designated as an initial condition. Through undesignated bacteria receive information from their environment, they are designated a number, causing them to “differentiate” into a state in which they emit viruses possessing information of the bacterium’s location and number. These viruses in turn collectively compel other bacteria to be designated a particular number.
+
-
 
+
-
In such a system, each bacterium must be able to identify relevant information, retain this information, and finally amass this information to “differentiate” into a particular number.
+
-
To realize this, we use DNA recombination caused by proper virus.
+
-
 
+
-
==='''Differentiation model in prokaryote'''===
+
-
[[Image:Differenciation.png|200px|thumb|Each grid of cells “differentiate” into a particular number]]
+
-
 
+
-
E. coli in each box rearrange DNA and determine their numbers by receiving information about the number from other E. coli in the same row, column, and block. In other words, they change their states irreversibly from “the multi-output state” to “the uni-output state.”
+
-
 
+
-
We realize this by making a switch we named “4C3 leak switch,” using the leak of terminators. This switch turns on when three of four choices are transmitted, regardless of the order of transmission.
+
-
 
+
-
 
+
-
 
+
-
==='''Information transmission by virus'''===
+
-
[[Image:Destination-restricted.png|200px|thumb|Destination-restricted information diffusion]]
+
-
 
+
-
To transmit information for proper E. coli, we use RNA phage named “signal virus.” Translation of the RNA transmitted from signal virus is controlled by antisense RNA characteristic to their location information.
+
-
 
+
-
This destination-restricted information diffusion can be a powerful tool for building bio-computer, which use the creature as the unit of calculation.
+
=='''Reference'''==
=='''Reference'''==

Revision as of 10:13, 26 October 2010

UT-Tokyo

Sudoku

Abstract Construct Lab note Result

Abstract

We're trying to make E.coli solve Sudoku puzzle. Human and Computers can solve Sudoku, of course. But E.coli, which is lower animal, solves sudoku in our project. It is very very interesting!

What is Sudoku?

What's Sudoku?

Sudoku is a puzzle game with the objective of filling a 9x9 grid of cells with the numbers 1~9 without entering the same number in a column, row or “block (see figure).” A player is given a grid in which some of the cells are filled in from the beginning and must complete filling in the grid by entering the remaining numbers. The rules are simple, but some puzzles can get very difficult, and it attracts fans from all over the world. For simplicity, here we solve a 4x4 grid version. However, expanding on the same principles, our E. coli can theoretically solve larger grids, for example 9x9 grids.


Solving Sudoku with our E. coli

Every cells "consider" independently

Now, we explain how to make E. coli solve Sudoku. First, we make 16 kinds E. coli corresponding to each cell. (図！) Our E. coli are in one of two states, which we designate “differentiated” or “undifferentiated.” There are four differentiated states corresponding to the numbers one to four. (図！) Differentiated E. coli have the ability to inform other bacteria what number they are, so that relevant bacteria do not differentiate into that number. Some E. coli are differentiated from the beginning. These bacteria set in action a chain of transmission events that result in the differentiation of bacteria corresponding to all 16 cells. These events take place in a flask which contains a co-culture of the 16 types of bacteria. Each of these 16 types interacts with detection bacteria on a plate which in turn inform the viewer the number the 16 cells have differentiated into with the use of fluorescent proteins.

Reference

MS2 1. 2.

Safety issue

We use new parts which are not registered as BioBrick parts. We don't intend to execute experiment which affect the environment or human body. We do experiment in the laboratory which safety is maintained and recombinant E.coli and virus which include new parts are not taken out of the laboratory.

Retrieved from "http://2010.igem.org/Team:UT-Tokyo/Sudoku_abstract"