Since my earlier post today dealt with the issue of “intelligent” machines becoming more like living organisms, and humans in particular, it’s perhaps appropriate that this one turns it around, to discuss the use of living organisms as computers. In a paper that is to appear in the Journal of Biological Engineering, a group of researchers has reported on an experiment in which they genetically engineered E. coli bacteria to solve a particular mathematical problem, the Hamiltonian Path Problem. (This problem is a special case of the Traveling Salesman problem; it essentially adds the restriction that travel is only possible between adjacent cities. The problem is of considerable interest in computer science because it is an NP-complete problem.)
The problem that was actually solved in the experiment is not particularly interesting in its own right, because it is quite small. But the steps that were taken in the process are interesting, in the sense that they illustrate some of the things that are possible in the world of genetic engineering.
In the software world, genetic algorithms use techniques motivated by observations from evolutionary biology to solve search and optimization problems. The algorithms are essentially heuristics that are intended to arrive at a solution in much the same way that biological evolution leads to the characteristics of a species. When implemented in software, these algorithms have two fundamental components:
- A representation encoding all possible solutions, corresponding to a biological gene
- A fitness function, that determines the evolutionary success of a solution, paralleling the idea of differential reproductive success in the biological world.
From its starting point, the algorithm produces successive “generations” of solutions, with the most fit solutions in each generation selected to “reproduce”, mimicking the process of natural selection.
What the experimenters here have done is to implement this sort of approach using an actual organism. They encode the relevant problem data as DNA sequences within the bacteria. These sequences are then “shuffled” randomly as the bacteria reproduce. Of course, there has to be some way of measuring the “solution” that has been arrived at. In the three-node problem studied, this was done (quite cleverly, I think) by encoding the data in genes that produced red and green fluorescent pigments, such that a Hamiltonian path solution would contain both pigments, and fluoresce yellow. The solutions were later verified by sequencing the DNA. One can think of this as a very large parallel computer, with literally billions of small processors.
This experiment was really a proof-of-concept project. As I noted earlier, the specific problem that was solved is very small. It isn’t clear that there is a really effective way to scale this approach to large problems, and it is the difficulty of solving large problems that makes the NP-complete set interesting in the first place. But it is a fascinating demonstration of some of the things that can be done with biological engineering, and perhaps should remind us again that the boundary between our machines and living organisms may not be quite as well defined as we think.