Team:Jefferson VA SciCOS/Project

From 2014hs.igem.org

(Difference between revisions)
Line 31: Line 31:
{|align="justify"
{|align="justify"
|
|
-
'''''<h3>Solving a 4-Node Traveling Salesman Problem Using the Hin/hixC Recombinant System</h3>'''
+
'''''<h3>Taking a Previous Encoding Scheme a Step Further</h3>'''
-
----
+
-
Our project’s goal was to assess the accuracy, scalability, and feasibility of a novel bacterial computer paradigm for solving a 4-node Traveling Salesman Problem.
+
-
|}
+
-
{|align="justify"
+
-
|
+
-
'''''<h3>Solving a 4-Node Traveling Salesman Problem Using the Hin/hixC Recombinant System</h3>'''
+
----
----
Our project’s goal was to assess the accuracy, scalability, and feasibility of a novel bacterial computer paradigm for solving a 4-node Traveling Salesman Problem.
Our project’s goal was to assess the accuracy, scalability, and feasibility of a novel bacterial computer paradigm for solving a 4-node Traveling Salesman Problem.

Revision as of 22:33, 20 June 2014

Contents

Solving a 4-Node Traveling Salesman Problem Using the Hin/hixC Recombinant System


Our project’s goal was to assess the accuracy, scalability, and feasibility of a novel bacterial computer paradigm for solving a 4-node Traveling Salesman Problem.

Bacterial Computing: The Future of the IT Industry All in an Agar Plate


Where would humanity be without the advent and rise of the computer? The 21st century has marked humanity’s entrance into a new Digital Age; now, more than ever, does the global marketplace and humanity itself depend on a thriving information technology sector. From the pocket-sized computing devices that we use to manage our day-to-day tasks to the massive supercomputers that mirror human intelligence, from the databases that store millions of patient’s records to the Big Data servers that analyze the vast number of financial transactions that take place every second, computing has evolved into a ubiquitous science that is both humanity’s present as well as its future. For years, the physical limitations that deterred the development of faster, more efficient computing devices were easily maneuverable, allowing computing to present itself as the seemingly perpetual gale force that propelled the sails of our global economy.

But now, the winds of the Digital Revolution seem to be stilling. Little do people realize that Moore’s Law, the golden standard for advances in computing, is coming to an end. Moore’s Law, a bold vision for the future originally proposed in the early 1970s, set a clear goal for the future of computing hardware: every two years, the transistor count on a typical microprocessor (our computing capacity) would double. Now, however, we’ve finally hit the physical limit where transistors are packed so close together that reliable electron flow can no longer be sustained. This dilemma has raised a hue and cry throughout the computing industry, and has led to extensive research and development into new avenues of computing. Can we really transcend this computational limit? Could it be possible that the future of the computing industry be quantum computing? Or could it be something else?

Our group believes that synthetic biology, specifically the nascent field of bacterial computing, holds the key to the IT industry’s qualms. The computational capacity of biological systems is shockingly vast and amazingly robust. Unlike standard computers, bacterial computers may be able to autonomously solve quantitative problems in a massively parallel fashion; moreover, because bacteria are constantly dividing, the number of processors working on the problem grows exponentially with culture time. Also, bacterial computers use much less energy than standard computers to solve the HCP and the agar plates that they’re cultured on can even fit in the palm of your hand.

The 2007 Davidson-Missouri iGEM team demonstrated an algorithm using DNA constructs and the Hin recombinase/HixC site system capable of solving a three node Hamiltonian Path Problem. However, this team’s ground-breaking research left several questions unanswered that our group found critical to the future of bacterial computing:

How accurate is bacterial computing? Can the algorithm be expected to reliably converge to a solution state regardless of the initial configuration?

How scalable is bacterial computing? Will our group be able to scale the technique up to larger node problems and how stable are hixC-site constructs for different proteins? Will our group be able to solve a completely different problem than the Hamiltonian Path Problem?

How feasible is bacterial computing? Bacterial computing features a paradigm where the hardware is far cheaper than the software. How will this compare to other computing paradigms when we perform a cost-benefit analysis?

With these guiding questions in mind, our group has proposed a project that assesses the accuracy, scalability, and feasibility of a bacterial computer paradigm for solving different initial configurations of a 4-node Traveling Salesman Problem. Our work proposes a novel way of encoding the Traveling Salesman Problem using variable Ribosome Binding Site strengths and DNA constructs that can be solved by the Hin recombinase/HixC site system.

The Traveling Salesman Problem


Imagine you’re a salesman tasked with delivering goods to a set of towns. How can you find the shortest possible route to travel in order to visit every town exactly once to deliver your goods? This is exactly what the Traveling Salesman Problem seeks to find. The problem itself is extremely crucial to the transportation and shipping industry, where finding the shortest route possible can mean millions of dollars saved on the thousands upon thousands of goods delivered daily. Could bacteria performing computations in an agar plate hold the answer to this longstanding question?

Taking a Previous Encoding Scheme a Step Further


Our project’s goal was to assess the accuracy, scalability, and feasibility of a novel bacterial computer paradigm for solving a 4-node Traveling Salesman Problem.

The Hin Recombinase/hixC Site System


The Hin Recombinase/hixC Site System is what breathes life into the encoding scheme we designed above. The system designed by a 2006 iGEM team is derived from Salmonella, where Hin regulates how flagellin genes are expressed. In our project, the system was used to constitutively shuffle the gene halves until a solution is arrived at.

The Path We Chose to Solve


The 2007 Davidson/Western Missouri iGEM team constructed 3 initial pathways to demonstrate that the Hamiltonian Path Problem could be solved in vivo.

We decided to use one of the starting constructs as a scaffold from which we could build our own composite pathway because each of the constructs contains three nodes: two split genes and a double terminator. Also, in the interest of time and resources, we were not concerned with constructing several pathways of our own as the Davidson/Western Missouri iGEM team had done. We ended up using HPP-A2 because it showed evidence of no fluorescence without Hin, which was the expected result as recorded by the Davidson/Western Missouri iGEM team. To HPP-A2, we added an RBS of moderate strength, as determined by the ribosome binding calculator and published values in literature. Compared to B0034, the RBS used in HPP-A2, B0032 is reported to exhibit 32% binding efficiency. Downstream of the RBS, we added another node: a BFP split-gene part. Thus, the order of our final part, from 5’ to 3’, was HPP-A2 + RBS + BFP1 + hixC + BFP2. We wanted to transform E.coli containing this composite pathway with Hin recombinase in order to shuffle the gene halves randomly and with varied efficiency, resulting in a solution to the TSP.