On the power of molecular computing

by Forrest Sheng Bao http://fsbao.net

Eric You Hsu, Stephen Gang Wu and I spent few hours tonight to go thru these papers about DNA computing. You can see the property of DNA molecules to do some fancy computing stuff. Looks like DNA computing has some potential on logical constraint problems, many of which are NP-complete programs. Thus, they are tough to computer scientists.

Looks like they are all focus on SAT problems. We are look forward to some better ideas.

Few weeks ago at MIT, when I was at iGem 2008, I saw a fancy research conducted by a joint group in Missouri. They implemented the hash algorithm by controlling the expression of fluorescent genes. I talked to them and wanna do more investigation on this topic.

Prolog approach to DNA computing, IEEE Conference on Evolution Computer, 1997 (CEC'97)

Using DNA to solve NP-complete problems, Science, 1995

Speeding up computations via molecular biology, university draft

Molecular computation of solutions to combinatorial problems, Science, 1994

Solution of a 20-Variable 3-SAT Problem on a DNA Computer, Science, 2002

DNA computing using single-molecule hybridization detection, Nucleic Acids Research 2004

Demonstration of a universal surface DNA computer, Nucleic Acids Research, 2004

DNA molecule provides a computing machine with both data and fuel, PNAS, 2003

Stochastic computing with biomolecular automata, PNAS, 2004

Good Encodings for DNA-based Solutions to Combinatorial Problems

Molecular computation: RNA solutions to chess problems, PNAS, 2000

An autonomous molecular computer for logical control of gene expression, Nature, 2004

No comments: