Team:SUSTC-Shenzhen-B/algorithm

From 2012.igem.org

(Difference between revisions)
Line 11: Line 11:
         <div id="templatemo_main">
         <div id="templatemo_main">
             <div class="col col23">
             <div class="col col23">
-
                 <h2>Algorithm 1</h2>
+
                 <h2>Overview of Our Algorithm</h2>
-
<p>In 2007, Carleton L Kingsford et al. [1] described TransTermHP, a new computational method to rapidly and accurately detect Rho-independent transcription terminators. </p>
+
<p>Our team created a pc software and an online tool to help users calculate the efficiency of their terminators.</p>
 +
<p>To calculate the efficiency of terminator efficiency, there are three steps.</p>
 +
<p>First,we cut the input terminator sequence into three parts, including A tail, stemloop, T tail using  Carleton L Kingsford Scoring System (Scoring System 1).</p>
 +
<p>Next, we score the terminator based on the d'Aubenton Carafa Scoring System(Scoring System 2) or Elena A Lesnik Scoring System(Scoring System 3).</p>
 +
<p>Finally, we calculate the efficiency of terminator using the simulation formular created by our team.</p>
-
<p>They put forward an algorithm to predict Rho-independent terminators.</p>
+
<p>From the picture below we can see that there are two choices when scoring terminators. So there are two algorithms of our software.</p>  
-
<p>The first 15 bases of the potential tail sequence are scored using a function:</p>
+
-
<p> <img src="http://2012.igem.org/wiki/images/7/75/Equation.y1.JPG" alt="" class="img_fl img_border" />  (1)</p>
+
-
<p>where</p>
+
-
<br>
+
-
<p> <img src="http://2012.igem.org/wiki/images/7/7e/Equation%2Cy%2C2.JPG" alt="" class="img_fl img_border" />  (2)</p>
+
-
<p>for n=1...15 and  =1.</p>
+
-
<p>The energy of potential hairpin configurations adjacent to a reference position can be found efficiently with a dynamic programming algorithm. The table entry hairpin_score[i,j] gives the cost of the best hairpin structure for which the base of the 5' stem is at nucleotide position i and the base of the 3' stem is at position j. The entry hairpin_score[i,j] can be computed recursively as follows:</p>
+
-
<p>  <img src="http://2012.igem.org/wiki/images/0/06/Equation.y.3.JPG" />  (3)</p>
+
-
<p>The function energy(i,j) gives the cost of pairing the nucleotide at i with that at j, and loop_pen(n) gives the cost of a hairpin loop of length n. The hairpin's loop is forced to have a length between 3 and 13 nt, inclusive, by setting loop_pen(n) to a large constant for any n outside that range. The constant 'gap' gives the cost of not pairing a base with some base on the opposite stem and thus introducing a gap on one side of the hairpin stem.</p>
+
-
<p>Table 1</p>
 
-
<p>Parameters used to evaluate hairpins</p>
 
-
<p>Pairing   Energy</p>
 
-
<p>G-C           -2.3</p>
 
-
<p>A-T           -0.9</p>
 
-
<p>G-T           1.3</p>
 
-
<p>Mismatch   3.5</p>
 
-
<p>Gap           6.0</p>
 
-
<p>Loop_pen(n)    1•(n - 2)</p>
 
-
<p>Parameters used to evaluate the energy of a potential hairpin where n is the length of the hairpin loop.</p>
 
-
 
-
<p>Being the main algorithm, the algorithm introduced above was used by us to write a program named hairpinscore. Users may use the program to predict various potential structures and efficiencies of a Rho-indepent terminator by simply inputting the sequence of the terminator. </p>
 
-
 
-
<p>The program wrote in C# was divided into several parts. </p>
 
-
 
-
<p>When a sequence was input, firstly, all the potential T tail sequences will be found. </p>
 
-
 
-
<p>Secondly, for each potential T tail sequence, all the potential stem-loop sequences will be found.</p>
 
-
 
-
<p>Thirdly, for all the potential stem-loop sequences of all the potential T tail sequences, the hairpin scores will be calculated and sorted in ascending order. </p>
 
-
 
-
<p>Forthly, for the first several probable cut positions, the structures will be determined. The structure is be expressed in an array of "0" and "1", where "0" means the corresponding base isn't paired with any other bases and "1" means the corresponding base is paired with another base. </p>
 
-
 
-
<p>Fifthly, the d score was calculated by the following method:</p>
 
-
<p>d score = tail score * 18.16 - hairpin score * 96.59 / LH - 116.87, where LH stands for the length of the stem-loop sequence. The method of calculating d score was adjusted from the method put forward by Yves d'Aubenton Carafa et al. [2]. </p>
 
-
 
-
<p>Lastly, by analyzing the experiment data, we've got the relationship between termination efficiency and d score. Thus, once the d score is determined, the efficiency will be calculated easily.</p>
 
-
 
-
<p>In the future, the program may have more useful functions, for example, giving alternative sequences with efficiencies closed to a given number.</p>
 
-
 
-
<br>
 
-
<br>
 
-
<p>Reference</p>
 
-
 
-
<p>1. Carleton L Kingsford, Kunmi Ayanbule and Steven L Salzberg: Rapid, accurate, computational discovery of Rho-independent transcription terminators illuminates their relationship to DNA uptake. Genome Biology 2007, 8:R22.</p>
 
-
<p>2. d'Aubenton Carafa Y, Brody E, Thermes C: Prediction of rho-independent
 
-
Escherichia coli transcription terminators. A statistical
 
-
analysis of their RNA stem-loop structures. J Mol Biol 1990, 216:835-858.</p>
 
   
   

Revision as of 18:50, 23 September 2012

SUSTC iGEM Theme - Free CSS Template

SUSTC iGEM Theme - Free CSS Template

Overview of Our Algorithm

Our team created a pc software and an online tool to help users calculate the efficiency of their terminators.

To calculate the efficiency of terminator efficiency, there are three steps.

First,we cut the input terminator sequence into three parts, including A tail, stemloop, T tail using Carleton L Kingsford Scoring System (Scoring System 1).

Next, we score the terminator based on the d'Aubenton Carafa Scoring System(Scoring System 2) or Elena A Lesnik Scoring System(Scoring System 3).

Finally, we calculate the efficiency of terminator using the simulation formular created by our team.

From the picture below we can see that there are two choices when scoring terminators. So there are two algorithms of our software.