Sunday, July 26, 2009

Bacteria solve NP-Complete problem.

In an interesting cross between genetics, biology and computer science, some clever lads attack The Hamiltonian Path Problem using bacteria.  From the abstract:

We programmed bacteria with a genetic circuit that enables them to evaluate all possible paths in a directed graph in order to find a Hamiltonian path. We encoded a three node directed graph as DNA segments that were autonomously shuffled randomly inside bacteria by a Hin/hixC recombination system we previously adapted from Salmonella typhimurium for use in Escherichia coli.


Really gawd awful Guardian article about it here.  Wiki page about the Hamiltonian Path problem here.

NP-Complete problems are an entire range of important, practical problems in life that normal (read serial) computers suck at.  Things like laminar flow, network optimization, scheduling etc.  This approach is quite novel, so it will be fun to see how they make out.  Imagine, solving the traveling salesman problem in a petri dish.

h/t Slashdot.

The Bacterialy Computational Phantom

No comments: