Bench Press

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.

(Image Credit)

Thankfully food scares like the Salmonella contamination of peanut products from the Peanut Corporation of America are fairly rare in the US the health risk posed by contaminated food and water must be taken extremely seriously and effective means to test and certify food and water safety are of the utmost importance. Despite this even with modern advances some tests can currently take days to verify the safety of food and water samples.

This lag time can ultimately prove disastrous in certain scenarios. For example, the rural
community of Walkerton, Canada experienced E. coli contamination in May, 2000 resulting in seven deaths and hundreds sickened by the contaminated water. Therefore, testing of critical supplies like water ought to be as near real time as possible in order to minimize potential harm.

This brings me to research being conducted by Dr. Shacham-Diamand’s group at Tel Aviv University. Speaking about the dangers of water poisoning Dr. Shacham-Diamand warns “You don’t want hospitals to be sensors for toxicity. That’s too late”. This desire to provide a more rapid and effective testing apparatus propelled Shacham-Diamand’s group to design a “lab on a chip” capable of accurately detecting a wide range of contaminants in water within minutes of simply adding water to the chip.

This “lab on a chip” is built upon genetically engineered E. coli in reaction chambers on a chip as seen in the diagram below (Subfigures A + B). When exposed to nL samples the E. coli luminesce in the presence toxins which are then detected and quantified by the signal strength. Initial experiments done with E. coli containing the lac promoter (activated by IPTG) fused to lux-CDABE genes of V. Fischeri proved the feasibility of utilizing whole cell bacteria in order to generate luminescent signal that could be detected utilizing a solid-state photodetector¹. Other experiments conducted by Dr. Shacham-Diamond’s group have proved the feasibility of detecting a variety of contaminants with genetically engineered E. coli².

Currently, Dr. Shacham-Diamand’s group has worked on further modeling of their chip design (above Subfigure C) in order to optimize the detection of the luminescent signal. The flexibility generated by using genetically engineered E. coli has Dr. Shacham-Diamand’s group looking into alternative applications of their chip such as screening potential cancer drugs.

In the end innovative nanoscale devices like this “lab on a chip” and the DNA-coated nanowire device we blogged about previously show tremendous promise for improving our ability to detect and diagnose a wide range of problems be they contaminated water or diseases.

(Sources: Tel Aviv University , 1 – Towards toxicity detection using a lab-on-chip based on the integration of MOEMS and whole-cell sensors , 2 - Novel Integrated Electrochemical Nano-Biochip for Toxicity Detection in Water)