close this bookVolume 5: No. 15
View the documentFunding news
View the documentAward competitions
View the documentScientific infrastructure
View the documentSoftware development
View the documentMolecular computation
View the documentJob opportunities
View the documentJournal calls
View the documentJournals and e-journals
View the documentSoftware marketing
View the documentComputists' news

Chuck Morefield has contributed the following notes:

According to Donald Beaver (Penn State) the first serious recognition within the CS community that DNA-based computing might be feasible (via site-directed mutagenesis) occurred at Asiacrypt 1994. An 11/94 article in Science by USC's Leonard Adleman (the 'A' in RSA cryptography) described a molecular calculator for a Hamiltonian/TSP problem through recombination of DNA fragments. (I believe all internode distances were of the same length. -- KIL.)

Richard Lipton (Princeton) generalized Adleman's paradigm to include a larger class of NP-complete problems, as described on . A commentary and extension is on . [Claus Rick , comp.theory, 4/19/95.]

Adleman's calculator destroys itself during the course of its computations, so it is not a universal computing machine. Another problem was raised in the article "On the Weight of Computations" for the Bulletin of the European Association for Theoretical Computer Science (55, 2/95). Juris Hartmanis (Cornell) argues that an Adleman DNA computer for a 200-node Hamiltonian path problem would weigh more than the earth! [Ibid.]

Alternative paradigms have been proposed. Donald Beaver describes a molecular system that can act as a universal computational device. His Turing machine can embedded in a single DNA molecule, and can be linked in parallel forms. There is speculation that exponential parallelism could solve problems with complexity greater than NP in polynomial time.

Robert Birge (Syracuse) reports in Scientific American (3/95) that proteins can be used for neural-style pattern recognition and for large memories. The field continues to move very fast.