Slashdot Mirror
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?"
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)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)
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.
Scuttlemonkey is a troll
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:
g e/landweber.html
P NAS.pdf
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/fellowatlar
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/Knights
I don't do html, so just cut'em and paste'em.
Nels
See what I've been reading.
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.