Team:UT-Tokyo/Sudoku abstract

From 2010.igem.org

(Difference between revisions)
(→What is Sudoku?)
 
(64 intermediate revisions not shown)
Line 1: Line 1:
-
{{UT-Tokyo_HEADER}}
+
__NOTOC__{{UT-Tokyo_CSS3}}{{UT-Tokyo_CSS_p}}{{UT-Tokyo_Head}}
-
<div id="main_all">
+
= '''Sudoku''' =
= '''Sudoku''' =
 +
<html>
 +
<div>
 +
        <ul id="inpagemenu">
 +
                <li><span>Introduction</span></li>
 +
                <li><a href="/Team:UT-Tokyo/Sudoku_construct" id="construct">System</a></li>
 +
                <li><a href="/Team:UT-Tokyo/Sudoku_modeling" id="modeling">Modeling</a></li>
 +
                <li><a href="/Team:UT-Tokyo/Sudoku_experiments" id="experiment">Experiments</a></li>
 +
                <li><a href="/Team:UT-Tokyo/Sudoku_perspective" id="perspective">Perspective</a></li>
 +
            <li><a href="/Team:UT-Tokyo/Sudoku_reference" id="reference">Reference</a></li>
 +
            </ul>
 +
</div>
 +
<div id="clear"></div>
 +
