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

We performed some initial tests to confirm the efficacy of our assembly system. The Genomikon assembly 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.

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.

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.