Team:USTC-Software/Project/Method
From 2013.igem.org
Line 135: | Line 135: | ||
- | <div id=" "> | + | <div id="Alignment_Analyze"> |
<h2>Operon Theory and Regulatory Model</h2> | <h2>Operon Theory and Regulatory Model</h2> | ||
<div id="jobs_container"> | <div id="jobs_container"> | ||
<div class="jobs_trigger"><strong>Operon Theory</strong></div> | <div class="jobs_trigger"><strong>Operon Theory</strong></div> | ||
- | <div class="jobs_item" style="display: none;"><p class="bodytext"></p><p align="justify">In genetics, an operon is a functioning unit of genomic DNA containing a cluster of genes | + | <div class="jobs_item" style="display: none;"><p class="bodytext"></p> |
- | under the control of a single regulatory signal or promoter. The genes contained in the | + | <p align="justify">In genetics, an operon is a functioning unit of genomic DNA containing a cluster of genes |
- | operon are either expressed together or not at all. Several genes must be both cotranscribed | + | under the control of a single regulatory signal or promoter.<br /> The genes contained in the |
- | and co-regulated to define an operon.<br/> | + | operon are either expressed together or not at all.<br /> Several genes must be both cotranscribed |
+ | and co-regulated to define an operon.<br /><br /> | ||
The first time “operon” was proposed is in a paper of French Academic Science, 1960. | The first time “operon” was proposed is in a paper of French Academic Science, 1960. | ||
The lac operon of the model bacterium E. coli was discovered and provides a typical | The lac operon of the model bacterium E. coli was discovered and provides a typical | ||
example of operon function. It consists a promoter, an operator, three structural genes and | example of operon function. It consists a promoter, an operator, three structural genes and | ||
a terminator. The operon is regulated by several factors including the availability of glucose | a terminator. The operon is regulated by several factors including the availability of glucose | ||
- | and lactose.<br/> | + | and lactose.<br /><br /> |
From this paper, the so-called general theory of the operon was developed. According to | From this paper, the so-called general theory of the operon was developed. According to | ||
the theory, all genes are controlled by means of operons through a single feedback | the theory, all genes are controlled by means of operons through a single feedback | ||
regulatory mechanism-repression. The first operon to be described was the lac operon in | regulatory mechanism-repression. The first operon to be described was the lac operon in | ||
E. coli. The 1965 Nobel Prize in Physiology and Medicine was awarded to François Jacob, | E. coli. The 1965 Nobel Prize in Physiology and Medicine was awarded to François Jacob, | ||
- | André Michel Lwoff and Jacques Lucien Monod for their discoveries concerning the operon and virus synthesis.<br/> | + | André Michel Lwoff and Jacques Lucien Monod for their discoveries concerning the operon and virus synthesis.<br /> |
- | <img src=" | + | </p> |
- | <p>Figure 1. Structure of Operon</p> | + | |
+ | <div align="center"><img src="../../method/Figure 1.png" /> | ||
+ | <p align="center"><strong>Figure 1.</strong> Structure of Operon</p></div> | ||
+ | <p align="justify">An operon is made up of several structural genes arranged under a common promoter and | ||
+ | regulated by a common operator. It is defined as a set of adjacent structural genes, plus | ||
+ | the adjacent regulatory signals that affect transcription of the structural genes. The | ||
+ | regulators of a given operon, including repressors, corepressors and activators, are not | ||
+ | necessarily coded for by that operon.<br /><br /> | ||
+ | As a unit of transcription, upstream of the structural genes lies a promoter sequence which | ||
+ | provides a site for RNA polymerase to bind and initiate transcription. Close to the promoter | ||
+ | lies a section of DNA called an operator.<br /><br /> | ||
+ | Operon regulation can be either negative or positive by induction or repression. Negative | ||
+ | control involves the binding of a repressor to the operator to prevent transcription. | ||
+ | Operons can also be positively controlled. An activator protein binds to DNA, usually at a | ||
+ | site other than the operator, to stimulate transcription. | ||
</p> | </p> | ||
- | + | <div align="center"><img style="width:600px;" src="../../method/Figure 2.png"/> | |
- | + | <p align="justify"><strong>Figure 2.</strong> Regulation of Operon | |
- | + | 1: RNA Polymerase, 2: Repressor, 3: Promoter, 4: Operator, 5: Lactose, 6: lacZ, 7: | |
- | + | lacY, 8: lacA. Top: The gene is essentially turned off. There is no lactose to inhibit the | |
- | + | repressor, so the repressor binds to the operator, which obstructs the RNA polymerase | |
- | Regulation of | + | from binding to the promoter and making lactase.Bottom: The gene is turned on.Lactose |
- | + | is inhibiting the repressor, allowing the RNA polymerase to bind with the promoter, and | |
- | + | express the genes, which synthesize lactase. Eventually, the lactase will digest all of the | |
- | + | lactose, until there is none to bind to the repressor. The repressor will then bind to the | |
- | + | operator, stopping the manufacture of lactase.</p></div> | |
- | + | ||
- | |||
- | + | </div> | |
- | + | ||
- | + | <div class="jobs_trigger"><strong>Regulatory Model</strong></div> | |
- | + | <div class="jobs_item" style="display: none;"><p align="justify">Regulation of gene expression includes four levels. We choose the transcriptional level to simulate the regulation both for its significance and model simplification.</p> | |
- | + | <div align="center"><img style="width:600px; height:auto;"src="../../method/Figure 3.png" /> | |
- | </p> | + | <p><strong>Figure 3.</strong>Regulation of gene expression.<br />Our regulation model is built based on the operon theory.<br /> The promoter region is regarded as the main regulatory region.</p></div> |
- | + | </div> | |
- | <div class="jobs_trigger"> <strong> | + | <div class="jobs_trigger"> <strong>Similarity and homology</strong></div> |
- | <div class="jobs_item" style="display: none;"><p align="justify">The | + | <div class="jobs_item" style="display: none;"><p align="justify">The sequence similarity is obtained by sequence alignment. It is defined as the proportion of the common subsequence in the aligned sequence. Any two sequences share a certain |
+ | similarity. It should be noted that similarity and homology are two different concepts.<br /><br /> | ||
+ | As with anatomical structures, homology between protein or DNA sequences is defined in | ||
+ | terms of shared ancestry. Two segments of DNA can have shared ancestry because of | ||
+ | either a speciation event or a duplication event. The terms “percent homology” and | ||
+ | “sequence similarity” are often used interchangeably. As with anatomical structures, high | ||
+ | sequence similarity might occur because of convergent evolution, or, as with shorter | ||
+ | sequences, because of chance. Such sequences are similar but not homologous. | ||
+ | Sequence regions that homologous are also called conserved.<br /><br /> | ||
+ | In our project, we use similarity to connect the exogenous gene with the original network. | ||
+ | Because there is a good chance that the exogenous gene is not homologous with the | ||
+ | genes in the network.</p> | ||
+ | </div> | ||
+ | <div class="jobs_item" style="display: none;"><p align="justify">The GRN matrix is the mathematical description of gene regulatory network in which “1” represents “enhance”, “-1” represents “repress” and “0” represents “no regulatory relationship”. The units(RU) in x-axis regulate the units in y-axis. A row can be seen as a vector containing all the information of the target(corresponding unit in the y-axis). Similarly, a column can be seen as a vector containing all the information of the regulator(corresponding unit in the x-axis).</p> | ||
+ | </div> | ||
+ | <div class="jobs_item" style="display: none;"><p align="justify">The sequence similarity is obtained by sequence alignment based on Needleman-Wunsch algorithm[FIXME: wiki link here]. The Needleman-Wunsch algorithm performs a global alignment on two protein sequences or nucleotide sequences. It was the first application of dynamic programming to biological sequence comparison. | ||
- | + | When dynamic programming is applicable, the method takes far less time than naive methods. Using a naive method, many of the subproblems are generated and sovled many times. The dynamic programming approach seeks to solve each subproblem only once. Once the solution to a given subproblem has been computed, it is stored to be looked up next time. | |
- | + | [Pic. 5 Dynamic programming and naive method] | |
- | + | ||
- | + | ||
- | + | ||
- | + | Like the Needleman-Wunsch algorithm, of which it is a variation, Smith-Waterman is also a dynamic programming algorithm. But it is a local sequence alignment algorithm. The famous BLAST(Basic Local Alignment Search Tool) is improved from Smith-Waterman algorithm. Although local algorithm has the desirable property that it is guaranteed to find the optimal local alignment, we decided to choose the global one because we regarded the segment sequence as a unit. | |
- | + | ||
- | + | ||
- | + | ||
- | + | ||
- | + | ||
- | + | ||
- | + | ||
- | + | ||
- | + | ||
- | + | ||
- | + | Sequences are aligned with different detailed methods in different situations. In the regulated side, what we care about is the DNA sequence. In the regulating side, it is the amino acid sequence. When it comes to predict the regulated behavior, we use a DNA substitution matrix to align promoter and protein coding sequences. In the prediction of regulating behavior, the substitution matrix BLOSUM_50 is used to align the amino acid sequences translated from protein coding sequences. | |
- | + | ||
- | + | ||
- | + | ||
- | Sequences are aligned with different detailed methods in different situations. In the regulated side, what we care about is the DNA sequence. In the regulating side, it is the amino acid sequence. When it comes to predict the regulated behavior, we use a DNA substitution matrix to align promoter and protein coding sequences. In the prediction of regulating behavior, the substitution matrix BLOSUM_50 is used to align the amino acid sequences translated from protein coding sequences. | + | |
The promoter similarities of the query unit and subject units are stored in a vector. The protein coding similarities are stored in another vector. These vectors are prepared to be used in the new network construction. | The promoter similarities of the query unit and subject units are stored in a vector. The protein coding similarities are stored in another vector. These vectors are prepared to be used in the new network construction. | ||
</p> | </p> | ||
- | + | </div> | |
</div><!--jobs container--> | </div><!--jobs container--> | ||
Line 223: | Line 234: | ||
<div id="jobs_container"> | <div id="jobs_container"> | ||
- | <div class="jobs_trigger"><strong> | + | <div class="jobs_trigger"><strong>Random Noise</strong></div> |
- | <div class="jobs_item" style="display: none;"><p class="bodytext"></p><p align="justify"> | + | <div class="jobs_item" style="display: none;"><p class="bodytext"></p><p align="justify">Normally, the similarity of two sequences will not be zero. Some computational |
- | </p> | + | experiments were carried out to study the random sequence similarities. We randomly |
+ | chose a gene in the network and generated 1000 random sequences. The alignment result | ||
+ | indicates that the random sequence similarities are Gauss distributed. The result suggests | ||
+ | that some similarities are out of statistic significance.</p> | ||
+ | <div align="center"> | ||
+ | <img src="../../method/Figure 4.png" /> | ||
+ | <p><strong>Figure 4.</strong> Random similarity distribution</p></div> | ||
+ | |||
+ | |||
</div> | </div> | ||
- | <div class="jobs_trigger"><strong> | + | <div class="jobs_trigger"><strong>Filter</strong></div> |
- | <div class="jobs_item" style="display: none;"><p align="justify"> | + | <div class="jobs_item" style="display: none;"><p align="justify">We need the genes highly similar to the exogenous one to interact with it. The program will |
- | + | align the exogenous gene(query) with genes in the network(subject) and get the original | |
- | + | similarities. In order to filter meaningless low values, a certain amount of random | |
- | + | sequences are generated for each query-subject alignment. Normally, 100 is sufficient. | |
- | </ | + | Because the sequence length will influence alignment result, random sequences are fixed |
- | + | at the same length as the query one. Then align random sequences with the subject | |
- | + | sequence. The statistic result of these random similarities is used as a threshold.<br /> | |
- | + | <div align="center">Threshold = μ + xσ</div><br /> | |
- | + | In the formula, μ is the average random similarity. σ is the standard deviation. x is used to | |
- | + | control the filter determined by machine learning. If the original similarity is lower than the | |
- | + | threshold, it is abandoned. It is usually means the original value is usually short of | |
- | </p> </div> | + | statistical significance.<br /><br /> |
+ | An example about filtring and consistency is presented in “Example”. | ||
+ | </p> | ||
+ | </div> | ||
- | <div class="jobs_trigger"> <strong> | + | <div class="jobs_trigger"> <strong>Construct new GRN</strong></div> |
- | <div class="jobs_item" style="display: block;"><p align="justify"> | + | <div class="jobs_item" style="display: block;"><p align="justify">If there is a three-unit network and they interact with each other as it is shown in the figure. |
- | The | + | The regulation is described by the GRN matrix.</p> |
+ | <div align="center"><img src="../../method/3.png" /> | ||
+ | <p style="font-size:18px;"><strong>Figure 5.</strong> Example network and its GRN matrix.</p></div> | ||
- | |||
- | + | <p style="font-size:20px;">If D is the exogenous unit, we can obtain three similarity data sets of D with the units in the | |
- | </br> | + | original GRN: |
- | + | <li style="margin-left:40px;">Promoter sequence similarity</li> | |
- | + | <li style="margin-left:40px;">Gene sequence similarity</li> | |
- | + | <li style="margin-left:40px;">Amino acid sequence similarity.</li> | |
- | </p> | + | <p> |
+ | The construction is equivalent to add a new column and a row into the original matrix.</p> | ||
+ | <div align="center"><img src="../../method/4.png" /> | ||
+ | <p><strong>Figure 6.</strong> Mathematical Equivalence</p></div> | ||
+ | <p>When filling the column, D is compared with the regulators of the unit in each row. The | ||
+ | regulations in the row are consider separately and marked as “positive group” and | ||
+ | “negative group”. The average similarity of each group represents the distance between | ||
+ | the exogenous unit and the group. D is supposed to have the larger one’s regulatory | ||
+ | direction(positive or negative). The regulatory intensity is the weight average regulation of | ||
+ | the chose group. The weight here is the amino acid sequence similarity.<br /><br /> | ||
+ | There are two conditions when fill the new row:<br /> | ||
+ | 1. There are units having the same promoter as the exogenous unit.<br /> | ||
+ | 2. There is no units having the same promoter as the exogenous unit.<br /><br /> | ||
+ | In condition 1, the units sharing the same promoter with the new member are picked out, | ||
+ | and the following steps are the same as the construction of the column. The difference is | ||
+ | the similarity used here is the gene sequence similarity. As explained in the regulation | ||
+ | model part, the promoter is the main regulatory region, but the following sequence is also | ||
+ | considered. Now the promoter is the same, so what we focus on are the gene sequences.<br /><br /> | ||
+ | In condition 2, the process is almost the same as constructing the new column. Promoter | ||
+ | similarity is used because it is the main region.</p> | ||
+ | <div align="center"> | ||
+ | <img src="../../method/5.png" /> | ||
+ | <p><strong>Figure 7.</strong> Construct New GRN</p></div> | ||
- | + | </div> | |
</div><!--jobs container--> | </div><!--jobs container--> | ||
</div> | </div> |
Revision as of 10:24, 27 September 2013
Methodologies
In order to simulate the GRN’s working and analyze the changing after exogenous gene imported, some advanced algorithms and classical methods are employed in the software. These algorithms and methods include Binary Tree method, Needle-Wunsch Algorithm, Decision Tree method, Hill Equation and PSO Algorithm. There are five parts of methodologies: Fetch Database, Alignment Analyze, New Network Construction, Network Model and Predict.
Fetch Database
Our software integrates all information we picked out about genes and generates a file named “all_info” —— all information about genes —— for the output graphical interface’s reading. In the meanwhile, the array of objects containing all information has been stored in computer memory which greatly improve the computing speed of our software. The format of all_info database: No. promoter_sequence gene_sequence gene_name ID left_position right_position promoter_name description The fetching module generates three files: old_GRN, all_info and uncertain_database.
Operon Theory and Regulatory Model
New Network Construction
If there is a three-unit network and they interact with each other as it is shown in the figure. The regulation is described by the GRN matrix.
Figure 5. Example network and its GRN matrix.
If D is the exogenous unit, we can obtain three similarity data sets of D with the units in the original GRN:
The construction is equivalent to add a new column and a row into the original matrix.
Figure 6. Mathematical Equivalence
When filling the column, D is compared with the regulators of the unit in each row. The
regulations in the row are consider separately and marked as “positive group” and
“negative group”. The average similarity of each group represents the distance between
the exogenous unit and the group. D is supposed to have the larger one’s regulatory
direction(positive or negative). The regulatory intensity is the weight average regulation of
the chose group. The weight here is the amino acid sequence similarity.
There are two conditions when fill the new row:
1. There are units having the same promoter as the exogenous unit.
2. There is no units having the same promoter as the exogenous unit.
In condition 1, the units sharing the same promoter with the new member are picked out,
and the following steps are the same as the construction of the column. The difference is
the similarity used here is the gene sequence similarity. As explained in the regulation
model part, the promoter is the main regulatory region, but the following sequence is also
considered. Now the promoter is the same, so what we focus on are the gene sequences.
In condition 2, the process is almost the same as constructing the new column. Promoter
similarity is used because it is the main region.
Figure 7. Construct New GRN
Network Model
Network analysis includes finding stable condition of network, adding new gene, finding new stable condition and changes from original condition to new condition. We use densities of materials to describe network condition. If all material densities are time-invariant, we can say the network condition is stable.
Predict
In some cases, importing exogenous gene is for enhancing or suppressing the expression of some specific genes in engineered bacteria itself. But it is hard to choose an appropriate regulatory gene. Our software analyzes the GRN forward as well as simulates by optimization algorithm backward for giving a reference of choosing to the users. Our software not only focused on the direct regulation but also focused on the global GRN. In the same time, controlling the expression of multiple genes in network has been realized by global prediction. What’s more, Particle Swarm Optimization (PSO) Algorithm makes it possible.
Database
This file contains the regulation between Transcription Factors.