# Davidson Missouri W/Background Information

### From 2007.igem.org

**Background Information**| Current Project: Solving the Hamiltonian Path Problem

*in vivo*| Mathematical Modeling | Gene Splitting | Results | Traveling Salesperson Problem | Software | Resources and Citations

In 1994 Adleman developed a system to solve the Hamiltonian Path problem using DNA *in vitro*. We have implemented a bacterial system to solve Hamiltonian Path problems *in vivo*. Our bacterial computer works by taking advantage of the Hin Recombinase protein and *hixC* sites to perform a "flipping" operation. By strategically placing *hixC* sites on a plasmid, along with reporter genes, we can simulate paths on a graph through flipping.

# The Hin Recombinase/*hixC* System Revisited

*Salmonella typhimurium* is a bacterium which moves using flagella. Depending on its environment, it expresses different sets of surface proteins on its flagella. It is able to change this expression through the use of Hin Recombinase and *hixC* sites. The Hin Recombinase enzyme catalyzes the inversion of DNA that lies between a pair of *hixC* sites. By flipping DNA segments between *hixC* sites *S. typhimurium* can express alternate flagellar surface proteins.

- Given a segment of DNA, flanked by
*hixC*sites (blue arrow):

- Two dimers of Hin Recombinase protein attach to a pair of
*hixC*sites around the DNA segment.

- The DNA segment between the pair of
*hixC*sites is inverted. Note that the green arrow is unaffected.

# Flipping Pancakes

In the 2006 iGEM competition, Davidson and Missouri Western used Hin Recombinase and *hixC* to model a mathematical problem, called the Pancake Flipping problem. The problem is the following: given a stack of pancakes which are burnt on one side and golden on the other, and two spatulas, what is the minimum number of flips required to sort the stack by pancake size and with all burnt sides facing downwards?

Using mathematical models it is possible to compute these estimates for small stacks. However, adding pancakes to a stack increases the number of possible permutations non-linearly. The number of possible stacks of *n* pancakes is equal to: 2^n (n!). Thus traditional computers are not well-suited for computations involving large pancake stacks.

However, it is possible to model pancake flipping using bacteria. If each pancake is given an identification number, along with a sign designating its orientation, then this can be stated equivalently using genes. Thus the following images show equivalent notations for pancake stacks:

By taking advantage of this notation it is possible to use bacteria as computers to solve pancake-flipping problems.

# Why Use Bacteria?

Although we have demonstrated how it is possible to solve mathematical problems using bacteria, it may not be obvious why this is helpful. Due to the exponential increase in problem size that arises from a linear increase in pancake stack size, traditional computers are not good at solving large pancake problems. This type of problem, as well as the Hamiltonian path problem, are not known to be solvable in polynomial time using traditional algorithms.

However, bacterial computers are not affected as much by this problem. If each plasmid within a bacterium is a computer, each bacterium contains several plasmids, and a single flask of bacteria contains billions of bacteria, then it is trivial to produce **billions of computers**. Each computer will be acting in parallel with the others, drastically reducing the amount of time required to reach a solution. The use of bacterial computers is thus a way to allow us to solve computational problems which traditional computers cannot.