Team:Alberta

Team Alberta represents the University of Alberta, from Edmonton. Our project, "The Littlest Mapmakers", is an attempt to create a biological computer capable of solving the Traveling Salesman Problem

The traveling salesman problem is a mathematical optimization problem that was first formally described in 1930, and has been intensively studied in the computer sciences as a benchmark for optimization algorithms. The problem asks:

Given a set of cities (or other destinations), and a list of the distances (or the travel time, fuel consumption, et cetera) 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 our project, we use DNA to compute solutions by converting all of the elements of the problem into representative sequences of DNA: cities become selectable marker genes (specifically, antibiotic resistance genes), paths between the cities become short, sticky-ended linkers (each of which is only able to ligate to two specific “city” strands), and the distance of a given path is represented by the concentration of the corresponding linker in solution. These pieces of DNA are successively ligated together to produce plasmids that signify “routes”, where the order in which the genes appear in the plasmid indicates the order in which the cities are visited.

The resulting plasmids are transformed into a bacterial culture, so that we can select for only those plasmids that include every city in the list. Then, plasmid DNA is extracted from the surviving bacterial colonies and analyzed to determine which plasmid (and thus which route) occurred the most frequently. This route, the one most favoured by the ligation reactions, is the optimal route!