Team:TokyoTech/Model
Modelling
0. Abstract
In order to tie the reproduction of artificial Turing patterns using bacterial communities at Wet Lab to the application and practical application, we considered various aspects this time. Based on interviews with Prof. Kondo (Osaka University) in Human Practice, the âfingerprintâ pattern that anyone has and can be said to be an individual identity is based on the Turing pattern theory. This time, a simulation was performed to restore a fingerprint from a rough fingerprint image using a Turing pattern, inspired by the experimental results at Wet Lab. First, by referring to the model proposed by Young (1983), we succeeded in calculating and visualizing Turing patterns using cellular automata without solving linear differential equations. After that, we established a method for pre-processing and correcting fingerprint data, and then performed a parameter search that can repair missing fingerprint data. For the cellular automaton equation described above, the phase value and randomization coefficient were set in a form suitable for the restoration of fingerprint data, and a restoration mechanism was finally constructed.
1. Introduction
Although We designed E. coli that can reproduce the Turing pattern in wet experiments, it is difficult to know what pattern will be shown from culture medium in advance. In this modelling page, We will show that we can create complicated pattern of nature to imagine the usefulness and applicability of this project. Therefore, We decided to make a program to repair fingerprints, a familiar Turing pattern.
Here is a link to the code used in our modeling (please visit our GitHub page). This page gives you further opportunity to understand the mechanism and potential that our strategy of modeling has.
2. Basic Features of Fingerprint Repair Model
2.1 Background - A Local Activator-Inhibitor Model of Skin Patterns
The Turing pattern model can be generated by calculation from these two linear differential equations, but it is necessary to apply the linear differential equation to each plot, resulting in a huge amount of computation. There was a problem. Therefore, Young (1983) proved that the Turing pattern can be calculated using a cellular automaton without solving this linear differential equation, and this time, we constructed a new model suitable for fingerprint restoration. Young (1983) hypothesized that each of the suppressor and diffusion factors diffuses from one cell to the surrounding cells as shown in the following figure of right. (see fig2)
The calculation in the cellular automaton follows the following procedure.
- Prepare a two-dimensional grid and distribute DC (Differentiated Cells) randomly.
- For each grid point, sum the feed values by DC of the grid points up to positions R1 and R2. It is assumed that the feed value of w2 acts on the grid point from the DC included up to w1 and R2 from the DC included up to the distance R1.
- If the total value of the feed values at each grid point is positive, the grid point in the next state is DC, and if it is negative, the grid point is UC (Undifferenciated Cells).
- Repeat STEP2 and STEP3 until convergence.
This figure is a GIF image showing a series of changes in which a Turing pattern is generated from random initial values. As pointed out by Young (1983), it takes about 5 iterations of STEP2 and 3 for the pattern change to converge.
3. Fingerprint Repair Model by iGEM TokyoTech
3.1 New Formulation for Fingerprint Repair
The following processing was applied to the feed values at each grid point.
\[ S= \sum_{i} W|\boldsymbol{ R }-\boldsymbol{ R_{i} }| \times (1-fn) + \boldsymbol{ N_{init} } \times fn + \boldsymbol{ N_{noise} } \times rd \]
| paramater | description |
|---|---|
| \( w \) | width of the grid. |
| \( h \) | height of the grid. |
| \( \boldsymbol{N_{init}} \) | \(\boldsymbol{N_{init}} \in \boldsymbol{R^{w \times h}} \) initial grid data. Each matlix element has 0 or 1. |
| \( \boldsymbol{N_{noise}} \) | \( \boldsymbol{N_{noise}} \in \boldsymbol{R^{w \times h}} \) random noise data. -1< Each matlix element < 1 |
| \( \boldsymbol{S }\) | \( \boldsymbol{S} \in \boldsymbol{R^{w \times h}} \) field score matrix. Next state matlix \(\boldsymbol{N}\) is calclated based on this score. |
| \( \boldsymbol{R} \) | grid point. |
| \( \boldsymbol{R_{i}} \) | DCs position near grid point at position \(\boldsymbol{R}\). |
| \( fn \) | weighting factor of initial state. |
| \( rd \) | weighting factor of random noise. |
The sign of the value of S calculated by this function is set to be reflected in the next state (the next calculation processing cycle). Here, the following processing is performed: 1) By adding random elements, it is possible to connect lines that are relatively close to each other, which has been divided in the past, so that convergence is accelerated. It was. 2) By pulling on the previous image, it is possible to prevent the pattern from being too far away from the previous image. In the subsequent Turing pattern, the pattern is generated with \(fn=0.01\) and \(rd=0.5\).
3.2 Parameter Search
We searched for combinations of cell-to-cell distance and reaction-diffusion factor concentrations that allow Turing pattern formation. At each grid point of a grid-like two-dimensional matrix, 1 is applied to DC (Differenciated Cells) cells and 0 is applied to UC (Undifferenciated Cells) cells. Based on Young (1983), it is known that if each reaction diffusion factor R1, R2, w1, and w2 is set appropriately, the pattern generated by this two-dimensional array converges to a Turing pattern. In this case, the ratio of DC cells in the two-dimensional array is calculated in each trial, and it is determined whether or not it converges to the Turing pattern. If it does not converge to the Turing pattern, either DC or UC will dominate, so the percentage of DC cells in the grid matrix will be 0 or 1.
In order to know the parameters that converge to the Turing pattern, the ratio of DC cells in the grid matrix after 10 state changes was displayed as a heat map as shown in the figure. (see fig4) For example, the pattern of convergence differs depending on the difference in w2. (see fig4) After many trials, we decided to experiment with \(r1 = 3, r2 = 6, w1 = 16,\) and \(w2 = -5\) in the subsequent fingerprint restoration section. (see fig5)
4. Improvement of Model
Aiming at further model improvement and practical application, first of all, a fingerprint image was converted into a grid matrix represented by 0 and 1, and a program that could create a Turing pattern using it as an initial value was created. However, we had to overcome the problem that fingerprints are not always restored even if appropriate parameters are set to generate Turing patterns.(see fig5)
As the program continues to run, the factors that determine whether the converged pattern repairs the fingerprint are: a) the line width of the generated Turing pattern and b) the actual width of the fingerprint image It turned out to be. Therefore, the width of the Turing pattern generated by the fixed parameters is examined, and at the same time, the scale of the two-dimensional fingerprint matrix given as the initial value is changed, and a new program is created to find the best match between the width of the fingerprint and the width of the Turing pattern. In this width search program, the pattern is thinned so that the width of the white side is 1 pixel. The concrete steps executed are as follows.
- First, find the line width of the Turing pattern generated when each parameter is "\(r1 = 3, r2 = 6, w1 = 16, w2 = -5\)".The width at this time is as shown in FIG. 7, and the mode value is 10.
- Then, measure the width of the uneven part of the fingerprint image and scale it to the Turing pattern width obtained in 1).When the fingerprint image is read and converted to a \((200 \times 200)\) grid matrix, the width of the fingerprint is examined. When the width is examined as shown in the following graph, it is found that the mode of the width is 3. In this graph, the binarized fingerprint photo is morphologically converted and then thinned to make the white width 1 pixel.(see fig8)
- By changing the scale of the fingerprint image to match the width of the Turing pattern obtained in (1), 10 pixels,(doubled to match 10, \((400 \times 400)\) the fingerprint can be restored as follows.(see fig9)
This program makes it possible to repair fingerprints for various fingerprint images. (as you can see in fig9 and fig10)
5. Discussion
The Turing pattern is thought to affect the pattern formation of various animals including zebras, and can generate various patterns. This model based on cellular automata which enable more efficient calculation, can import the temperature and light from wet lab as parameters. When you use this model, you should note that the fingerprint can be reproduced by the Turing pattern, but 62.5% of the noise is difficult to repair, and 87.5% noise is hardly repaired (see fig12).
To sum up, this simulation will help converge E. coli to the expected pattern and the conditions can be modified based on actual environmental factors.
Reason of Qualification for Gold Medal Criterion #3
The new model of Turing pattern in our project can be applied for modeling co-culture systems that have been worked on by many team projects. In general, this model can be generated from two linear differential equations by calculation,but there is a problem that the calculation amount is enormous. A program that can calculate Turing patterns using cellular automata without solving linear differential equations is open sourced so that the iGEM team can take advantage of the futureThis platform helps to show the usefulness and applicability of regenerating patterns in wet lab.
Reference
- D. A. Young, Mathematical Biosciences, 72, 1, 51-58 (1984)
- Graduation thesis of Mr. Fujii from Yamamura Group, School of Computing, Tokyo Institute of Technology
