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)
http://ieeexplore.ieee.org/xpl/freeabs_all.jsp?arnumber=592304

Using DNA to solve NP-complete problems, Science, 1995
http://www.cs.princeton.edu/~dabo/bio-comp/satgen.ps

Speeding up computations via molecular biology, university draft
ftp://ftp.cs.princeton.edu/pub/people/rjl/bio.ps

Molecular computation of solutions to combinatorial problems, Science, 1994
http://www.usc.edu/dept/molecular-science/papers/adleman-science.pdf

Solution of a 20-Variable 3-SAT Problem on a DNA Computer, Science, 2002
http://www.sciencemag.org/cgi/content/abstract/1069528v1

DNA computing using single-molecule hybridization detection, Nucleic Acids Research 2004
http://nar.oxfordjournals.org/cgi/content/abstract/32/17/4962

Demonstration of a universal surface DNA computer, Nucleic Acids Research, 2004
http://nar.oxfordjournals.org/cgi/content/abstract/32/10/3115

DNA molecule provides a computing machine with both data and fuel, PNAS, 2003
http://www.pnas.org/content/100/5/2191.abstract

Stochastic computing with biomolecular automata, PNAS, 2004
http://www.pnas.org/content/101/27/9960.abstract

Good Encodings for DNA-based Solutions to Combinatorial Problems
http://books.google.com/books?id=2Bv8zVzxzYIC&pg=PA247&lpg=PA247&dq=Good...

Molecular computation: RNA solutions to chess problems, PNAS, 2000
http://www.pnas.org/content/97/4/1385.full

An autonomous molecular computer for logical control of gene expression, Nature, 2004
www.weizmann.ac.il/mathusers/udi/papers/automoleculcomp_nat04.pdf

No comments: