Team:Alberta/Overview

Overview

The Travelling Salesman Problem

The Littlest Mapmaker 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 solve a TSP biologically, we must create biochemical analogues for all of the components of the original problem. For the Littlest MapMaker, we do this by assigning a symbolic bacterial reporter gene or selectable marker gene to each of the paths that connect a pair of cities. For instance, for the example map featured here, the path connecting cities A and B is symbolized by a gene coding for ampicillin antibiotic resistance. This allows us to describe routes through the network as a sequence of genes, standing for a sequence of paths. Again for example, the route travelling from city A to B, then to C, and then to D before returning to A is described by the sequence ampicillin resistance gene, followed by green fluorescent protein gene, then blue amyl chromoprotein gene, and finally chloramphenicol resistance gene.

Finding the Path

Our biocomputer tests the different routes by assembling plasmids with the corresponding gene sequences. All of the various possible plasmids are assembled simultaneously, through a series of biased ligation reactions that prefer assembly of plasmids that use short paths — that is, those genes that symbolize shorter paths are more likely to be incorporated into a plasmid than those which symbolize longer paths (see “Building the Routes” below for more detail on how we create this preference). Billions of plasmids are 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.

MapMakers at Work

Unfortunately, as a byproduct of our assembly method, many of the plasmids generated this way do not correspond to any valid route through the assigned set of cities, and these need to be filtered out so that the frequency of production of each of the valid routes can be compared. To compute the validity of the plasmids, we transform them into a culture of E. coli, which are then grown on antibiotic-treated plates and allowed to express their reporter genes, making it simple to unambiguously identify the plasmid employed by a given colony based on its colouration and resistances.

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.

Building the Routes

Our plasmid assembly system relies upon the achievements of previous Team Alberta iGEM entries, 2009’s BioBytes and 2010’s Genomikon assembly methods. The method relies on the aforementioned symbolic representation of the paths in the salesman's route with genes and pieces of DNA. A route starts at the origin of replication (the salesman's home city), travels along some gene (the first path of the planned journey), meets a linker (the city at the end of that path), then travels along a second gene (the second path) to another linker (the second city), on to a third gene (the third path) and a third linker (the third city), and finally a fourth gene (the final path) which must return to the origin (the addition of a final tail-linker that will close the plasmid).

The actual assembly begins with origins of replication anchored at one end to magnetic beads in a suspension within a reaction microfuge tube. The anchored strands have a single, free-floating sticky end. In the first ligation, the three genes representing the possible first paths on the salesman's route are added to the bead suspension, along with ligase and buffer. The genes are able to ligate on to the free sticky end of the origin of replication; the ligating of a given gene represents the salesman having planned to travel along that path. Once the new gene has been ligated on, we use a magnet to hold the beads (along with the anchored DNA) inside the reaction tube, while washing away the rest of the reaction, including the enzyme, buffers, and any non-ligated DNA that remains. The beads are then resuspended in a new reaction mixture, containing the next ligation step (the linker). The first and second ligation steps are shown in the schematics below.

Applying Magnetic Bead Assembly to the TSP Problem

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.

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.

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.

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.