# Team:Davidson-MissouriW/Project

### From 2010.igem.org

Line 15: | Line 15: | ||

<h4> What is the Knapsack problem?</h4> | <h4> What is the Knapsack problem?</h4> | ||

<img src="http://2010.igem.org/wiki/images/d/da/Davidson-MissouriWknapsack.png" alt="" width=300/> | <img src="http://2010.igem.org/wiki/images/d/da/Davidson-MissouriWknapsack.png" alt="" width=300/> | ||

- | <p>The knapsack problem is an NP-complete problem | + | <p>The knapsack problem is an NP-complete problem that asks whether: given a capacity and different weighted items, if there exists a subset of the items for which the sum of its values is equal to that of the capacity.<br><br> |

There are several variations of the knapsack problem. The one that we are focusing on involves attempting to fit various items of various weights into a knapsack with a certain capacity. You have solved the knapsack problem if you manage to fill the knapsack to capacity. Other variations include looking for the closest possible value to the capacity that we can fill if the capacity itself cannot actually be reached.<br><br> | There are several variations of the knapsack problem. The one that we are focusing on involves attempting to fit various items of various weights into a knapsack with a certain capacity. You have solved the knapsack problem if you manage to fill the knapsack to capacity. Other variations include looking for the closest possible value to the capacity that we can fill if the capacity itself cannot actually be reached.<br><br> | ||

In order to help people understand the knapsack problem and its complexity, we have built a <a href="http://72.22.219.205/knapsack">knapsack game</a>. In tutorial mode this game will give the user hints to help solve the problem. The challenge mode of the game should give the user an appreciation of the complexity of the knapsack problem and the overall class of NP-complete problems. | In order to help people understand the knapsack problem and its complexity, we have built a <a href="http://72.22.219.205/knapsack">knapsack game</a>. In tutorial mode this game will give the user hints to help solve the problem. The challenge mode of the game should give the user an appreciation of the complexity of the knapsack problem and the overall class of NP-complete problems. | ||

</p> | </p> | ||

<h4> Why Bacterial Computing? </h4> | <h4> Why Bacterial Computing? </h4> | ||

- | <p>In mathematics, there exists a class of complex mathematical problems, known as NP-complete problems, where there are no efficient algorithms to solve these problems other than exhaustive search of trying all the possible solutions one at a time and determining whether or not they are actually solutions. Bacterial computers offer a more efficient alternative approach to solving these NP-complete problems. By engineering a Bacterial computer, the | + | <p>In mathematics, there exists a class of complex mathematical problems, known as NP-complete problems, where there are no efficient algorithms to solve these problems other than exhaustive search of trying all the possible solutions one at a time and determining whether or not they are actually solutions. Bacterial computers offer a more efficient alternative approach to solving these NP-complete problems. By engineering a Bacterial computer, the billions of cells can simultaneously try the possible solutions and determine whether they are in fact a solution to the given problem. |

<br><br> | <br><br> | ||

Besides the much greater efficiency and speed, another advantage of bacterial computers is that it actually becomes more powerful as the number of cells increase from cell division. Despite the complexity of bacterial computing, it is quickly gaining popularity because of its many advantages over the traditional computer. | Besides the much greater efficiency and speed, another advantage of bacterial computers is that it actually becomes more powerful as the number of cells increase from cell division. Despite the complexity of bacterial computing, it is quickly gaining popularity because of its many advantages over the traditional computer. |

## Revision as of 20:58, 28 July 2010

## iGEM Davidson – MWSU 2010: Project

### Abstract

