Living Computers
Computer-in-a-petri-dish?
So much is made about man vs machine in science fiction, that maybe we’ve neglected to pay attention to the entity which may trump us both: bacteria. A team of US Researchers have recently published an article in the Journal of Biological Engineering that suggests an innovative use of synthetic biology to perform complex computations.
Consider a classical computer science problem: the Hamiltonian Path. Imagine that you’re a tourist, and you have a map of all the cities you wish to visit along with all the roads which connect those cities. Finding a Hamiltonian Path, in this case, would mean traveling to each city you want to visit without having to go through any city more than once. While this may seem like simple map work, computer scientists have so far been unable to find a way of efficiently finding a Hamiltonian Path that does not go through an exhaustive list of paths.
However, a team of scientists from across four academic institutions (Missouri Western State University, Davidson College, North Carolina Central University, and Johnson C. Smith University) have cleverly engineered a solution using Escherichia coli bacteria to solve a basic form of the Hamiltonian Path with only three cities.
The cities were represented by a combination of genes causing the bacteria to glow red or green, and the possible routes between the cities were explored by the random shuffling of DNA. Bacteria producing the correct answer glowed both colours, turning them yellow.
The magic behind the bacterial solution is that, through sheer brute force made possible by bacterial exponential multiplication, the bacteria can explore a wide range of possible solutions to the Hamiltonian Path Problem in parallel! 1000 bacteria = 1000 test runs! So, if the Hamiltonian Path Problem is harder than you expect, then simply let the bacteria divide. If they divide three more times, you’ll have increased the “computational” power available to you by a factor of 8!
But what makes the Hamiltonian Path Problem so interesting? If you’re a computer science buff, you’d know that the Hamiltonian Path is classified as NP complete, something which describes the most difficult search problems out there. More formally, an NP complete problem is a search problem that has an answer that can be checked/verified in a quick and efficient manner, but, as far as we know, does not have a quick and efficient way to solve. Given this very precise and esoteric definition, you would think the number of NP complete problems would be very limited. In actuality, NP complete problems show up everywhere. These problems range from esoteric ones like the Knight’s tour problem, the Travelling salesman problem, to challenging scheduling and traffic routing questions in telecommunications networks and multicore processors, and even to games like Sudoku and Battleship! (A list of some of the more well-known NP complete problems is listed on this Wikipedia page)
What makes this particular result even more interesting is the fact that NP complete problems are reducible to each and every other NP complete problem. In other words, a method that can quickly and efficiently solve one NP complete problem can be used to solve every other NP complete problem quickly and efficiently as well. In a sense, all NP complete problems are inherently the same problem. Thus, creating a bacterial solution to solving one NP complete problem provides a potential path to solve every other NP complete problem, proving that synthetic biology can do a whole lot more than just simple biological circuits, they may even provide an interesting tool to solve some of the most challenging computational problems.
So perhaps the judgment day the Terminator series envisioned won’t originate from Cyberdyne, but from a synthetic biology lab experimenting with some “smart” bacteria. I’ll be keeping my eyes open.
