Team:Jefferson VA SciCOS/Project

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.