The Cre-lox system is a tool that involves the splicing of a specific pair of DNA sequences called lox sites with an enzyme called Cre recombinase. We implicated this system in attempts to manipulate gene expression that mimics randomly "selecting objects" to fill a knapsack in order to solve the knapsack problem. To do this we needed a set of variant lox sites in order to create constructs that would yield different subsets of survival and fluorescence to optimally fill the knapsack. Initially the design to address the knapsack problem had several vital components using modules that consisted of lox sites that floxed the TetA gene and RFP. In our attempts to solve the knapsack problem, we assembled 10 new lox sites with mutations in the 8 bp region and floxed 16 out of 21 possible lox site combinations with red fluorescent protein with these variant lox sites. We built a construct with a fluorescent protein gene downstream of TetA to test for the presence of a terminator within the TetA gene. Along the way, we built several tools to assist us in the wetlab. In addition, we recorded several observations regarding gene expression and codon optimization as we progressed. Characterizing and attempting to understand these foundational problems became one of the new focuses of this team.

### Introduction

#### What is the Knapsack problem?

The knapsack problem is an NP-complete problem that asks whether: given a capacity and different weighted items, if there exists a subset of the items for which the sum of its values is equal to that of the capacity.

There are several variations of the knapsack problem. The one that we are focusing on involves attempting to fit various items of various weights into a knapsack with a certain capacity. You have solved the knapsack problem if you manage to fill the knapsack to capacity. Other variations include looking for the closest possible value to the capacity that we can fill if the capacity itself cannot actually be reached.

In order to help people understand the knapsack problem and its complexity, we have built a knapsack game. In tutorial mode this game will give the user hints to help solve the problem. The challenge mode of the game should give the user an appreciation of the complexity of the knapsack problem and the overall class of NP-complete problems.

#### Why Bacterial Computing?

In mathematics, there exists a class of complex mathematical problems, known as NP-complete problems, where there are no efficient algorithms to solve these problems other than exhaustive search of trying all the possible solutions one at a time and determining whether or not they are actually solutions. Bacterial computers offer a more efficient alternative approach to solving these NP-complete problems. By engineering a Bacterial computer, the billions of cells can simultaneously try the possible solutions and determine whether they are in fact a solution to the given problem.

Besides the much greater efficiency and speed, another advantage of bacterial computers is that it actually becomes more powerful as the number of cells increase from cell division. Despite the complexity of bacterial computing, it is quickly gaining popularity because of its many advantages over the traditional computer.

#### Our Biological Design

-Band pass filter (TetA)

-Weights (Codon Optimization)

-Packing (Lox switches)

-Did we fill the knapsack (death, fluorescence)

Even cells with identical genes can produce different levels of protein. This variation is called noise.

While noise is generally treated as a necessary evil in synthetic biology, we chose to use the stochastic nature of gene expression to our advantage.

In order to control for the random nature of gene expression, we decided to implement a band pass filter. Essentially, this filter kills off cells that express either too much or two little of a chosen protein. Band pass filters harness and focus noise without eliminating it. We chose to use this system in order to help bridge the gap between a digital problem and an analog solution.

The combination of the tetA gene and an environment containing the antibiotic tetracycline creates a natural band pass filter. The tetA gene provides a level of resistance to tetracycline by creating efflux pumps that help the cell excrete the otherwise fatal tetracycline. However, these pumps come with a cost. They make the cell membrane more porous and permeable. With too many pumps, the cell cannot maintain homeostasis and dies; with too few pumps, the cells cannot remove tetracycline from its cytoplasm and dies from blocked protein synthesis.

With this band pass filter in mind, we decided to make the cell itself the knapsack. Overexpression of tetA would be analogous to exceeding the capacity of the knapsack. However, this decision left us with a fundamental problem: weights. We used a novel tool called codon optimization to assign weights. By rewriting the codons of the gene itself to more closely match the available tRNAs, we could theoretically increase how many pumps were produced by different versions of the same gene in a given time frame.

We planned to create a chain of these modules with a different fluorescence attached to each one to act as reporters. Each tetA and fluorescent color pair would be attached to a kind of genetic switch in the form of the Cre/lox system. A switch being on would correspond to packing an item of that weight into the knapsack. Allowing this system to run and randomly flip switches on and off would ensure that all possible combinations of packed knapsacks would be generated. The TetA band pass filter could give us a narrow subsets of cells that solved the problem. We could then figure out how a cell packed the knapsack based on the fluorescent reporters.