Team:USTC-Software/algoritms and methods

From 2012.igem.org

(Difference between revisions)
 
Line 4: Line 4:
<html>
<html>
<head>
<head>
-
     <title>Achievements USTC-Software</title>
+
     <title>Database</title>
     <link rel="stylesheet" href="https://2012.igem.org/Team:USTC-Software/css/style?action=raw&ctype=text/css" type="text/css"/>
     <link rel="stylesheet" href="https://2012.igem.org/Team:USTC-Software/css/style?action=raw&ctype=text/css" type="text/css"/>
     <link rel="stylesheet" href="https://2012.igem.org/Team:USTC-Software/css/header_style?action=raw&ctype=text/css" type="text/css"/>
     <link rel="stylesheet" href="https://2012.igem.org/Team:USTC-Software/css/header_style?action=raw&ctype=text/css" type="text/css"/>
Line 10: Line 10:
     <link href='http://fonts.googleapis.com/css?family=Quicksand' rel='stylesheet' type='text/css'>
     <link href='http://fonts.googleapis.com/css?family=Quicksand' rel='stylesheet' type='text/css'>
</head>
</head>
 +
<body>
<body>
     <div id="page_wrapper">
     <div id="page_wrapper">
-
         <p class="h1">Algorithms and Methods</p>
+
         <p class="h1">Database</p>
-
         <p class="main">In order to make the computational process less time consuming, some advanced algorithms and classical methods are employed in the software. These algorithms and methods include Genetic Algorithm, Quicksort Algorithm and recursive method. To meet need of the common biological researchers, some innovative and original improvements have been proposed by our team to make the computing time much less and the results much more various.</p>
+
         <p class="main">Since this year our software has the functions of rebuilding the biological system by providing proper regulatees and regulators to users, a huge database containing comprehensive information about regulation is of great need. In order to make the calculated results experimentally feasible, we use in vivo data generated from Regulon Data Bank, a website providing all genome information about E.coli. K-12. Thus, our database includes all the information of E.coli. K-12. This is the very first time in iGEM competition that a team uses such a huge database, especially the massive regulatory information, in their software.</p>
-
 
+
         <p class="main">The database consists of two parts: first part stores regulatory information of operons to operons and genes to genes, and the second part contains genome information about operons, genes, promoters, terminators, RBS, 5' UTR and 3' UTR.</p>
-
        <p class="h2">Genetic Algorithm</p>
+
         <p class="main">To present the unique features of our database, we name it RegulonLib</p>
-
        <p class="main">Genetic Algorithm resembles the natural way of evolution. This algorithm is routinely used to search for optimal solutions of certain problems, belonging to the larger class of Evolutionary Algorithm. Thus, some terminologies are borrowed from natural evolution process such as generation, mutation, selection and inheritance.</p>
+
-
        <p class="main">A typical Genetic Algorithm should have the following requirements:</p>
+
-
        <p class="list">a genetic representation of the solution domain</p>
+
-
        <p class="list">a fitness function to evaluate solution domain</p>
+
-
        <p class="main">The method in classical Genetic Algorithm is to reduce the whole process into several generations. After each generation, the result will get closer to the optimum one. Every generation contains two phases: growth phase and selection phase. These two phases mimic natural growth process and selection process. At the very beginning of the Genetic Algorithm, a group of cells are initialized randomly with genes, proteins and reactions between them. Each cell represents a mathematical model, and in our case, this model is presented in Ordinary Differential Equations (ODE). These ODEs can be generated by listing all the reactions in each cell using chemical master equations. Then the evolutions begin.</p>
+
-
        <p class="main">Here is the introduction to classical phases.</p>
+
-
        <p class="h3">1. Growth phase</p>
+
-
        <p class="main">Assuming there are n cells in the initialization step, then in growth phase all these cells will duplicate themselves. The duplicated cells will go through randomly mutation process. In our software, these mutations include:</p>
+
-
        <p class="list">1) Changing the degradation rate of a randomly chosen protein.</p>
+
-
        <p class="list">2) Changing the kinetic constant of a randomly chosen reaction.</p>
+
-
        <p class="list">3) Adding a new gene, in the meantime the corresponding protein should be added as well, including the transcriptional reaction and the degradation reaction of the protein.</p>
+
-
        <p class="list">4) Adding a regulation. Namely adding a regulatory reaction between a gene and a protein, and the kinetic constants are randomly drawn in (0,1).</p>
+
-
        <p class="list">5) Adding a post transcriptional reaction. As for this case, there are several kinds of modifications</p>
+
-
        <p class="list">5.1) A+B->AB: Binding between two proteins</p>
+
-
        <p class="list">5.2) A+B->A: catalytic reaction</p>
