Team:Alberta/Overview

From 2013.igem.org

(Difference between revisions)
 
(4 intermediate revisions not shown)
Line 420: Line 420:
     <div class="titlebar">
     <div class="titlebar">
<br>
<br>
-
      <h3><font color="#A80000"><font size="6">The Littlest Mapmaker</font></font></h3>
+
<img src="/wiki/images/4/41/Ab_mapmen_title.png" width="600" height="95"></img><img src="/wiki/images/a/a5/2013-igem-logo.png" width="198" height="95"></img>
-
      <h4><i><font size="2">"Exploration into the world of <font color="#A80000">DNA Computing</font>"<br/>
+
-
        Team Alberta: University of Alberta</font></i></h4>
+
-
      <a href="http://www.ualberta.ca" class="ualberta-logo"><img src="/wiki/images/b/b3/Ualberta-logo.png" alt="University of Alberta"></img></a>
+
-
      <a href="https://2013.igem.org/Team:Alberta" class="igem-logo"><img src="/wiki/images/a/a5/2013-igem-logo.png" alt="iGem Main Page"></img></a>
+
     </div>
     </div>
     <div class="bin">
     <div class="bin">
Line 437: Line 433:
             <li><a href="/Team:Alberta/Parts">Submitted Parts</a></li>
             <li><a href="/Team:Alberta/Parts">Submitted Parts</a></li>
             <li><a href="/Team:Alberta/Accomplishments">Accomplishments</a></li>
             <li><a href="/Team:Alberta/Accomplishments">Accomplishments</a></li>
-
            <li><a href="/Team:Alberta/Attributions">Attributions</a></li>
 
           </ul>
           </ul>
         </li>
         </li>
Line 445: Line 440:
             <li><a href="https://igem.org/Team.cgi?year=2013&team_name=Alberta">Official Profile</a></li>
             <li><a href="https://igem.org/Team.cgi?year=2013&team_name=Alberta">Official Profile</a></li>
             <li><a href="/Team:Alberta/Sponsors">Sponsors</a></li>
             <li><a href="/Team:Alberta/Sponsors">Sponsors</a></li>
 +
            <li><a href="/Team:Alberta/Attributions">Attributions</a></li>
           </ul>
           </ul>
         </li>
         </li>
Line 478: Line 474:
             <a href="/Team:Alberta/Parts"><p>Submitted Parts</p></a>
             <a href="/Team:Alberta/Parts"><p>Submitted Parts</p></a>
             <a href="/Team:Alberta/Accomplishments"><p>Accomplishments</p></a>
             <a href="/Team:Alberta/Accomplishments"><p>Accomplishments</p></a>
-
            <a href="/Team:Alberta/Attributions"><p>Attributions</p></a>
 
         </div>
         </div>
       </div>
       </div>
Line 489: Line 484:
       <div class="block">
       <div class="block">
         <h2>The Travelling Salesman Problem</h2>
         <h2>The Travelling Salesman Problem</h2>
-
         <p>The Littlest Mapmaker is Team Alberta's endeavour to create a biological computer capable of solving  
+
         <p>MapMen is Team Alberta's endeavour to create a biological computer capable of solving  
           Travelling Salesman Problems (TSP), a general form of problem that asks:</p>
           Travelling Salesman Problems (TSP), a general form of problem that asks:</p>
         <p class="centered-well">Given a set of cities, and a list of the distances between each pair of those cities,  
         <p class="centered-well">Given a set of cities, and a list of the distances between each pair of those cities,  
Line 526: Line 521:
       <div class="block">
       <div class="block">
       <h2>Calculating Gene Concentration</h2>
       <h2>Calculating Gene Concentration</h2>
-
      <p>Recently, last year’s team supervisor Doug Ridgway sagely suggested
+
       <img src="/wiki/images/5/57/2013Alberta_New_algorithm.png" style="width:100%;"></img>
-
that while the algorithm that we have used to relate linker concentration
+
-
to path length may seem intuitively correct but that we may want to
+
-
exam its validity. We therefore tested a text-book example of a five-city
+
-
TSP that yields 4 best solutions and 8 sub-optimal solutions (illustrated
+
-
below). We then compared them to the solutions obtained when we
+
-
mimicked the linker weighting strategy by summing the reciprocal path
+
-
lengths. The reciprocal method correctly identified 3 of the 4 best paths
+
-
and showed close agreement with the rank of other solutions. It was
+
-
therefore adequate for our POP but not strictly accurate and would
+
-
probably become increasingly useless with increasing problem
+
-
complexity. Doug developed a formally correct algorithm which we have
+
-
described below (see revised strategy). </p>
+
-
       <img src="/wiki/images/7/7d/Z_minus_1_fig_678x856.png" style="width:100%;"></img>
+
       </div>
       </div>
       </div>
       </div>

Latest revision as of 03:43, 29 October 2013


Overview

The Travelling Salesman Problem

MapMen is Team Alberta's endeavour to create a biological computer capable of solving Travelling Salesman Problems (TSP), a general form of problem that asks:

Given a set of cities, and a list of the distances between each pair of those cities, what is the shortest possible route that travels to every city exactly once and then returns to the origin city?

In Biological Terms

To take advantage of the considerable information processing power of biology, we must create biochemical analogues for all of the components of the original problem. We begin by assigning a symbolic reporter gene or selectable marker gene to each of the six paths in our example map. The assignment is arbitrary; which gene is used for which path does not matter as long as it creates some kind of observable phenotype. For example, the path connecting the northeast city and the northwest city is symbolized by a gene coding for ampicillin resistance. The path from the northeast to city to the southeast meanwhile, is symbolized by a gene coding for kanamycin resistance.

Now, just as the travelling salesman might describe taking a particular route to his customers – leaving from the northeast origin city and taking the road to the southwest, then turning up the north road from there, then back down the southeast, before returning northward home from, we can also represent that series of paths as a sequence of genes: ChlorR, RFP, GFP, and KanR.

Finding the Path

Just as a computer using a brute force approach to the travelling salesman problem would test every route and tally the sum distance of the paths travelled, our biocomputer assembles a multitude of plasmids, representing every possible combination of paths, through a set of ligations that represent the legs of the salesman’s journey. In the first leg, we depart from the origin city along any of the available roads: AmpR, ChlorR, or KanR. In the plasmid production, we begin with a combinatorial ligation – one where all three of the genes are being ligated with origins of replication, but only one of the three is able to ligate onto each Ori, resulting in a collection of incomplete plasmids that each includes just one of the three genes.

Following the first gene ligation, a short linker piece is added, signifying the city that has been reached – all of the linkers are identical, there is no differentiation of routes based on this component. In the second leg of the journey, we perform a ligation with three more genes, representing all of the possible paths the salesman might take next – three colour genes. Again, each growing plasmid can only incorporate one of the new genes, so we obtain a random assortment of incomplete plasmids that each include one antibiotic resistance from the first ligation and one colour gene from the third ligation.

The third leg of the journey is identical to the second, incorporating an additional colour gene, and the final leg uses the three antibiotic genes once again. At the end of this process, we will have obtained a randomized distribution of 76 different kinds of plasmids representing all of the different possible permutations of the genes, capable of producing 18 unique phenotypes, and representing the six bi-directional solutions to the four-city travelling salesman problem.

MapMakers at Work

Once the plasmids have been produced, how can we use them to identify the correct solution? The answer is in the frequency with which each plasmid occurs: We create bias in the ligations during assembly so that genes that represent shorter paths are more likely to be incorporated into the plasmids, meaning in turn that the final product plasmids are more likely to be composed of several short-path genes. As a result, although we still expect to see plasmids representing every possible route, those plasmids that represent the shortest routes through the map will be much more common than plasmids representing lengthy routes. By identifying the most abundant plasmid, we identify the shortest route and thus the optimal solution.

The bias is introduced through the concentration of the reactants in each ligation. If a gene is meant to represent a short path, its concentration in the ligation will be higher than the others, and conversely, genes that are meant to represent lengthy paths will be included in lower concentrations than the others. As a result, at any given ligation step, the gene symbolizing the shortest available path is more likely to be incorporated. Among the product plasmids, genes are incorporated at a rate inversely proportional to their length. The concentration used for each gene in the ligation is described by the expression: –ln[Gene]∝(path distance)

To identify which of the plasmids is most frequent, the products are transformed into a bacterial culture. Because each of the genes produces an easily interpreted phenotype, this allows us to infer the most frequently transformed plasmid from the frequency of the colonies produced on agar plates. The plasmid carried by any given colony on the plates below can be readily identified by the combination of the colony colour (purple colonies have RFP and aCP, orange colonies have RFP and GFP, and green colonies have GFP and aCP), and the antibiotic resistances it exhibits, which are inferred from the plate on which it is growing. As an example, a purple colony growing on the kan/amp plate must have the Amp-Red-Blue-Kan-plasmid shown in the first column below.

Many of the colonies do not correspond to any valid route. For instance, an orange colony on the kan/amp plate has the plasmid Amp-Red-Green-Kan, which does not describe a valid circuit visiting each city exactly once – but because we can tell that this is an invalid solution, we would not count this colony when assessing the frequency of the valid plasmids. Any four-city travelling salesman problem has just three unique solutions, and so there are only three phenotypes that must be counted: purple kan/amp, orange kan/chlor, and green amp/chlor. The colonies of these three phenotypes are counted and compared, and the most frequently occurring plasmid is the optimal solution!

Calculating Gene Concentration