# Team:Davidson-MissouriW/Project

(Difference between revisions)
 Revision as of 13:20, 29 July 2010 (view source)Eushiu (Talk | contribs)← Older edit Revision as of 13:21, 29 July 2010 (view source)Eushiu (Talk | contribs) Newer edit → Line 15: Line 15:

What is the Knapsack problem?

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.

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.

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.        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.

## 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 using massive parallel computing. 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

Cells of identical genotype 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 produces 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. Therefore, tetA is a band pass filter.

With this band pass filter in mind, we decided to make each cell a knapsack. Overexpression of tetA would be analogous to exceeding the capacity of the knapsack. However, we still had to solve a fundamental problem: weights. We used a novel tool called codon optimization to assign weights. By rewriting the codons of the tetA gene, we could alter the number of pumps produced by different versions of the same gene in a given time frame.

We planned to produce a chain of tetA modules with a different fluorescent protein attached to each one to act as visual and biochemical reporters. Each tetA and fluorescent color pair would be attached to a genetic switch in the form of the Cre/lox system. A switch being on would correspond to packing an item of that weight (color and tetA level) 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.

### Summary and Outlook

Our summer project culminated with foundational advances in the fields of codon optimization, cre-lox characterization, and gene expression. The team successfully built 6 tetA constructs with varying levels of codon optimization and deoptimization. We also assembled eleven novel lox sites and characterized interactions between several of them in the presence of cre protein. While choosing and characterizing reporters, we observed variations in gene expression due to environmental factors and inherent variability in bacterial cells. We designed tools such as the VeriPart and the Oligator, among others, to assist our wetlab research.

With the help of this integral research, we have the tools and knowledge to address the knapsack problem. Looking to the future, we wish to further experiment with varying levels of codon optimization and gene placement. Finally, we wish to construct different modules that could solve the knapsack problem.

top