</html>
-
Abstract   
+
== '''Introduction''' ==
-
[https://2010.igem.org/Team:UT-Tokyo/Sudoku_construct  Construct]   
+
-
[https://2010.igem.org/Team:UT-Tokyo/Sudoku_lab_note  Lab note]       
+
-
[https://2010.igem.org/Team:UT-Tokyo/Sudoku_result  Result]
+
-
== '''Abstract''' ==
+
==='''Background'''===
 +
The ability to integrate and process information is indispensable for biological devices that operate autonomously in intricate environments, such as in "smart drugs", which sense and respond to the patient's health state appropriately.
 +
Therefore, the design and construction of such genetic circuits has long been pursued in the field of synthetic biology since its inauguration. Accomplishments include the toggle switch, logic gate, counter, and flip-flop switch.
-
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!
+
However, the function of most of these circuits is either limited to relatively simple form, such as Boolean logic element, or not robust enough to work correctly. A universal means of communication between individual elements is also generally lacking. As part of the solution, here we propose a new information processing unit which receives multiple inputs, memorizes the inputs stably, and makes a decision based on the combination of the inputs. In addition, we have devised a means of communication between individual bacterial-based elements. Importantly, this system allows destination-specific delivery of information even when the number of possible destinations is immensely large. As proof-on-principle of the above systems, we have created bacteria that solve "Sudoku", a world famous puzzle game.
-
=== What is Sudoku? ===
+
==='''What is Sudoku?'''===
-
[[Image:What_Sudoku_99.png|200px|thumb|What's Sudoku?]]
+
[[Image:9x9.png|200px|thumb|The example of Sudoku (9x9)]]
-
Sudoku is a famous puzzle game. It is now widely known all over the world. There are a lot of version of Sudoku puzzle, but the 9×9 cells version is the most famous. 81 cells are divided into nine smaller squares containing nine cells each; we call them subgrids. The puzzle setter provides a partially completed grid, which typically has a unique solution. The player must fill in the empty cells with the numbers 1 to 9 in such a way that no digit appears twice in the same row, column or subgrid. It looks like a Latin square. Sudoku requires no math, but logic. Sudoku became an international hit in 2005.
+
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.
-
===''E.coli'' solves Sudoku?!===
+
==='''Solving Sudoku with our ''E. coli'''''===
-
[[Image:Parallel_computing.png|200px|thumb|What's Sudoku?]]
+
[[Image:E.coli corresponding.png|200px|thumb|16 kinds of ''E. coli'' corresponding to each cell]]
-
[[Image:E.coli_info.png|200px|thumb|What's Sudoku?]]
+
-
How does ''E.coli'' solve a Sudoku puzzle? Now we explain it with simple version puzzle, 2 blocks of contiguous 4×4 cells.
+
[[Image:Differentiation-model.png|200px|thumb|Every cells can "differentiate"]]
-
''E.colis'' are on each cells. Every ''E.coli'' has the number information and the locate information where it is on. When we solve 4×4 puzzle, we have to fill in the empty cells with the numbers 1 to 4, and use the same number only once in the same row, column or subgrid. So, when every ''E.colis'' can transmits information mutually, ''E.colis'' can solve puzzle in parallel. To realize this, we use "[https://2010.igem.org/Team:UT-Tokyo/Sudoku_construct  4C3 leak switch]" and "[https://2010.igem.org/Team:UT-Tokyo/Sudoku_construct  signal virus]."
+
Now, we explain how to make ''E. coli'' solve Sudoku. First, we make 16 kinds of ''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 from one to four.
-
==='''Solution unique to the microbe: parallel computing'''===
+
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.
-
To solve Sudoku by human or the computer, we have to check the candidate of numbers which matches the rules for each 9x9 boxes. On the other hand, E. coli can fill in all boxes at a time by the system below.<br>
+
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 which the 16 cells have differentiated into with the use of fluorescent proteins.
-
-Judging all boxes simultaneously.<br>
+
-
-Getting information about the location. (Which boxes they are in?)<br>
+
-
-Outputting the correct number.<br>
+
-
In other words, we propose the possibility of the new method of calculation, parallel computing, which has never been realized by traditional computers.
+
 +
If you'd like to know how our ''E.coli'' solves SUDOKU particularly, please see the [https://2010.igem.org/Team:UT-Tokyo/Sudoku_construct  System] page.
-
==='''Differentiation model in prokaryote'''===
 
-
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.” This process is similar to the process of multicellular organisms, which can differentiate depending on the situation around them. We consider that to build such differentiation model in prokaryote will lead to more profound understanding for life.
 
 +
<html>
 +
<object width="640" height="385"><param name="movie" value="http://www.youtube.com/v/wzcryKryME8?fs=1&amp;hl=ja_JP"></param><param name="allowFullScreen" value="true"></param><param name="allowscriptaccess" value="always"></param><embed src="http://www.youtube.com/v/wzcryKryME8?fs=1&amp;hl=ja_JP" type="application/x-shockwave-flash" allowscriptaccess="always" allowfullscreen="true" width="640" height="385"></embed></object>
 +
</html>
-
==='''Information transmission by virus'''===
 
-
E. coli in each box have to transmit their information of the number to the other appropriate  boxes (Boxes which are in the same raw, column, and 3x3 boxes). To realize this “destination-restricted information diffusion,” we propose new information transmission system using RNA phage. With embedding information of the number and location in RNA loaded into the phage, we realize information transmission to the particular E. coli. This “destination-restricted information diffusion” can be a powerful tool for building bio-computer, which uses the creature as the unit of calculation.
 
-
 
+
{{UT-Tokyo_Foot}}
-
==='''Possibility of application for Artificial Intelligence'''===
+
-
Originally, the process of solving Sudoku can be accomplished with high-level intelligence like human. Therefore, we suppose that implementation of this process in E. coli, or prokaryote, can play an important role in developing artificial intelligence.
+
-
 
+
-
 
+
-
== Appeal point ==
+
-
 
+
-
=== Parallel computing ===
+
-
 
+
-
Our E.coli is superior to PC.
+
-
 
+
-
=== Differentiation model ===
+
-
 
+
-
This is a model of Eukarya differentiation model created by prokaryote.
+
-
 
+
-
 
+
-
 
+
-
== Future vision ==
+
-
<!--<html><object width="640" height="385"><param name="movie" value="http://www.youtube.com/v/eyDq2ox7_PA?fs=1&amp;hl=ja_JP"></param><param name="allowFullScreen" value="true"></param><param name="allowscriptaccess" value="always"></param><embed src="http://www.youtube.com/v/eyDq2ox7_PA?fs=1&amp;hl=ja_JP" type="application/x-shockwave-flash" allowscriptaccess="always" allowfullscreen="true" width="640" height="385"></embed></object>
+
-
</html>-->
+
-
?????
+
-
 
+
-
</div>
+
-
{{UT-Tokyo_FOOTER}}
+

Latest revision as of 03:57, 28 October 2010

UT-Tokyo

Sudoku

Introduction

Background

The ability to integrate and process information is indispensable for biological devices that operate autonomously in intricate environments, such as in "smart drugs", which sense and respond to the patient's health state appropriately. Therefore, the design and construction of such genetic circuits has long been pursued in the field of synthetic biology since its inauguration. Accomplishments include the toggle switch, logic gate, counter, and flip-flop switch.

However, the function of most of these circuits is either limited to relatively simple form, such as Boolean logic element, or not robust enough to work correctly. A universal means of communication between individual elements is also generally lacking. As part of the solution, here we propose a new information processing unit which receives multiple inputs, memorizes the inputs stably, and makes a decision based on the combination of the inputs. In addition, we have devised a means of communication between individual bacterial-based elements. Importantly, this system allows destination-specific delivery of information even when the number of possible destinations is immensely large. As proof-on-principle of the above systems, we have created bacteria that solve "Sudoku", a world famous puzzle game.

What is Sudoku?

The example of Sudoku (9x9)

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

16 kinds of E. coli corresponding to each cell
Every cells can "differentiate"

Now, we explain how to make E. coli solve Sudoku. First, we make 16 kinds of 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 from 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 which the 16 cells have differentiated into with the use of fluorescent proteins.

If you'd like to know how our E.coli solves SUDOKU particularly, please see the System page.



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