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?"

Key Cracking

If someone can come up with a enzymatic encryption algorithm, you could test trillions of keys at once.

The question is - does the time to compute the RNA solution scale with the size of the problem the same way a traditional computational solution does?

-josh

time, space and the scalability of wet chemistry

Firs, a minor point: I believe that the problem that Adelman solved was a seven node Hamiltonian path problem. This is like the TSP, but formulated as a decision problem: given a directed graph, is there *any* path from point A to point B that visits all the nodes once.

Not to detract from Adelman's work---it was a very pretty algorithm, and it did prove the principle that this COULD be done---but it didn't really give a practicle way of solving the problem. All it did was spread the computations out over a large number of processors.

Think about it this way: Of course I can solve an NP hard algorithm in polynomial time---just give me an exponential number of processors.

What Adelman's algorithm did, and what it looks like these Princeton researchers did, was create every possible solution as a nucleotide (RNA or DNA) strand, and then select out the correct ones. Although I haven't thought about the problem that the Princeton researchers have tackled, with the Ham-path problem, there are potentially n^n possible sequences *of the right length* that have to be searched. When the sequences are made, however, many others will be made as well. That's quite a few if the problem gets to be of any size at all.

As the size gets up to anything "reasonably hard" the amount a fluid required to simply keep the DNA/RNA in solution will get prohibitively large, and now we have to be able to do chemistry on them. These basic operations that are typically done on DNA/RNA, like PCR, gel electrophoresis, and probing, are usually done on *microliters* of solution, not megaliters. This is why the only things researchers have been able to do so far is these "toy" examples.

My feeling is that the problem with all of this work is that all of the algorithms (that I've seen) rely on the same basic scheme: encode all the solutions and then in a massively parallel way fish out the correct one. What's probably going to be needed to yield anything practicle is for someone to figure out a way for the nucleotide to be an active part of the computation, rather than a passive encoding device. This is most likely going to take a while, since the only operations we can do to these molecules are the ones we can FIND proteins to do for us. Once protein engineering gets better, we may be able to do more.

A question I have: Since this model of computation is not super-Turing, why are all of these researchers trying to tackle NP-complete problems? They'll run into the same exponential blowups that conventional machines do. It seems that it might be more productive to look into ways to harness the vast potential parallelism to handle large instances of P-time algorithms in a more efficient manner. Just a thought.

What am I missing?

I could be way off here, so help me out if ya can, or ignore this blithering idiot.
According to the article "Strands of RNA containing 1,024 base pairs were encoded with every possible solution to a specific chess problem" and "Molecules can store more information than silicon chips, and this was the largest problem ever solved by a molecular computer"
It sounds like it was given the answers, so wouldn't this be more useful as a storage medium?
The article seems to indicate it being as a computer. Am I missing something about computing here?

RC5 ....

So when can I start using my RNA for RC-5?

Well as I see it you need to do this:

• create a solution containing R/DNA encoding all possible keys - 2**56 molecules given that 1 Mole is ~6x10**23 (~6*2**76) molecules we're going to need 2**-20 moles of solution - probably you need a lot of reduncdancy so maybe 2**-10 moles - each base pair is going to have a molecular weight of say 600 and we need 56 of them to encode the key - plus we'll probably need a working space of 56*32*1000 base pairs (a number pulled from the top of my head) plus an answer of 56 base pairs - this gives a weight of ~1kg (plus it's solution say 2kg, added RNA etc to actually perform the functions are going to be many kg extra) quite reasonable - a 64-bit key with more rounds is going to require something that's in the tonne range :-)
• come up with a process where the N rounds of key expansion required for rc56 occur by somehow matching RNA to an existing strand of R/DNA and extending it with the intermediate result (normally stored in a temp location for RC5) - this is the hard part since the operations involve addition I have no idea how these get done in a test tube
• continue applying these operations growing the molecules untill they're the length that corresponds to the required number of rounds
• introduce another RNA that matches molecules of the required length with a tag on the end that corresponds to the known text we're looking for - this molecule detatches the original key and raises it's hand ("here we are!")
• you detect all the molecules that passed and run their found keys against the algorithm (the current rc5 algorithm has a small number of have false positives - a chemical reaction is probably going to have a number of ba positives too)

well there you are - time to go out and buy that test-tube (and nano-assembler) .... or for the 64-bit keys maybe an unused resovoir ....

DNA/RNA computing still limited...

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

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

More info about bio-computing in general here. [mitre.org]

more info

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

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.