Want to read Slashdot from your mobile device? Point it at m.slashdot.org and keep reading!

 


Forgot your password?
Close
typodupeerror
×
Science

RNA Computer 119

Posted by emmett from the internal-wearable-computing dept.
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?"
This discussion has been archived. No new comments can be posted.

RNA Computer More

RNA Computer

Comments Filter:
  • 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 [slashdot.org] 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.

  • In C (Score:1)

    by Logan ( 7529 )
    static int masks[] = { 0xa1, 0x142, 0x8c, 0x10c, 0x10, 0x61, 0x62, 0x85, 0x10a };
    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,
    &nbsp&nbsp(board & 1) ? '*' : '.', (board & 2) ? '*' : '.',
    &nbsp&nbsp(board & 4) ? '*' : '.', (board & 8) ? '*' : '.',
    &nbsp&nbsp(board & 16) ? '*' : '.', (board & 32) ? '*' : '.',
    &nbsp&nbsp(board & 64) ? '*' : '.', (board & 128) ? '*' : '.',
    &nbsp&nbsp(board & 256) ? '*' : '.');
    for(i = start; i < 9; i++)
    &nbspif(!(mask & (1 << i)))
    &nbsp&nbspplaceknights(board | (1 << i), mask | masks[i], i + 1);
    }

    int main(void)
    {
    placeknights(0, 0, 0);
    }

    logan

  • This experiment apparently didn't find every solution, from what I understand. There are 94 possible solutions out of 512. The experiment came up with 43 answers, only one of which was not a valid solution. So while obviously non-solutions were weeded out, the solution space was not as exhaustively represented as one might wish. Still, pretty impressive.

    logan

  • More C (Score:1)

    by Logan ( 7529 )
    This uses the serial version of the RNA algorithm.

    #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;
  • Subject says it all
    Time flies like an arrow;
  • Maybe I don't understand the problem...

    ------- \
    |K|O|O| )
    ------- /
    |O|O|X| > 6 solutions * 4 corners = 24
    ------- \
    |O|X|O| )
    ------- /

    ------- \
    |O|K|O| )
    ------- /
    |O|O|O| > 6 solutions * 4 sides = 24
    ------- \
    |X|O|X| )
    ------- /

    ------- \
    |O|O|O| )
    ------- /
    |O|K|O| > 8 solutions = 8
    ------- \
    |O|O|O| )
    ------- /

    And the last time I checked 24 + 24 + 8 = 56

    What am I missing?
    Time flies like an arrow;
  • 1024 positions a week? This is much slower than a regular computer. Probably because of the speed of the chemical processes to actually sort out the DNA. On the other hand, I can imagine that with enough vats of DNA the process wouldn't take much longer for even really really difficult problems, like a calculation of the optimal placment of fiber cables between houses in the U.S., or cracking RCS-64 really really fast.

    I wonder what the speed would be in MIPS?
  • Lately I haven't seen any of those comments, but I've been seeing more than enough comments like yours. It was funny the first three times, but now it's getting to be about as funny as the "First post" so please stop.

    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.
  • I think it's an interesting idea. But I think that there would be practical problems running it: there's a lot of error in living systems, they mutate a lot, they operate a lot by random diffusion and stochastic processes. They survive mostly through massive redundancies. They're slow compared to electronic computers.

    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.
  • 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?
  • I'm not really too sure I understand HOW they do this - but <I>can</I> it be made faster? Seems to me like using two 386s in parallel just for the sake of doing so instead of using a high-end Athlon.

    Then again, I suppose that the whole purpose of this RNA computing experiment was to show that it can be done.

    One important point - it selected a WRONG answer? Lotta good it'll do if it's running fast and in parallel if it's WRONG =)
  • 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
  • so then the next question is: what would be the analog to MPI in the RNA system? could the enzyme be modified "on the fly" due to the shape the result was taking? not as simple as a pH test, i'm sure...
    am wondering about recursion, too (feed the answer of one test tube in as the input of another...)
  • There were a total of 43 correct solutions among 512 total possibilities; the RNA computer found all 43 correct ones and one incorrect one.

    are we sure the answer space is 94? reads as though all 43 were found...
  • 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?

  • Distributed.net seem to have problems with handing out their keyspace without the computers processing keys wrong. Maybe we should wait a while.
  • Quantum computing seems like a much cooler way to do these problems.

    quantum computing not faster for this problem. why? because you have to get all possible solutions. if all you demand is a single solution, then possibly quantum computing is faster.

    while it's true that a quantum computer could check all 512 possibilities at the same time, you can never ever get more than one answer in the end of the computation.

    cheers,

    sh_

  • 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.

    • Hmm, you could use a virus as a loader.

    Is this what people are talking about when they say "the viral nature of the GPL"?


    -Jordan Henderson

  • does the RNA use quantum [slashdot.org] computation or just the brute force of having lots of medium-sized molecules moving really fast?

    --

  • 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 ;)

  • 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.

  • very cool idea. how much though?
  • People working on molecular computing have looked into this. Some literature:

    • Adleman, Rothemund, Roweiss, Winfree. "On applying molecular computation to the Data Encryption Standard." From 2nd DIMACS workshop on DNA Computers, 1996.
    • Boneh, Dunworth, Lipton. "Breaking DES using a molecular computer." From first DIMACS workshop on DNA Computers, 1995.

    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)

    -----------------------------------------------

  • 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
  • Read some more about the tech, they can do binary with it so that means they can do all this and more.

    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?
    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 ;) How many years is a trillion weeks?
  • 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.

  • 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.

    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)

  • 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?
  • 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.
  • 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?

    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

  • 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.
  • 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.
  • 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 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 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...
  • Whether by chance or divine intervention, it's good enough to render a human pretty decently.

    The human genome contains about 3,000,000,000 bases (see here [dcmsonline.org]). 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.

  • Here's another article on the same topic.

    RNA Harnessed As Molecular Computer Tests Well [unisci.com]

    From the same people (UniSci) that brought you Quantum Evolution [unisci.com].
  • 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.
  • 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.
  • 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.
  • 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...

  • 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.

  • Re:Wow... (Score:2)

    by ebw ( 5903 )
    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?
  • 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.

  • 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. :)
  • The two properties of DNA most important to molecular computing are:
    • Massive parallelism
    • Base pair matching (A-T, G-C)

    The second property is what gives it the capability of computing things.
    Adleman's original solution to the Hamiltonian path problem worked in the following way:

    • Give each of the n (=7) cities a unique encoding (string of DNA bases) c_i = t_i f_i. That is, each city encoding is divided into two parts: "to" and "from".
    • If the graph contains an edge from city i to city j, create the edge e_ij = f'_i t'_j, where f'_i and t'_j are the (DNA base) complements of f'_i and t'_j, respectively.
    • Dump all the c_i and e_ij into a clean test tube and wait a while for them to match up.
    • Remove all paths (i.e., double strands) of length != n. Then remove all paths that don't start with the first city and end with the last one. Then remove all paths that don't contain each city. (All of these filtering processes can be done by well-developed biochemical/mechanical techniques used regularly in normal DNA labs.)
    • If there are any paths left, you got yourself a Hamiltonian path!

    I'd love to draw diagrams, but it's kinda hard using lynx... One shortcoming of Adleman's experiment was that the method only works on this particular problem (kind of a DNA hack). But since then, several more general models have been created. One developed by Richard Lipton encodes binary numbers by representing them as graphs, and then using Adleman's method. Specifically, he has a vertex v_i for each bit position, and connects it to v_i+1 by way of "zero" and "one" vertices 0_i and 1_i (so there are edges from (v_i,0_i), (v_i, 1_i), (0_i, v_i+1), (1_i, v_i+1)). A particular number is just a path along this graph. So, you can dump all the the dna into a test tube, perform the operations needed your problem, and see if any of the remaining double strands are paths (not hamiltonian) from the first "bit" to the last, and thus solutions to your problem...

    But as some people have noted, DNA computing is slow...and while speed*parallelism makes up for some of it, it's still slower than a pc, and much much slower than distributed computing. There are different ways it could compete, though:

    • Ultrafast (and accurate) artificial DNA-like molecule created.
    • 3D nature better exploited. That is, the techniques used up to now don't really lend themselves to scaling in huge-ass vats. If they could, maybe you could fill your house up with DNA instead of building that Beowulf.
    • Solving more "natural" problems. Protein folding?
    • Nanotechnology. Instead of computing things, we could use the attachment properties of DNA to build nice little things (or make crystals to build nice little things). DNA is easily broken, though, so you have to be careful.

    -----------------------------------------------

  • 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...


    ------------
  • 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.
  • 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.
  • 2. Yeah, but will it run Linux?

    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.
  • If they are actually able to get an RNA-based computer to perform computational skills based simply on sequences, then what is stopping them from creating sequencing machines that hook up to your computer, and the next time you buy some software it comes in a vial. You pour your little vial into your computer and up pops a new piece of intelligent software!

    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?

  • The DNA->RNA->protein chain that builds our cells needs to transfer 6 bits of binary information per amino acid used. Our bodies do about 10-to-the-power-21 simple computational operations per day just growing and repairing damage.

    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.

  • Key Cracking (Score:3)

    by joshv ( 13017 ) on Saturday February 05, 2000 @11:59AM (#1302419)
    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 (Score:3)

    by zook ( 34771 ) on Saturday February 05, 2000 @02:32PM (#1302420)
    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? (Score:3)

    by Duxup ( 72775 ) on Saturday February 05, 2000 @12:01PM (#1302421) Homepage
    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 .... (Score:4)

    by taniwha ( 70410 ) on Saturday February 05, 2000 @12:34PM (#1302422) Homepage Journal
    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... (Score:5)

    by gatzke ( 2977 ) on Saturday February 05, 2000 @12:06PM (#1302423) Homepage Journal
    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 (Score:5)

    by FigWig ( 10981 ) on Saturday February 05, 2000 @12:18PM (#1302424) Homepage
    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 (Score:5)

    by nels_tomlinson ( 106413 ) on Saturday February 05, 2000 @12:09PM (#1302425) Homepage
    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 (Score:5)

    by Dr. Zowie ( 109983 ) <slashdotNO@SPAMdeforest.org> on Saturday February 05, 2000 @12:16PM (#1302426)

    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.

Slashdot Top Deals

Receiving a million dollars tax free will make you feel better than being flat broke and having a stomach ache. -- Dolph Sharp, "I'm O.K., You're Not So Hot"

Close