+
-
        <p class="list">5.3) A+BC->B: partial catalytic</p>
+
-
        <p class="list">5.4) A->A*: post transcriptional modification</p>
+
-
        <p class="list">5.5) BC->B: partial degradation</p>
+
-
        <p class="main">After a generation, the 2*n cells will go to another phase.</p>
+
-
        <p class="h3">2. Selection phase</p>
+
-
        <p class="main">The fitting function, or score function, is used to evaluate each cell according to the mathematical model in each one. Before this phase begins, the ODE model of each cell should be firstly extracted. From all the ODEs, the software can get the simulated data. The score function here is to give each cell a score by comparing the simulated data and the input data. To make it clear in a mathematical way, the scoring function is:</p>
+
-
        <p class="list">1)</p>
+
-
        <p class="list">2)</p>
+
-
         <p class="main">represents the input data of the ith species at the jth time point, and the represents the calculated data of the ith species at the jth time point. So these two functions actually calculates the variance of simulated behavior and the input behavior.</p>
+
-
        <p class="main">Thus after each cell are given a score, Quicksort Algorithm is utilized in ranking all the 2n cells. Then the first n cells will remain for the next generation, the other cells will be eliminated.</p>
+
-
 
+
-
        <p class="main">That is a generation of the whole Genetic Algorithm. Then the group of cells will go through several hundred or thousands of generations. The final several cells are assumed to the cells with the best behaviors.</p>
+
-
        <p class="h2">Our Improvements</p>
+
-
        <p class="main">By merely using classical Genetic Algorithm is proved to be slow in computational process. As for some steps in the algorithm, some cells with potentials may be eliminated due to the low score at that generation. Moreover, the original algorithm does not consider cells with different topology levels and does not sort the cells by complexity, either. Thus, to avoid these problems, we make some important changes to the algorithm, and the results prove to be better and more practical than the classical one.</p>
+
-
 
+
-
        <p class="main">1. We classify mutations into two kinds: mutation of topology and mutation of parameter. Topology mutation only contains mutation type 3-----adding a new gene. In order to preserve the potential properties of each cell, for some generations in the grown phase cells can only have topology mutations, and then the cells will undergo parameter mutations. This special design of Genetic Algorithm helps preserve cells with potentials. In addition, we can thus provide cells with different complexity levels.</p>
+
-
         <p class="main">2. To avoid the results concentrated around the local optimum, we initialize several groups of cells with different initial conditions, and we duplicate and selection cells in each group. With this improvement, we will get cells with different behaviors, providing users with more choices.</p>
+
-
         <p class="h2">Quicksort Algorithm</p>
+
         <p class="h2">1. Regulatory Information</p>
-
         <p class="main">Quicksort Algorithm has been ranked among top 10 algorithms by IEEE. Quicksort method is mainly used in the case of sorting or retrieving. Its properties like time and computational space saving makes it outstanding among all the sort methods, and that is why it is so commonly used in simulations of nearly all the fields.</p>
+
         <p class="main">These two matrices share some basic properties. The regulatory direction is from the regulators in the ith row to the regulatees in the jth column (i, j are row and column indices), and the element at (i,j) represents the regulatory relations. In our case, several kinds of regulatory relations are considered shown as follows:</p>
-
         <p class="main">The core of Quicksort Algorithm is a recursive method which reduces the complexity of the problem step by step, and the final step should be a simple case easy to deal with. Recursion makes the problem less difficult to understand and more feasible in programming.</p>
+
         <p class="list">1: positive regulation</p>
-
         <p class="main">In simple pseudocode, the algorithm can be expressed as this:</p>
+
         <p class="list">-1: negative regulation</p>
-
         <pre>
+
         <p class="list">0: no regulation</p>
-
            Function quicksort('arrary')
+
        <p class="list">2: both positive and negative regulation</p>
-
                If length('array') <=1
+
         <p class="list">-2: unknown regulation</p>
-
                    return 'array'
+
         <p class="main">As to the operon-operon matrix, it has dimension of 549*549 and gene-promoter matrix is 773*180. Recursive method is employed to find proper regulators and regulatees.</p>
-
                select and remove a pivot value 'pivot' from 'array'
+
-
                create empty list 'less' and 'great'
+
-
                for each 'x' in 'array'
+
-
                    if 'x' <= 'pivot'  then  appendix 'x' to 'less'
+
-
                    else appendix 'x' to 'great'
+
-
                return concatenate(quicksort('less'), 'pivot', quicksort('great'))
+
-
         </pre>
+
-
         <p class="main">In our case, the array stands for the scores of all the cells. Here we use Quicksort Algorithm to rank all the cells according to their scores, and then the first several cells will be selected waiting for the next generation.</p>
