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?"
Generally, shouting "Moderate this up" is about as useful as "First Post". Some of the moderators are actually able to decide on that for themselves.
Yes, but if it determines that eliminating human life is the best way to continue running, what'll we do?
So I kicked back, stared at the ceiling, and counted the solutions in my head. I came up with 94 (I guess I'm a good counter!). A little toy C program I wrote came up with 94 solutions as well.
So color me unimpressed with the accuracy of their computational results. They lost more than half of the solution set!
Also it seems the RNA strands do not interact with each other at all: they record parallel results of independent computations. That limits them to embarrassingly parallel problems. We already know how to build really good hardware for those.
where do I plug in my 21" sony?
Whoa, put the guns down and chill out. It was an innocent question. Everyone has a different life. We can't all sit at home and read up on this stuff day in and out. We don't all have the same life style.. try to understand that before you go off on someone.
-Take a deep breath, and call me in the morning
The one week number is completely meaningless. The actual calculation to solve the problem probably took under a second. The rest of the time was spent in prep and removing all the incorrect solutions BY HAND (not automated). Prep and purification could be speeded up by at least an order of magnitude. -Ozborn
Stuff like that is in almost every article Slashdot posts. The MS conspiracy's always crack me up. People think the PS2 will be God only because the development kit runs Linux, and every single new technology has to be imagined as being in a beowulf culster. It's quite predictiable actually.
6*2**76 = ~4.5*10**23
1 mole = ~6.02*10**23
2**79 = ~6.04*10**23 = less than 1% error
Wait... if we continue up this scale... the whole earth is one giant supercomputer and it looks like the hitchhiker's guide to the galaxy was right!
-TBM
... soon we can play chess against our sperms.... unless the 23 chromosomes instead of 46 would mess it up??
Isn't technology wonderful?
--ac
that's my first time ever to hear 'parallel' used as an epithet. but you'll see. one day you're going to need a parallel problem, but they will all turn their backs on you, and all because of one thoughtless slashdot post. god you make me sick!
Just do click here for hot hot grrls!
when was the last time you talked to a parallel problem. did you take one out for coffee today? did you have a nasty breakup with one last week?
and do you even understand what "embarrasingly parallel" means? have you been anywhere *near* even moderately current research? do you know how to use your computer for more than web browsing?
good luck getting a clue, and I'll be watching for you in the Darwin Awards.
You don't get it. The RNA has to store all solutions, so it's more in the order of 3*10^9 solutions, not 2^(3*10^9).
Meanwhile, for the original poster: "embarrassingly parallel" means a problem that is so parallel that it's very easy to split up among multiple processors: so easy that it would be embarrassing to a real hacker to work up a sweat doing it. Something like searching for an RC5 key by brute force is embarrassingly parallel. But modelling the weather (for example) is not, because the CPU's modelling individual weather cells have to do significant communication with each other.
>I submitted this late last week, when I found it mentioned on Ars Technica. I guess that sounds like sour grapes because it is.
>I don't do html, so just cut'em and paste'em.
Perhaps this I'm-too-sexy-to-create-links attitude might have something to do with your story submissions being rejected?
One: No. The experiment involved fabricating enzymes to identify certain RNA sequences (those whose encodings happened to match the solution to a certain problem). Just RNA and enzymes -- not even complete cells, much less neurons.
Two: Well, things get a little tricky. In its current form, you have to create every possible solution before you can solve. And since an infinite set of cryptographic keys are available, you have a problem. This procedure would have cryptographic relevance if (a) it could be modified such that the enzymes generated and tested solutions automatically and (b) speed were greatly improved (which may be as simple as using a wider -- more parallel -- test tube).
This idea works well on embarassingly parallel problems where the algorithm is simple and the keyspace is large -- but is there any chance that it could be applied to a wider class of problems?
Furthermore, solutions to small problem set sizes are not that interesting, as they can be obtained using classical methods. Solutions to large problem sizes are what you would want to compute using a {D,R}NA computer; but this may require impractical physical resources.
--ac
http://nhse.cs.rice.ed u/CRPC/newsletters/jan93/news.tsp.html
--ac
this problem has the complexity of the following thing: find a string of eight 1's and 0's that dosen't have two consective 1's. but it's oh so much more impressive when couched as a chess problem.
i know my subject is so negative. well, actually, i think this is terifically cool. it's cool because it gives some insight into how our bodies can work. that is, it extends the 'computer' metaphor, and that's fun.
but get real. it's never gonna be used as a computer by anyone.
You missed the finale of the article... it's a destructive algorythm. Would you want to repurchase your "storage medium" every time it was accessed for a "bit" of information?
"Couldn't we program this RNA computer to determine the best way to continue running?"
We could, if we knew how to formalize the definition of good/better/best. Thusfar, this part of AI still falls squarely on human shoulders. We know how to use AB-trees, genetic algorithms, et al, to make computers seek out "better" or "the best" solutions to a problem, but only as long as we have a function which returns a quantified measure of how "good" a thing is, or how much "better" one thing is than another. For specific situations, this is pretty easy -- "good" is the inverse of the thermometer's output's difference from 70 degrees, for instance, or "good" is getting five in a row before the opponent could possibly do the same (for gomoku). Defining "good" in the general sense (as in "make the computer run better") is much more difficult. If you came up with a precise definition, where every component used in that definition was well-understood and easily assessable by resources available to the computer, then you could apply existing AI technology to the problem of optimizing for it. Whether the computer had the necessary resources for doing so, in terms of memory space and processing speed, is another matter.
-- Guges --
okay, okay, it didn't come off like i meant it to. it's just that the more i thought about what to write, the more stupid the phrase 'embarassingly parallel' seemed. so i wrote what i thought was a commensurately stupid post. nevermind.
but anyway, come on, what kind of problem do you expect them to tackle on their first try. it's like this is their first baby step into this new way of computing and all people can say is how embarrasingly parallel their problem was.
come on: "embarassingly parallel". laugh.
You pose the problem by making a strand that only a valid solution can pair with
I don't think this is quite how it works. The problem here is that, due to the 1:1 nature of DNA pairing (i.e. A and T, G and C), if you can give a strand that only the correct solution can pair with, you, by definition, have to know the correct solution.
StickBoy
I think I'm not quite getting the point; the article said that they included the answers with the data:
After synthesizing trillions of DNA strands to stand for every possible solution, his test tube finally came to the correct conclusion after about a week.
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? How could this scale when the answer appears to need be fed with the data...
It's going to be the only intelligent response. I can't imagine that it could take less time to generate a strand of RNA containing all possible solutions to a complicated problem, than it would take to solve it with a digital computer. Just imagine if the article read, "We stored all possible solutions on our hard disk, then programmed our compaq computer to evaluate each one in turn!" Just as it wouldn't matter much if they used a SCSI or an IDE hard disk, it doesn't matter that they use RNA as the storage medium.
I may be wrong but here is how I understand it. By encoding the information in the RNA strands that means they merely have a very large number of strands which have a certain random configurations. These configuration can be interpreted as solutions to a problem set, some corerct some incorrect. They then narrow down the strands in the test towards correct answers by adding certain chemicals. These chemicals react with the correct or incorrect solutions in a certain way as to give the testers an effective way to isolate the incorrect solutions from the answer set.
Sorry about forgetting what a mole is. That is pretty sad on my part.
You are correct that you could miss an important sequence. I said that here but nobody picked it up. Moderators should browse everything...
This DNA computing is basically enumeration of all solutions in parallel. If I remember correctly, the solution time scales linearly with the number of variables. The resulting problem is, each step can take a long time (hours?). So even though it scales nicely, it takes forever.
I think the article said it solved a problem in a week for a problem with 512 possible answers. That is 2^9, 9 variables. About day/variable, assuming linear scaling.
I think people are working on ways to extend DNA computing so that larger problems can be handled, and steps can be accomplished more quickly. But I have no good refs...
I have see a couple of presentations on this DNA computing thing. As far as I understand it...
DNA helix- two strands. We can use the 4 base pairs GATC (remember GATTACA the movie...) to make a single strand. There should exist a mate to the single strand, like a photo negative.
You pose the problem by making a strand that only a valid solution can pair with. Then you expose the solution DNA strand to a mixture of random solutions. Only the correct solutions can attach to the single strand solution. Then you examine your mix and figure out what a solution to the problem is.
Becaue you are relying on chemical steps, you sometimes get the wrong answer. You also cannot verify that you really have a random set of potential solutions (the single answer may not actually be in your flask..) And each chemical step takes time to process, and there are multiple steps.
So basically it is brute force, but a fairly good attempt at brute force, much better than using computers we have today. The molecules are moderate size, bigger than atoms but smaller than polymers or cells. basically a protien. Each base pair is made up of a few atoms, I think. The molecules don't move fast like gas molecules cause they are in solution, but they are still move a lot.
Quantum computing seems like a much cooler way to do these problems.
When you say they wouldn't be able to solve NP-hard problems are you implying that they could possibly solve non-hard problems?
Well, computer scientists have a particular definition of "hard". CS people measure how hard a problem is by counting the number of steps the best algorithm for the problem takes to process some number of data n.
An practical algorithm runs in n steps. Even n^5 steps isn't all that bad. But there exist problems where the n ends up in the exponent -- like 2^n steps. For large values of n, the time required to solve such problems just isn't reasonable, and while parallel computers can help a bit, for large values of n, the amount of help they can provide is insignificant compared to the number of steps needed. In practice this means that parallel computers can make easy problems solvable faster, but they really aren't a solution to hard problems.
Obviously, anyone can solve a given *instance* of an NP-complete problem for a small n. An NP-complete problem is so called because no algorithm exists that can compute the solution in polynomial time, which means for large values of n, the time required by even the fastest supercomputer exceeds the expected life span of the Universe. Adelman in no way disproved that the TSP problem was NP-complete.
static int count;
int placeknights(int board, int mask, int start)
{
int i;
printf("%02d: %c%c%c\n %c%c%c\n %c%c%c\n\n", ++count,
  (board & 1) ? '*' : '.', (board & 2) ? '*' : '.',
  (board & 4) ? '*' : '.', (board & 8) ? '*' : '.',
  (board & 16) ? '*' : '.', (board & 32) ? '*' : '.',
  (board & 64) ? '*' : '.', (board & 128) ? '*' : '.',
  (board & 256) ? '*' : '.');
for(i = start; i < 9; i++)
 if(!(mask & (1 << i)))
  placeknights(board | (1 << i), mask | masks[i], i + 1);
}
int main(void)
{
placeknights(0, 0, 0);
}
logan
logan
#include <stdio.h>
int main(void)
{
int i, j;
for(i = j = 0; i < 0x200; i++)
if(((!(i & 0x080) && !(i & 0x020)) || !(i & 0x001)) &&
((!(i & 0x040) && !(i & 0x100)) || !(i & 0x002)) &&
((!(i & 0x008) && !(i & 0x080)) || !(i & 0x004)) &&
((!(i & 0x004) && !(i & 0x100)) || !(i & 0x008)) &&
((!(i & 0x001) && !(i & 0x040)) || !(i & 0x020)))
printf("%02d: %c%c%c\n%c%c%c\n %c%c%c\n\n", ++j,
(i & 0x001) ? '*' : '.', (i & 0x002) ? '*' : '.',
(i & 0x004) ? '*' : '.', (i & 0x008) ? '*' : '.',
(i & 0x010) ? '*' : '.', (i & 0x020) ? '*' : '.',
(i & 0x040) ? '*' : '.', (i & 0x080) ? '*' : '.',
(i & 0x100) ? '*' : '.');
}
logan
The difference being, "We stored all possible solutions on our hard disk, then programmed our compaq computer to evaluate them at the same time !" The cool part being the parellel operation of the RNA computer. Now assume that the computer were fed random information. Based on what I had been reading, it would only keep the solutions that solved the equation. Digesting those that didn't.
Time flies like an arrow;
Time flies like an arrow;
Fruit flies like a bananna
Subject says it all
Time flies like an arrow;
Time flies like an arrow;
Fruit flies like a bananna
Nothing personal, this is meant for everybody.
And I'll tell you why.
Because many are commenting about its use in d.net's computing effort, I'll tell you a major flaw in this. Although the RNA and a d.net's client both are trying all possible combinations, d.net can expand its list of possible combinations on the fly.
Example: d.net's RC5 client started without internet access will assemble a list of possible keys(1*2^32 keys) and then test them.
I will think this is really cool when a cell given basic information about a problem(the rules of knights & the size of the board) and then determines what the possible placements are, then decides which ones are valid.
Then, it will be ready for real computing.
You can't legislate goodness. Let each to his own destiny, by will of his freely made choices.
Then there's the question of scalability - what would be the volumes and masses of reactants that you would need to solve particular problems? The great promise of the approaches being tried by Adleman et al is that they offer massive parallelism, but exactly because of that the scaling problem comes in as several posters have pointed out.
Dreaming is cool.
I'm glad it's not just my lab that thinks that. Sighs of distress are heaved whenever she puts a trendy "biocomputing" spin on things. When you say they wouldn't be able to solve NP-hard problems are you implying that they could possibly solve non-hard problems?
Let's first calculate the # of permutations possible for an RNA string
We have 4 bases (A,C,G and U (this is RNA not DNA right?)) - so we have 4 posibilities for a string of 1 bases, and 16 for a string of 2 bases (4x4=16 or written out AA,AC,AG,AU, CA,CC,CG,CU,etc). So for a string of 10 bnucleotide bases we have 4^10 possibilities or 1048576 (1x10^6). Thats alot for just such a short chain.
How much would that weigh?
An average nucleotide (the base (ACGT or U) plus the binding sugar) has an atomic weight of approximately 500 Daltons. So if we multiply out the atomic weight times the number of strands divided by Avrogadros number (6.023x10^23) we can figure out the weight of those million different strings of RNA
So we get
500 x (1x10^6)/(6.023x10^23)= approx 1x10^-15 grams. THAT's 10to the MINUS 15 grams of material. That's a freakin TINY amount of stuff.
So how many solution could be in a gram(that's actually a fair amt of RNA,but anyway)
1x10^6 times 1x10^15 or 1x10^21 HUGE BRUTE numbers eh?
This isn't exactly right because you would have to make the RNA chain slightly longer (23 or 24 bases long) to get all of these solutions, but you get the point.
Of course an RNA or DNA computer won't be exactly correct. Binding mismatches can occur, you won't get truely random sequences or not all of them will form, but it will probably be MORE accurate than an electrical computer.
..........FULL STOP.
A mole is approx 6.02e23 "things" (in this case, molecules), so your estimate would be off by a factor of 2.
And I suppose that it is important to note that as long as you've got a pot of 'random' DNA, there's always the chance that no matter how much you have you may be missing one important sequence. Nevertheless, I like the idea - but how much faster <I>could</I> this solve P-NP problems? Is there any way to estimate that?
-- Imagine how much more advanced our technology would be if we had eight fingers per hand.
I'm not positive, but my guess would be that the amount of RNA you'd need would increase exponentially, while the time would remain pretty constant. You're basically just trading off computational time for space, by trying a ton of things in parallel.
-ElJefe
The article made reference to the 7 city travelling salesman problem, which appears to have trillions of possible solutions. The DNA computations took about a week to finish before finding the correct solution.
On a regular computer, if you had a pre-generated list of solutions, all prepared beforehand for processing, wouldn't a standard PC be able to evaluate this same problem in a week?
Does anyone know how long it takes to synthisize trillions of DNA or RNA strands?
Actually a 10 city TSP can be solved by a normal computer in decent time. 10 citys can even be solved by brute force, 10! is something like 3*10^6 which can be computed. And there are much better solutions than brute force.
Surely technology such as this could be used to BREAK THE ENCRYPTION ON COPYRIGHTED WORKS! Isn't it therefore illegal under the terms of the DMCA?
I gots ta ding a ding dang my dang a long ling long
Distributed.net seem to have problems with handing out their keyspace without the computers processing keys wrong. Maybe we should wait a while.
No, but that's not saying we can't up the limit. Conventional digital computers can't handle umlimited numbers- we're limited by the amount of memory we have. This seems like a similar problem (as much as the two computational systems can be similar), and I've no doubt this limit will change.
-Matthead
Is this what people are talking about when they say "the viral nature of the GPL"?
-Jordan Henderson
--
The shareholder is always right.
The insane computer in Demon Seed was constructed using RNA! Anyone remember its name?
A pre-post note: OK, as I have been reading through these postings, a few thoughts have occured to me. You can berate me for being a foolish dreamer, or a lengthy poster as you like. It's a long post with a lot of ideas. I enjoy everything, flame as you will ;)
This algorithm that has been created is destructive, neh? And from what I've read, it can't select the correct answer and present it in any way. Also, it has the potential to be incorrect. The RNA also has to be pre-encoded with all possible answers, which gives it a finite number of answers. The RNA solver has to be pre-coded as well. These are all limitations that will stop RNA computing from going computational.
But putting the RNA inside of a container, would solve these problems. Call this container a cell for ease, if you would, although it really wouldn't be. The cell would basically 'regulate' the RNA, so the actions it took would not be so uncontrolled. Enzymes are great, mind you, but we don't have all that solid a hold on them. The cell would also replicate, given correct proteins. So we create one cell and drop it in a vat of metaphorical peanut butter, and watch it multiply. If the multiplication process was automated and modified properly, we could end up with cells with 'identification numbers'.
The identification numbers would serve as an organization process to allow the cells to all refer to their 'parent cells' on which process to execute. The parent cells would refer to their parent cells, etc. If all these cells were placed in a non-moving communicative network, this would actually work. Then you could stimulate the parent of all cells electronically, as humans and all other organisms do. This could be the user's job - tell the cell what to do. It will refer to the 'memory' cells (containing RNA sets with memory pairs which respond to queries about their setting) for programming instructions, then send that out to all the 'child' cells. You get the idea - massively parallel, heirarchal(sp?), nondestructive (reproducing cells don't destroy themselves) processing. The heirarchal process leaves us with an EXTREMELY rare chance of error (check an answer 50 times?). The parallel process gives us extreme power. The RNA factor gives us extreme speed. And the cell network idea gives us the power to modify RNA (through proteins inside the cells themselves, reacting to electric stimuli).
Anyone see any problems with this? I don't, but I have nil background in biochemistry or biocomputing. So someone else answer the comments ;)
** Hit any user to continue **
I have two questions about this technology,
Is this technology the birth of real living neural networks? I ask this because this is how the brain is thought to work, millions of processors (neurons) working in parallel. And if so would it mean that creations like Data from Star Trek:TNG isn't so far off.
Secondly,
What would happen with cryptology. The government or some agency could in theory use this technology to break encryption schemes. Not because of power behind one processor but because of hundreds of thousands of processors solely dedicated on cracking something.
thelopez
This would certainly surprise everyone trying to evolve software:)
Seriously, this could give you some nice, fast software if you could select the right mutants- I remember seeing an article somewhere that a similar system reduced the transistor count in a chip from ~200 to ~50.
I wonder if it would be possible to evolve a stable Windows? A stress test, so to speak.
If you think this is interesting, check out The Cosmic Serpent : DNA and the Origins of Knowledge by Jeremy Narby. My girlfriend gave me this for Christmas and I swear it was one of the most intriguing books I've read on DNA ever.
========================================
Death will come, and will have your eyes
-- Pavese
very cool idea. how much though?
I think the algorithms basically do the same thing you described. Adleman et al's approach would require about 1 gram of DNA. To do the "hard part", it builds up from a set of primitive operations (merge, separate, set, and clear). These can be controlled robotically, but will still take a bit of time since it takes a while before all the molecules settle into place after each operation. IIRC, bottom line a year or two ago was several months in theory. I'm not sure where current technology stands.
(this overview of DES cracking as well as more information about D/RNA computing in general can be found in DNA Computing by Paun, Rozenberg, Salomaa)
-----------------------------------------------
-----------------------------------------------
how much bandwidth has been wasted by this sig?
This is the first time stuff has been done with RNA, DNA is what Adelman used and what has been used up to this point... so its not old news...
Esperandi
HA! No.... if you had a standard PC, it wouldn't have enough storage space to store the possible solutions (unless you have a few hundred thousand terabyte drives lying around). Until this guy did this, any travelling salesman problem above n=5 was considered NP Complete - meaning theoretically possible, but the calculations would take so long even trying to do it would be stupid... as in it would probably take the age of the universe to calculate it.
Esperandi
You've got a hundred thousand terabyte drive to store the solutions on?
;) How many years is a trillion weeks?
BTW, it would take several centuries or so to evaluate all of the answers on your compaq.
Esperandi
Serial vs parallel actually DOES make a difference, and it takes virtually no time at all to generate all those RNA combinations. It's nice that you can't imagine how reality works so you assume that it is limited to your feeble mind, but it takes much less time to generate "a strand of RNA containing all possible solutions"... it doesn't do that, it generates a few trillion AT THE EXACT SAME TIME.
Take everything the RNA does and multiply it by a few trillion and you'll get an idea on how long it'd take to do it serially on a PC
That time is constant as well because they are produced in parallel with splicing, completing, and complementing enzymes.
It can't scale time-wise the same as normal computational machines, just look at what they've done... they've been solving NP-complete problems of degrees never even imagined within the realm of possibility. So maybe it can't solve a 10 trillion city travelling salesman problem without 100,000 gallons of RNA.... so what? It can solve a 10 city one that no one thouhgt would be possible in as much time as it takes a normal computer to solve a 5 or 6 city one.
Esperandi
They already have solved NP-complete problems. The problem is, as soon as they solve them, someone says "oh, well then it obviously wasn't NP-complete, we just screwed up before". The very first problem Adelman did with a DNA calculation engine was considered NP-Complete.
Esperandi
(it was a travelling salesman hamiltonian path problem of some really high number of cities... something like 5 or 10 more than they said was impossible)
Wired beat them to the interview and let the guy who invented this stuff write an article in their magazine somewhere around 6 years ago.
The chess thing was probably Marvin Minsky or one of his friends in Tech Square in the AI labs near MIT... read the book "Hackers" by Stephen Levy if you really dig those kinds of guys, its all about the great stuff the guys just beginning in the field did.
Esperandi
Sure, this is impressive, but just wait 50 years and check out how good the microwaveable food will be!
You can't use RNA or DNA while its inside living cells... if I knew how to get it out of my cells I could probably do some DNA computing experimentation after reading "DNA Computing."
Esperandi
To the paranoiacs: its not the big corporations that stop me from being able to extract DNA from my cells, so don't scream about trademarks or patents or any of that crap.
You're basically just trading off computational time for space
Ah, but doesn't it take time to produce all that RNA? They have to be encoded with specific patterns for each problem. And they can only be used once, and then you need a fresh batch.
- Isaac =)
Mmmm, 2^(3*10^9) different solutions sounds pretty decent to me.
-=* no sig *=-
No it doesnt take much time. It takes about 30 minutes per cycle to add a new base on a dna strand in a commercial DNA synthesizer. Add equal amounts of the four possible bases each round of the synthesis and you can make 4^n sequences in n*30 minutes. ie overnight you can make 10^15 DNA sequences. You then use the parallel nature of enzymatic solution phase reactions to convert all of those into RNA sequences (~1 hour)
no sig.
As quoted in her preprint
"Thus, as 2^50 = ~10^15 is approximately the number of RNA molecules that in vitro selection protocols can currently search, this projects an upper bound for the size of DNA or RNA computing experiments that could use exhaustive search algorithms. Fortunately, this is on the same order as many interesting problems in computer science, such as DES."
I think that this approach could be streamlined to solve a problem of this magnitude in the course of a couple days. How does this compare with current computer based methods?
no sig.
This is a problem in combinitorics, they said. Generating all possible combinations is trivial, though dull. The difficult question is: which of the 2^10 combinations are solutions? That's where the massive parallelism in the testtube comes in, I gather. I don't understand exactly how it works, but apparently his RNA winnows out the good answers and tosses(most of) the bad. That doesn't seem easy.
See what I've been reading.
How long does it take to generate the solutions?
What happens if you change the data?
Currently, the only known way to guarantee the best solution is to generate all possible solutions, which is why it's so hard. Your suggestion doesn't improve the performance of the algorithm.
that what im talking about...
my measly d.net stats would go through the roof with an rna box (err... cell cluster) ;-)
theres actually a very interesting discussion on this in applied cryptography (by the guy whose name i forget. it discusses algae used for computing (checking) keys to crack crypto... i think a cubic meter of seawater could mop up all those nasty super computers and uber-parallel monsters that lead in the stats race on d.net ;-) hehe thats my plan
the real shiftaling has user number 5134
Karma: -43 and DROPPING!!!
when i think about minimizing our technology, i mostly think about the minimal we can get. today, while we talk about the minimal transistor, we probably want to talk about a lonely atom, with 1 or more electrons. and when i think about it in terms of biotechnology, i think of the smallest cell we need, and it's still huge, it's made of milions of atoms. not that i'm against new things, and espeacially not against biotechnology, but think about that that we'll never minimize things in biotechnology as we might in normal technology.
Dan.
TBM, you need to stop eating those shrooms! btw, hows life in you're part of the universe? LPC - scooby dooby doo, where are you?
It seems like we're just heading in circles. First silicon is used for computing - then we decide molecules can do the job - then we decide RNA would be a really good medium - how about DNA? then cells? then tissues? how about organs? next systems? ("hey dude, i have a 200GHz circulatory system") - Next people. Pretty soon we're gonna have people breaking keys and typing shit for eachother.
My mom can render 200million triangles per second...what can your mom do?
-FluX
All flame will be summarily flamed! thank you for calling america on-crack.
"It is seldom that liberty of any kind is lost all at once." -David Hume
I am not really a computer scientist or a biologist, but just in terms of biomass, I would imagine that you would need 2x or 3x what the RC5-56 computer that a previous poster considered (1 kg). That would be for solving a 56 bit problem(RC5 being a 56 bit key...) I guess. Don't quote me on that, I am probably wayyyy out of my league to say somethig like that.
I dont have a
I am certainly not a real computer scientist, or for that matter, a real biologist, but while reading this article, I had some interesting thoughts. What if a biocomputer scientist (that would be the correct term for this kind of situation, right?) could encode a DNA strand that coded (coding meaning the DNA -> RNA -> protein translation coding) for specific "computing" proteins. These proteins could would theoretically be able to do "normal" computing fucntions such as add, subtract, multiply... The biocomputer scientist then makes a DNA strand with a "program" encoded in it. This strand would have base pairs that would code for something like computer functions (eg. the variables, what needs to be checked in the variables, ect...). Now, if the first strand could run adds, subtracts, multiplies, ect, on the second strand, then that biocomputer scientist could have a semi-functioning biocomputer. The idea could get more and more complicated if you had a "bio-operating system". This would be able to take and save data for other uses on other D/RNA strands. It could modify that data. That biocomputer scientist could have a bath of these computing proteins and D/RNA strands running all kinds of problems, making and saving data, editing that data, analyzing that data, ect... You could even Or maybe i just sound like a siily high-school optimist kid who dreams too much. What do you think?
I dont have a
I wonder how many chess games I could win with my body as a giant beowulf cluster.
On the other hand since supposedly my cells are in quantum multiverses this could be dangerous...
The human genome contains about 3,000,000,000 bases (see here). That's in every single cell, and an RNA computer may be able to do more than that, but it's definitely not unlimited numbers.
--
Play Match-It.
Here's another article on the same topic.
RNA Harnessed As Molecular Computer Tests Well
From the same people (UniSci) that brought you Quantum Evolution.
--
He lives in a world where those who do not run the client software of the omnipresent meme are unacceptable.
Yes, it's true that the computer had to have all of the possible answers pre-generated and fed to it. This is a terribly inefficient system, but you have to keep in mind the scope and purpose of the project. This technology is very new and very experimental. Therefore, they wanted to limit the scope of their experiment, as any good experimenter should. A real implementation would undoubtedly generate possible answers on the fly, and check them much like the way temporary variables are used to consider possibilities in most current programs. So, while this may not have been as good from a computing standpoint, it is better from a scientific standpoint, because it lets them see more accurately where the errors are.
WARNING: there is a trojan on your
The idea is that it is set up with all the possible combinations, and then it works out which ones are "right" by itself - so it is a computer.
have to pay license fees to use RNA, it will be illegal to try to "read" it, even in Norway, etc. etc. They've already staked out a proprietary claim on information in the human genome, and this RNA computer has some SERIOUS PROFIT-MAKING POTENTIAL.
Then again, genetics seems to do a pretty good job with *us* . . . Whether by chance or divine intervention, it's good enough to render a human pretty decently.
Al Qaeda has ninjas!
Sure, give the system to microsoft. Before you know it they will translate windows2000. The only problem is the resulting RNA/DNA system will be the size of John Candy after dinner.
There are two kinds of people in the world: Those with good memory.
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.
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.
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.