Team:Davidson-MissouriW/Project

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 where given a certain value for capacity and weighted items of different values , to determine whether or not 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 millions 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.