NP-Problems and molecular computation

[ryokan]

Ten years ago (Science 1994;266:1021-4), Adelman built the first DNA based computer to solve the so-called Hamilton Path problem for seven nodes. SAT problems were solved with similar approaches by Lipton (Science 1995;268:542-5), with a DNA-based algorithm and Faulhammer (PNAS 2000;97.1385-9) who used a RNA-based algorithm .

The initial excitement following these reports was constrained by major limitations: mainly, the need of a massive amount of DNA and the exponential increase in the chance of error to solve larger-scale problems.

I pose the following questions:
Do you think that molecular computation is promising?
Since its first use, DNA computation had a seemingly slow development. Why? I think that besides the intrinsic limitations, this field, by interdisciplinary, is less attractive than other "hot" topics in Biology.

 

[selfAdjoint]

I pose the following questions:
Do you think that molecular computation is promising?
Since its first use, DNA computation had a seemingly slow development. Why? I think that besides the intrinsic limitations, this field, by interdisciplinary, is less attractive than other "hot" topics in Biology.

I think molecular computation is as promising as any radically new technique now on the menu, in particular I believe it will pay off quicker than quantum computation.

My experimence is that it is the nature of computational methods to have a brilliant beginning and then stall, or appear to. Look at expert systems and neural computing. What have they done for us lately? Actually in fact quite a bit, but it doesn't make the papers because it's no longer a breakthrough.

 

[ryokan]

in particular I believe it will pay off quicker than quantum computation.

If so, why?

 

[selfAdjoint]

Because quantum computation still requires new, as yet unkown, technology to reach its potential, but nanophysics can build chips with technology already in use.

 

[ryokan]

Because quantum computation still requires new, as yet unkown, technology to reach its potential, but nanophysics can build chips with technology already in use.

I partially agree.

Effectively, there is now technology that allows to use DNA as a tool for diagnostic purposes in form of microarrays or “biochips”.

There are also solid lines of research on the use of DNA to construct nanomachines.

And there are very interesting findings on a “cellular computer” that after diagnose a cancer cell based in its specific RNA levels, would release single-stranded DNA molecules to interfere with such RNA, causing the self-destruction of the cell.

But as far as I know, the molecular approach to solve some NP problems was based only in molecular computing in liquid phase at a laboratory – scale . And it is here where the intrinsic limitations of DNA computing (due to the error-prone enzymatic activities and the string length and amount of DNA required) seems incapable to surpass the conventional electronic computers to solve NP problems.

So, It would be possible that the technology required to quantum computing be developped before the overcome of the limitations inherents to DNA computing to solve NP problems.

 

[ryokan]

Computation is more easy inside than outside

Problems with DNA computation in vitro contrast with the facilities to computation that cells have.

I think that a good example of NP-problem that cells solve constantly is the correct folding of their proteins (Levinthal's paradox).

It is possible that the actual methods of "molecular computation" using DNA, with their inherent limitations, must be replaced by a possible form of "cellular computation" widely focused on NP problems with isomorphism to the problems that cells solve daily.