+
-
         <p class="h2">Recursion method</p>
+
         <p class="h2">2. Genome information</p>
-
         <p class="main">As we integrate all the regulation in a matrix, and to make the database compatible with the software, we use a recursion method to find the regulatory matrix in the database matrix. After finding the matrix, we then can used the parts in the database to rebuild the system.</p>
+
         <p class="main">Genome information of operons, genes, promoters, RBS, terminators, 5' UTR and 3' UTR are stored in over 10000 SBOL format files. Some details are listed below:</p>
-
         <p class="main">This recursive method aims to find small matrix in a big matrix, and recursion makes it universal to every case. Imagine finding an m*m matrix in a n*n matrix (n>m), the finding steps are as follows:</p>
+
         <p class="list">2652 Operons, along with names and components (gene, promoter, terminator) for each</p>
-
         <pre>
+
        <p class="list">4554 Genes, along with name, identifier, sequence, start position, end position, start codon and  end codon for each. </p>
-
            FindMatrix(n*n database matrix, m*m target matrix)
+
         <p class="list">3734 Promoters, along with name, identification ,sigma factor and sequence for each.</p>
-
                If (m ==1 )
+
        <p class="list">207 Terminators, along with identifier, sequence and PubMed ID for each.</p>
-
                    Return target matrix
+
        <p class="list">179 RBS, along with identifier, start position, end position and sequence for each.</p>
-
                Else findMatrix( n*n database matrix, (m-1)*(m-1) target matrix)
+
        <p class="list">3731 5' UTR & 3' UTR, along with number of 5' UTR, number of 3' UTR, start position of 5' UTR, end position of 5' UTR, start position of 3' UTR, end position of 3'UTR, sequence of 5'UTR and sequence of 3' UTR.</p>
-
                Return choices
+
        <p class="main">Here is a screenshot of a SBOL file</p>
-
         </pre>
+
         <img src="" alt="" />
-
         <p class="main">Computational tests have proved that this recursion method is efficient and time saving in finding matrix. And as for our database, two kinds of database matrix of 773*773, 549*549 are generated on users choice.</p>
+
         <p class="main">Based on this unique and comprehensive database, we also build a clotho application with the same name Regulon Lib.</p>
-
          
+
         </div>
-
    </div>
+
</body>
</body>
</html>
</html>

Latest revision as of 15:33, 26 October 2012

global_header

igem

Database

Database

Since this year our software has the functions of rebuilding the biological system by providing proper regulatees and regulators to users, a huge database containing comprehensive information about regulation is of great need. In order to make the calculated results experimentally feasible, we use in vivo data generated from Regulon Data Bank, a website providing all genome information about E.coli. K-12. Thus, our database includes all the information of E.coli. K-12. This is the very first time in iGEM competition that a team uses such a huge database, especially the massive regulatory information, in their software.

The database consists of two parts: first part stores regulatory information of operons to operons and genes to genes, and the second part contains genome information about operons, genes, promoters, terminators, RBS, 5' UTR and 3' UTR.

To present the unique features of our database, we name it RegulonLib

1. Regulatory Information

These two matrices share some basic properties. The regulatory direction is from the regulators in the ith row to the regulatees in the jth column (i, j are row and column indices), and the element at (i,j) represents the regulatory relations. In our case, several kinds of regulatory relations are considered shown as follows:

1: positive regulation

-1: negative regulation

0: no regulation

2: both positive and negative regulation

-2: unknown regulation

As to the operon-operon matrix, it has dimension of 549*549 and gene-promoter matrix is 773*180. Recursive method is employed to find proper regulators and regulatees.

2. Genome information

Genome information of operons, genes, promoters, RBS, terminators, 5' UTR and 3' UTR are stored in over 10000 SBOL format files. Some details are listed below:

2652 Operons, along with names and components (gene, promoter, terminator) for each

4554 Genes, along with name, identifier, sequence, start position, end position, start codon and end codon for each.

3734 Promoters, along with name, identification ,sigma factor and sequence for each.

207 Terminators, along with identifier, sequence and PubMed ID for each.

179 RBS, along with identifier, start position, end position and sequence for each.

3731 5' UTR & 3' UTR, along with number of 5' UTR, number of 3' UTR, start position of 5' UTR, end position of 5' UTR, start position of 3' UTR, end position of 3'UTR, sequence of 5'UTR and sequence of 3' UTR.

Here is a screenshot of a SBOL file

Based on this unique and comprehensive database, we also build a clotho application with the same name Regulon Lib.

Retrieved from "http://2012.igem.org/Team:USTC-Software/algoritms_and_methods"