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?"
I'm at an end here.... Could someone please explain how genetic computing works?
What I mean is: modern computing relies on the fact that electrical signals (voltages and currents) can be controlled to mean something.
What is the basic assumption in genetic computing? That compounds will deterministically combine and react with another substance? How does a trillion DNA strands get reduced to one by just sitting there?
I haven't seen any good explanations about genetic computing in terms regular programmers can understand...
You should never take life too seriously - You'll never get out of it alive.
Wouldn't a valid test of data crunching be more along the lines of actually solving the problem, not just figuring out which answer from those provided were correct?
There is a whole class of problems which can only be solved (as far as we know) by trying all possable solutions until one works. That's what was done in the test tube.
Imagine the possabilities for database systems! A vat contains all of the records happily replicating. Pull out a sample, add the query strands and react away. Soon, the sample will contain all records matching the query.
That's what I said to myself while reading this article. Science is going FAST! I would'nt have believed to have this made possible in at least 10 years, and here we have it!
The implications are enormous. On top of that, mechanized DNA analysis tool are becoming almost mainstream, and it's not too far before they will cost less than a big computer.
What next? That's probably the biggest question. What about having a slasdot interview of the guys who did this? That's HACKING dudes; think about it, it's comparable to the first dude who ever solved a chess problem on an electronic computer. Was that, what, 50 years ago? Think about the application we will have in that time frame.
Shit!!!
Yes. It's the same problem, in fact. There is a general consensus among both biologists and computer scientists that this sort of molecular computing will never become practical due to the amount of RNA or DNA needed. Earlier in her career Laura Landwebber did brilliant work on RNA editing -- I really don't understand why she has decided to work on something that's clearly a dead end.
Additionally, one should remember that even ignoring the practical limits on the technology these molecular "computers" really offer no theoretical benefits over any other Turing-equivilent computer besides being massively parallel. They still wouldn't be able to solve NP-hard problems.
Given that the paper said that this was a destructive algorithm,
I would say that you could win one game.
Too bad you wouldn't be around to enjoy your victory.
ebw
and they'll be coding AI in RNA. So then you're RNA will become self aware and travel back in time to kill your mother.
;)
Dooms day is on the way baby.
Seriously though, this is pretty spiffy stuff. Seems like they are going about it the wrong way, however. Making strands with all of the possible solutions, then eliminating the incorrect doesn't seem like it would ever lend itself to general purpose computing. Seems like it would be better to find a way to produce only correct solutions.
Anybody have any more info on this stuff?
This sig is false.
So does anyone have an idea about how this will scale in terms of the volume and mass of the reactants required to solve problems that conventional computers are struggling with? IIRC the last estimates for large-scale Hamiltonian network problems that were done after the Adleman stuff came out indicated that there would have to be more DNA mass than the earth to solve problems involving more than 20 nodes. Is there not a similar problem here?
Okay, this is a cool concept and all, but I bet most of ya'll dont realize quite HOW cool.
You see, we have in cognitive science the idea of 'pigeonholeing'; that if I build houses all day, I see everything in terms of building houses (which is not entirely true, when was the last time you used duct tape on a duct).
So if this application was thought up by MOLECULAR BIOLOGISTS AND CHEMISTS, what happens when some good hardcore Computer Scientists and Hackers get their minds into the functions of the system?
I think the technology is much further in capability along than we realize, but we dont fully understand how to apply it, so we are maybe not as impressed as we should be.
-- Crutcher --
#include <disclaimer.h>
Very nice, but what about mutation? A RNA strand goes crazy and we end up with a borgified version of some creature. crudpuppy or dustpuppy anyone?
:)
Moderators, please note this is a slightly funny look at a possible problem. I know that *puppy is fiction, but then, the idea just sounds good.
I can throw myself at the ground, and miss.
Regarding the 1 incorrect answer:
"We just had a bit of bad luck -- or more literally two bits, since it was two single-point errors in a row that foiled our algorithm," Landweber said. "Two errors in a row are exceedingly rare and shouldn't become a problem when we scale up."
Better catch those "exceedingly rare" errors now else we'll have a DNA Y2K before you know it.
Seriously though, it solved the traveling salesman problem in a week? If this stuff is already in action, we should be testing the limits of computability, like finding the most approximate value of pi, calculating patterns in the stock market, and not losing any more damn Mars Polar Landers.
This DNA computing business is also a good way to teach people about how computers actually work. Most, I'm sure, think of a computer as just boxes of binary, not why 1 and 0 are used (you could use 52 and zebra instead) and why silicon was used (better than rubber bands, I'll tell you that) and why DNA is a much better solution.
Can't wait until this stuff is desktop able, and if you predict it will take 50 years, just remember what Gates thought about HD space in '83...
------------
"Okay, who taught the cat how to type ctrl alt delete?"
I've been reading "DNA Computing by Paun, Rozenberg, Salomaa" published by Springer. It goes into great detail on how one might implement a variety of algorithms on DNA and RNA computing. Essential reading! One chapter discusses the practicalities of decrypting DES and there's a good section on solving the well known SAT problem that computer scientists should know well. It gets quite heavy later on but early on it gives formal descriptions of the various DNA computing steps that are available so you can easily go off and start designing algorithms yourself.
-- SIGFPE
Imagine a day when we build a computer that is able to create it's own RNA strands to solve a problem, instead of having us provide it with them. With the advances that are being made in artificial intelligence, we may just be able to take the next step forward and create living intelligence. After all, couldn't we program this RNA computer to determine the best way to continue running? If it's able to build it's own RNA to solve the problem, it may be able to basically create life on its own. The day may come when a computer virus is really no different than any other sort of virus we encounter.
Hmm, you could use a virus as a loader. Talk about world domination!
The strands of RNA are said to physically contain all possible combinations. This seems to somewhat limit the possible size of problems.
--
Play Match-It.
But then there is the issue of replication. Mass replication of the RNA would involve enzymes that are quite messy; 1 error per 20000 base-pairs. The term of burning software would evolve into replicating strands! Oh, what fun!
This is probably quite premature, but the possiblities of a molecular computer running on genetic code could also be the makings of a half-machine/half-genetic semi-artificial intelligence. Neat! What do you think?
All this is very delicately self-regulated. It's digital data processing, though not quite as we know it.
I think the best way of understanding the genome is as a computer program that has been continuously maintained and enhanced for 4,000,000,000 years. Each baby is a new beta.
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
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.
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?
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.