RNA Computer

TBM writes "Here is an article on the use of RNA to do some computational tasks. It was given the problem of placing knights on a 3x3 board such that no knight could kill another and found 43 correct solutions and one incorrect one out of a possible 512. They say it works in parallel and so trillions of parallel computations are possible... So when can I start using my RNA for RC-5?"

Comments

DNA/RNA computing still limited...

[gatzke]

There are some great advantages in DNA/RNA computing, but some limitations too. From some of the stuff I have seen, you can pose a problem chemically, then use random sequences of DNA to see if any solutions are found. This effectively lets billions and trillions of potential answers be attempted in parallel. This complete ennumeration scheme is better than using computers, but still limited.

If you talk about searching a space of n binary variables, there will be 2^n potential solutions. Say n=1000, 2^n~=1e300. If I remember the number of molecules in a mole of something is around 3e23. You can get a bigger pot of random DNA (more moles) but this is still a limitation for DNA computing as far as I know right now.

For big traveling salesman (Non-Polynomial) problems, the size can easily reach n=1,000,000. DNA computing is cool, but only useful in some specific applications.

And while we are at it, extending the current solution algorthms to parallel computing versions doesn't always help. Doubling the number of processors (or doubling the speed of each processor) in the best case only helps you solve one more binary variable.. 2^n=>2^(n+1)

More info

[FigWig]

This type of combinatorial bio-computing was first done in 1994 by Adelman. He solved a Hamiltonian path problem by evolving a solution in DNA.

More info about bio-computing in general here.

more info

[nels_tomlinson]

I submitted this late last week, when I found it mentioned on Ars Technica. I guess that sounds like sour grapes because it is. Anyway, here are some additional links:

First, the principle researcher's lab page. FRS 120 looks particularly interesting. The course outline has lots of neat links.

http://www.princeton.edu/~lfl/

Then her homepage, with information on her work, in this area and others:

http://www.santafe.edu/sfi/research/fellowatlarg e/landweber.html

and a page with links to a LOT of papers, in this area and others:

http://www.princeton.edu/~lfl/research.html

Finally, here is the particular paper which the eetimes article is based on (I think):

ftp://rnaworld.princeton.edu/pub/export/KnightsP NAS.pdf

I don't do html, so just cut'em and paste'em.
Nels

Scalability

[Dr. Zowie]

All of these RNA computational studies (there have been several to date) highlight the fact that individual RNA "computers" are extremely tiny and cheap, so that massively parallelizable operations can be accomplished quickly.

It's important to remember that, while RNA computation can accomplish amazing things through humongously parallel arrays of specialized molecules, the computation is still subject to the limits of (for example) NP-completeness. In this case, the "hard part" appears (you have to read between the lines) to have been the enumeration of all 9-bit numbers in coded RNA. This part of the problem scales exponentially, even if the actual final step is so massively parallel that it runs in constant time.

When I was knee-high to a lisp interpreter, I remember hearing about different sort algorithms that ran faster than quicksort. My favorite was the spaghetti sort, which runs in linear time for moderately sized numbers and involves slamming a bundle of raw spaghetti into a table (the linear part comes from cutting the strands to lengths proportional to your numbers). The problem is that, by the time you scale the spaghetti sort up enough to beat quicksort running on a Cray, you find that you have to slam 10^23 strands of spaghetti into the face of the Moon -- and then you end up having to spend something like at least root(n) time figuring out which one is the longest, so quicksort wins in the end (if you break the sort up into many spag sorts you end up with a hybrid solution that runs in n log(n) time).

I think that the RNA sort is like this: for small numbers it scales OK, but there are hidden costs to each operation that spoil the scalability later.