Team:Alberta/Overview

From 2013.igem.org

(Difference between revisions)
 
(9 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 470: Line 466:
           <a href="#Finding-the-Path"><p>Finding the Path</p></a>
           <a href="#Finding-the-Path"><p>Finding the Path</p></a>
           <a href="#Mapmakers"><p>MapMakers at Work</p></a>
           <a href="#Mapmakers"><p>MapMakers at Work</p></a>
-
           <a href="#Building-the-Routes"><p>Building the Routes</p></a>
+
           <a href="#Weight"><p>Calculating Gene Concentration</p></a>
           <h5>Project Sections</h5>
           <h5>Project Sections</h5>
             <a href="/Team:Alberta/Background"><p>Background</p></a>
             <a href="/Team:Alberta/Background"><p>Background</p></a>
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 507: Line 502:
       <div class="block">
       <div class="block">
         <h2>Finding the Path</h2>
         <h2>Finding the Path</h2>
-
         <p>Our biocomputer tests the different routes by assembling plasmids with the corresponding gene sequences.       
+
         <p>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. </p>
-
          All of the various possible plasmids are assembled simultaneously, through a series of biased ligation 
+
<center><img src="/wiki/images/9/95/AB_Genemap.png" style="width:35%;"></img></center>
-
          reactions that prefer assembly of plasmids that use short paths — that is, those genes that symbolize 
+
<p>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. </p>
-
          shorter paths are more likely to be incorporated into a plasmid than those which symbolize longer paths (see 
+
<img src="/wiki/images/7/7e/AB_Assemblyfull.png" style="width:100%;"></img>
-
          “Building the Routes” below for more detail on how we create this preference). Billions of plasmids are 
+
<p>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.<p/>
-
          produced in this way, and because of the bias in favour of short path genes, the predominating products are 
+
-
          gene sequences that correspond to very short routes. Identifying the predominant product of the assembly 
+
-
          would, in turn, identify the shortest path and therefore the solution to the problem. </p>
+
       </div>
       </div>
       <a class="anchor" id="Mapmakers"></a>
       <a class="anchor" id="Mapmakers"></a>
       <div class="block">
       <div class="block">
         <h2>MapMakers at Work</h2>
         <h2>MapMakers at Work</h2>
-
         <p>Unfortunately, as a byproduct of our assembly method, many of the plasmids generated this way do not
+
         <p>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. </p>
-
          correspond to any valid route through the assigned set of cities, and these need to be filtered out so that
+
         <p>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)</p>
-
          the frequency of production of each of the valid routes can be compared. To compute the validity of the  
+
        <img src="/wiki/images/9/95/Proportions.png" style="width:100%;"></img>
-
          plasmids, we transform them into a culture of E. coli, which are then grown on antibiotic-treated plates and
+
<p>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.<p/>
-
          allowed to express their reporter genes, making it simple to unambiguously identify the plasmid employed by
+
<img src="/wiki/images/6/6d/Ab_Solution_identification.png" style="width:100%;"></img>
-
          a given colony based on its colouration and resistances. </p>
+
<p>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! </p>
-
         <p>For example, consider the three possible routes for our sample four-city problem. The solution shown at the  
+
-
          right of the diagram below produces colonies that are coloured purple (a combination of the blue
+
-
          chromoprotein and red fluorescent protein reporter genes) and is able to survive on ampicillin/kanamycin
+
-
          plates. This is the only combination of genes that will result in this combination of colour and
+
-
          resistances. To determine which of the three routes is the solution to this travelling salesman problem, we
+
-
          plate the bacterial culture across these antibiotic plates and count the colonies that match with the three
+
-
          valid routes. The most commonly occurring bacterial genotype will correspond to the optimal route. </p>
+
-
        <img src="/wiki/images/8/8d/2013Alberta-mapmaker-states.png" style="width:100%;"></img>
+
       </div>
       </div>
-
       <a class="anchor" id="Building-the-Routes"></a>
+
       <a class="anchor" id="Weight"></a>
       <div class="block">
       <div class="block">
-
        <h2>Building the Routes</h2>
+
      <h2>Calculating Gene Concentration</h2>
-
        <p>We performed some initial tests to confirm the efficacy of our assembly system. The Genomikon assembly
+
      <img src="/wiki/images/5/57/2013Alberta_New_algorithm.png" style="width:100%;"></img>
-
          method requires that we be able to successfully bind and elute DNA from magnetic beads, and that we be able
+
-
          to perform successive ligations on the bead-bound strands. These are necessary for building the plasmid
+
-
          "routes", as described in the project overview page. The assembly is performed by anchoring origins of
+
-
          replication to the magnetic beads in a suspension, leaving each one with a single, free-floating sticky end,
+
-
          onto which a new gene can be ligated. Between ligations, the magnetic beads (and thus the anchored DNA) are
+
-
          held in place with a magnet while the rest of the reaction is washed away, allowing the beads to then be
+
-
          resuspended in a new reaction solution. For this reaction, we bound the Ori, then ligated a KanR gene onto
+
-
          it, followed by a short, 13-base-pair linker, and finally a ChlorR gene, all with wash steps in between.</p>
+
-
 
+
-
        <p>In the gel below, the second lane displays the result of an origin of replication (Ori) sample that was
+
-
          bound to the bead, washed and then re-eluted – the presence of DNA at the desired mass in this lane confirms
+
-
          the successful binding and elution. The third lane demonstrates that we can successfully ligate genes (KanR
+
-
          in this case) directly to the Ori at high efficiency and still safely elute them. In the fourth lane, we
+
-
          have ligated a 13-base-pair linker onto the existing Ori-KanR, followed by a second gene, ChlorR. Although
+
-
          the high-mass band suggests that ligation was successful, the fact that there is still a stronger band at
+
-
          the Ori-KanR mass suggests that the ligation has not proceeded to completion.</p>
+
-
 
+
-
        <p><b>Applying Magnetic Bead Assembly to the TSP Problem</b></p>
+
-
        <div class="expandable"><img src="/wiki/images/4/48/2013Alberta-Building-the-Routes-1.png"></img></div>
+
-
 
+
-
        <p>The second ligation adds a short, 25-base-pair linker strand to the free end, which replaces the free                             
+
-
          sticky end with one that is able to receive another gene, allowing (after another wash) for the next gene to
+
-
          be ligated onto the growing strand. </p>
+
-
 
+
-
        <div class="expandable"><img src="/wiki/images/4/45/2013Alberta-Building-the-Routes-2.png"></img></div><br/>
+
-
 
+
-
        <img src="/wiki/images/c/c6/Poster2_678x448.jpg" style="width:100%;"></img>
+
-
 
+
-
        <p>Once all of the genes have been ligated (alternating with linkers), a tail-piece that complements the 
+
-
        original bead-anchor DNA sequence is added, so that the finished product can be unbound from the beads and 
+
-
        will close upon itself to form the circular plasmid. In this fashion, a four-gene, roughly 5000-base-pair 
+
-
        plasmid is assembled in as little as an afternoon, cheaply and easily. </p>
+
-
 
+
-
        <div class="expandable"><img src="/wiki/images/f/f2/2013Alberta-Building-the-Routes-3.png"></img></div>
+
-
 
+
-
        <p>When we ligate a new gene to the growing strand in this process, we provide the reaction with several 
+
-
        genes, representing every path that the travelling salesman problem might take at that step. We bias the 
+
-
        system to favour short paths by setting the concentration of the added genes based on the reciprocal of the 
+
-
        corresponding path’s length, as adjusted by a calibration coefficient (C in the formula below). As a result, 
+
-
        a gene that symbolizes a short path will be included in the reaction at higher concentration than a gene that 
+
-
        symbolizes a long path, and the shorter path genes will occur more frequently among the product plasmids.</p>
+
-
 
+
-
        <div class="centered"><img src="/wiki/images/e/e9/2013Alberta-Gene-Expression-Formula.png" style="width:60%;">
+
-
        </img></div>
+
-
 
+
-
        <p>For example, if the path corresponding to the ampicillin resistance gene in a particular TSP takes only one 
+
-
        unit of distance, while the chloramphenicol resistance gene path in the same problem takes four units of 
+
-
        distance, then we might use 0.4 picomoles of the AmpR gene, and 0.1 picomoles of the ChlorR gene when adding 
+
-
        those two genes to the ligation. We would then expect the ratio of products to be roughly 4:1 AmpR to ChlorR, 
+
-
        favouring the shortest path more in proportion to its distance. </p>
+
       </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