Background  

For years, the fundamental information-processing components of computers have been getting smaller and smaller. But traditional semiconductor devices start to become significantly more difficult and expensive to fabricate reliably as their dimensions fall below the wavelengths of the more easily-manipulated forms of light [Stix-95]. This has contributed to a recent groundswell of interest concerning possible alternative computation technologies that would circumvent the size plateau that semiconductors might soon reach. As foreseen by Feynman [Feynman-60] and promoted by Drexler [Nanosystems], an obvious next plateau would involve computational components consisting of individual molecules. There is already an active literature on the subject in (for example) the journals Nanotechnology and Journal of Molecular Electronics, but until recently, most projects remained at the level of molecular wires (e.g., [Wagner-Lindsey-94]) or switches (e.g., [Bradley-93]) and seemed decades away from putting the parts together to carry out extended computations.

But now, a new approach to molecular computing appears to offer the hope of more immediate results. That approach is to take the existing complex molecules found in living systems, which are readily obtainable, and figure out how to take advantage of their inherent information-processing capabilities to perform desired computational tasks. For example, Birge [Birge-95] has investigated using the optically triggered state transitions of the protein bacteriorhodopsin to store bits of information. Lahoz-Beltra and colleagues [LahozBeltra-et-al-93] have investigated how arrays of tubulin proteins inside living cells seem to implement a cellular (2) automaton capable of transmitting information and performing Boolean logic. Conrad [Conrad-92], Aoki and others [Aoki-et-al-92] discuss using the spontaneous interlocking of proteins in solution to perform logical operations.

Proteins are not the only large biomolecules of interest: other researchers have investigated the information-processing properties of DNA. Many years ago Bennett ([Bennett-73],[Bennett-82]) showed how the mechanisms of DNA replication, transcription and translation can be viewed as highly energy-efficient molecular machines. Tom Schneider [Schneider-93] has investigated the theory of the thermodynamics of computation in systems where DNA strands or proteins in solution recognize and bind with certain DNA sequences. Heller and Tullis are designing simple self-assembling photonic devices made of DNA [Heller-Tullis-91]. And finally, most recently, Adleman ([Adleman-94],[Adleman-95]), Lipton [Lipton-94], Beaver ([Beaver-95],[Beaver-94]) and others have investigated how the interactions between DNA molecules in solution can be used to generate and test many possible solutions to NP-hard problems in parallel.

So far, Adleman has been the only one to report an actual DNA computation. In his experiments [Adleman-94], Adleman used chemical reactions involving DNA molecules to compute the solution to a small instance of the directed Hamiltonian path problem (henceforth DIR-HAMPATH). In his technique, many different species (chemically distict types) of molecules representing different possible solutions to the problem were generated and tested chemically, in parallel, suggesting the possibility that a scaled-up version might be capable of such enormous parallelism so as to afford a significant speedup over existing supercomputers on these types of problems. Unfortunately, Adleman's technique, as described, was capable of directly solving only DIR-HAMPATH problems, with other problems in NP being solvable only indirectly, by reduction. More useful would be a DNA system capable of performing arbitrary computations, while still taking advantage of the inherent parallelism of the chemistry.

Already, several different universal DNA computers have been proposed, by Beaver, by Smith and Schweitzer, and others that remain unpublished. In addition, years ago Denninghoff and Gatterdam showed that a certain abstract model of DNA recombination was Turing complete. These alternative techniques will be analyzed in detail and compared with CMM later, in the thesis itself. For now, the important point is just that the other approaches are all unsatisfactory in one way or another; either they suffer from a fatal bug that would prevent correct operation, or else they require many complex, labor-intensive processing steps, in which mixtures are repeatedly separated and recombined, making them difficult or infeasible to carry out in practice. In contrast, CMM was designed from the beginning to be extremely simple to carry out in the lab: once a computation is set up, executing it involves only the automated operation of a standard piece of molecular biology lab equipment called a PCR machine, with only occasional, simple interventions.

There is another important criteria which played a part in the conception of CMM: biological plausibility. Computing with biological molecules is a subject of scientific interest not just because it is another way to do computing, but because it is a way to do computing that might, in some form, conceivably take place in actual living organisms, or be made to do so. Cells are already known to perform a number of complex computational operations (see [Smith-Schweitzer-95]), and certainly the construction of a complete organism from a single cell is a formidable computational task. But the full range of computational mechanisms that operate in vivo is unknown. Therefore, any new technique for molecular computation, if biologically plausible, is interesting because if it turns out to take place in cells, it might advance our understanding of some aspect of biology. Additionally, if a computational technique does not already take place in cells but might be made to do so, there may conceivably exist a potential for applications in molecular medicine. CMM, as will be explained later, has a certain degree of biological plausibility that other proposed DNA computation techniques lack, due to their many labor-intensive steps and other factors.

Now, without further ado, the next chapter will describe how CMM works and the results of our analyses of it to date.

Footnotes

 

2.

Cellular as in "made of a grid of logical cells," not cellular as in "involving living cells"