E. coli bacteria Solves Complex Computer Problems

[Guest Monthra]

A research team made up of four faculty members and 15 undergraduate students from the biology and mathematics departments at Missouri Western State University in Missouri and Davidson College in North Carolina, USA engineered the DNA of Escherichia coli bacteria, creating bacterial computers capable of solving a classic mathematical problem known as the Hamiltonian Path Problem.

 

A Hamiltonian path is a path in an undirected graph which visits each vertex exactly once. A Hamiltonian cycle (or Hamiltonian circuit) is a cycle in an undirected graph which visits each vertex exactly once and also returns to the starting vertex. Determining whether such paths and cycles exist in graphs is the Hamiltonian path problem which is NP-complete.

 

Hamiltonian paths and cycles are named after William Rowan Hamilton who invented the Icosian Game, now also known as Hamilton's puzzle, which involves finding a Hamiltonian cycle in the edge graph of the dodecahedron. Hamilton solved this problem using the Icosian Calculus, an algebraic structure based on roots of unity with many similarities to the quaternions (also invented by Hamilton). Unfortunately, this solution does not generalize to arbitrary graphs.

 

Escherichia coli (commonly named E. coli), is a Gram negative bacterium that is commonly found in the lower intestine of warm-blooded organisms (endotherms).

 

http://www.jbioleng.org/content/3/1/11/abstract