Fwd: Using 'Nature's Toolbox,' A DNA Computer Solves A Complex Problem

From: Wade T.Smith (wade_smith@harvard.edu)
Date: Fri Mar 15 2002 - 03:07:44 GMT

  • Next message: AaronLynch@aol.com: "Re: Predicting the Stock Market Is Child's Play"

    Received: by alpheratz.cpm.aca.mmu.ac.uk id DAA11526 (8.6.9/5.3[ref pg@gmsl.co.uk] for cpm.aca.mmu.ac.uk from fmb-majordomo@mmu.ac.uk); Fri, 15 Mar 2002 03:13:37 GMT
    Subject: Fwd: Using 'Nature's Toolbox,' A DNA Computer Solves A Complex Problem
    Date: Thu, 14 Mar 2002 22:07:44 -0500
    x-sender: wsmith1@camail.harvard.edu
    x-mailer: Claris Emailer 2.0v3, Claritas Est Veritas
    From: "Wade T.Smith" <wade_smith@harvard.edu>
    To: "Memetics Discussion List" <memetics@mmu.ac.uk>, "SKEPTIC-L" <skeptic@listproc.hcf.jhu.edu>
    Content-Type: text/plain; charset="US-ASCII"
    Message-Id: <20020315030741.CAFF31FD49@camail.harvard.edu>
    Sender: fmb-majordomo@mmu.ac.uk
    Precedence: bulk
    Reply-To: memetics@mmu.ac.uk

    ---------------- Begin Forwarded Message ----------------

    PASADENA, CALIF. 91109 TELEPHONE (818) 354-5011

    Contact: JPL/Carolina Martinez (818) 354-9382
                  USC/Matthew Blakeslee (213) 740-9335

    FOR IMMEDIATE RELEASE March 14, 2002


    A DNA-based computer has solved a logic problem that no person could
    complete by hand, setting a new milestone for this infant technology
    that could someday surpass the electronic digital computer in certain

    The results are published in the online version of the journal
    Science on March 14 and will also run in the print edition.

    The new experiment was carried out by USC computer science professor
    Dr. Leonard Adleman, who made headlines in 1994 by demonstrating
    that DNA -- the spiraling molecule that holds life's genetic code --
    could be used to carry out computations.

    The research was partially supported by grants from NASA's Jet
    Propulsion Laboratory, Pasadena, Calif., and NASA's Ames Research
    Center, Moffett Field, Calif., as part of the Computing, Information
    and Communication Technology Program.

    The idea was to use a strand of DNA to represent a math or logic
    problem, and then generate trillions of other unique DNA strands,
    each representing one possible solution. Exploiting the way DNA
    strands bind to each other, the computer can weed out invalid
    solutions until it is left with only the strand that solves the
    problem exactly.

    Although they are still nowhere near primetime, "DNA computers do
    have several attractive features," said Adleman, distinguished
    professor of computer science and biological sciences and holder
    of the Henry Salvatori Chair in Computer Science in the USC School
    of Engineering. "They are massively parallel, compute with extremely
    high energy-efficiency and store enormous quantities of information."

    Adleman's first experiment proved that computing with molecules was
    possible. But the problem solved -- to find the shortest route among
    seven cities -- could easily have been solved by a person with a pencil
    and paper. Adleman's new experiment solves a problem requiring the
    evaluation of more than one million possible solutions -- too complex
    for anyone to solve without the aid of a computer.

    It required a set of 20 values that satisfy a complex tangle of
    relationships. Adleman's chief scientist, Nickolas Chelyapov, offered
    this illustration: Imagine that a fussy customer walks onto a
    million-car auto square and gives the dealer a complicated list of
    criteria for the car he wants.

    "First," he said, "I want it to be either a Cadillac or a convertible
    or red." Second, "if it is a Cadillac, then it has to have four
    seats or a locking gas cap." Third, "If it is a convertible, it should
    not be a Cadillac or it should have two seats."

    The customer rattles off a list of 24 such conditions, and the salesman
    has to find the one car in stock that meets all the requirements.
    (Adleman and his team chose a problem they knew had exactly one
    The salesman will have to run through the customer's entire list for
    each of the million cars in turn -- a hopeless task, unless he can move
    and think at superhuman speed. This serial method is the way a digital
    electronic computer solves such a problem.

    In contrast, a DNA computer operates in parallel -- with countless
    molecules shimmying around together at once. This is equivalent to each
    car having a valet inside who will listen to the customer read his list
    over a PA system and will drive off the lot the moment his car fails one
    of the conditions. By the time the customer finishes his list, his dream
    car will be waiting alone on the lot.

    While the time needed to solve problems of this class (called
    "NP-complete problems") increases exponentially (2, 4, 8, 16 ... ) for
    serial computers, it increases only linearly (2, 4, 6, 8 ... ) for
    parallel computers.

    In principle, then, the DNA computer should outstrip the electronic
    computer on savagely complex combinatorial problems -- breaking
    schemes, for example. Unfortunately, Adleman said, the DNA computer
    currently is too error-prone to achieve its great potential.

    "In the past century we've become really good at controlling electrons,"
    he said. "It would take a breakthrough in the technology of working with
    large biomolecules like DNA for molecular computers to beat their
    electronic counterparts."

    Still, even if no one finds a way to beat electronic computers on
    very complex problems, Adleman said, DNA computers might find
    applications in other areas. "It's possible that we could use
    DNA computers to control chemical and biological systems in a way
    that's analogous to the way we use electronic computers to control
    electrical and mechanical systems," he said.

    Adelman suggested, for example, that such systems might someday be
    engineered into living cells, allowing them to run precise digital
    programs that would interact with their natural biochemical processes.
    "We've shown by these computations that biological molecules can be
    used for distinctly non-biological purposes," he said. "They are
    miraculous little machines. They store energy and information, they
    cut, paste and copy.

    "They were built by 3 billion years of evolution, and we're just
    beginning to tap their potential to serve non-biological purposes.
    Nature has given us an incredible toolbox, and we're starting to
    explore what we might build."

    Other co-authors of the Science paper were Ravinderjit S. Braich,
    a post-doctoral student; Cliff Johnson, a neurobiology Ph.D.
    graduate student and Paul W.K. Rothemund, who received his Ph.D.
    and is now at Caltech. The research was also supported by grants
    from the Defense Advanced Research Projects Administration, the
    Office of Naval Research and the National Science Foundation.

    JPL is a division of the California Institute of Technology in Pasadena.


    ----------------- End Forwarded Message -----------------

    This was distributed via the memetics list associated with the
    Journal of Memetics - Evolutionary Models of Information Transmission
    For information about the journal and the list (e.g. unsubscribing)
    see: http://www.cpm.mmu.ac.uk/jom-emit

    This archive was generated by hypermail 2b29 : Fri Mar 15 2002 - 03:25:55 GMT