"I was deeply impressed by this book"--John le Carré
In the summer of 1993, Leonard Adleman was lying in bed reading James Watson's textbook Molecular Biology of the Gene when he mumbled to his wife, "Gee, this is really amazing stuff." And the idea hit him!
Adleman, a mathematician well-known for his work in computer security and cryptography, was struck by the similarity between DNA - the basic stuff of life - and computers. Using what is essentially a four-letter alphabet, DNA stores information that is manipulated by living organisms in almost exactly the same way computers work their way through strings of 1s and 0s. So, could DNA be made to function like a computer? If the answer's yes, new ways of building entirely different kinds of computers would open up - computers so fast they could solve some of today's unsolvable problems, so small they would exist at the molecular level.
Thanks to learning algorithms and other evolutionary tools being incorporated into computers, the machines around us are becoming more lifelike. But Adleman wanted to tackle the question from the opposite direction. What if life itself, already susceptible to genetic engineering, could be used to solve problems? What if DNA could be shifted from reproducing life to thinking about it? Adleman imagined a future in which organic and inorganic computers link up; he wanted to witness this momentous occasion in his lifetime.
Inspired, he hopped out of bed and started to build the world's first DNA computer.
During the '80s, when Adleman took on AIDS research in addition to mathematics, he found himself in a rare position for a computer scientist - he already knew how to do biological benchwork. He was able to synthesize strands of DNA, and splice and dice them to read the messages spelled out in their molecular strings. But what message should be encoded there if DNA was going to solve a computational problem?
After six months of intense research, scribbling out formulas, often reduced to an agitated trance, Adleman shouted Eureka! It was Christmas of 1993, and two unexpected gifts lay in front of him: a design for the world's first molecular computer, and its first problem to solve.
Adleman imagined testing his DNA computer with something called a directed Hamiltonian path problem. (The Hamiltonian path was named after Irish mathematician William Rowan Hamilton, who devised the routing conundrum in 1857.) A simplified version of this, known as the traveling salesman problem, poses the following question: Given an arbitrary collection of cities a salesman has to travel between, what is the shortest route linking those cities? Adleman's version limited the number of connecting routes between cities by specifying in which cities the salesman should begin and end his journey. Since not all cities are directly connected, the challenge lay in discovering the one continuous path to link them all.
A Hamiltonian path problem involving four or five cities can be solved by doodling on a piece of paper, but when the number of cities grows by even a small amount, the problem's difficulty balloons - it becomes what is known in mathematical terms as "hard." Hard problems cannot be solved efficiently by algebraic equations. Answers can only be found by crunching through every possible solution, and most hard problems are too difficult for humans or computers to solve. Finding a Hamiltonian path connecting 100 cities using a well-known algorithm, for example, would take 10147 operations. Assuming one was trying to solve the problem on a computer working at 1 trillion operations per second, this computation would take 10135 seconds - vastly longer than the age of the universe!
"I didn't want to do a cheap pet trick," says Adleman of choosing this problem. "I thought molecular computers might be able to solve problems that aren't currently solvable with electronic computers; I wanted the argument to be convincing."
Adleman limited his "test" to seven cities connected by fourteen possible routes. He was looking for the one itinerary known to connect the cities in a directed Hamiltonian path - a path that would begin in Atlanta, end in Detroit, and pass through each intervening city only once. What mattered was not the answer (Adleman already knew this), but the question. Could DNA compute? Could it figure out a problem that exemplifies those currently beyond our reach?
The day after Christmas, Adleman drove to the University of Southern California virology lab in Pasadena. He had been researching white blood cells and how HIV selectively kills them. But, today, Adleman wasn't planning to cure anything but an intellectual itch. He ordered 21 test tubes of single-stranded DNA (one for each city and the 14 routes connecting them).
A few days later, a series of glass vials with what looked like dust balls gathering in the bottom arrived at Adleman's desk.
He took a pinch from each ball and threw it into a test tube holding a watery solution. A second later he had his answer, and the world had its first molecular computer. Once the contents of the test tube were filtered and amplified, there remained a trillion copies of a molecule whose long strings of four-letter words encoded a Hamiltonian path for getting from Atlanta to Detroit. On the day of its creation, Adleman's DNA computer (he called it the TT 100, after the 100 microliter test tube) was already faster, thriftier, and smaller than its electronic cousin. This was indeed amazing stuff.
Although he's a professor of computer science at the University of Southern California at Los Angeles, the 49-year-old Adleman, with a mop of brown hair curling around his ears, looks like a perpetual student - a besneakered prof who could still get carded at the campus pub. Compact and trim, he plays a mean game of racquetball.
Adleman's office is a 10-by-10 faceless cubby furnished with a metal desk and a couple of brown plastic chairs. It's remarkable for what it doesn't have: a high-powered computer. Humming under the window is an old IBM PC-AT with a Goldstar black-and-white screen. Adleman uses this "dumb" terminal to send himself e-mail messages throughout the day, little reminders of things he's supposed to do.
Adleman's other office, at his San Fernando Valley home, where he does most of his work, is equally Spartan; it does, however, house a Pentium 90-based computer. One gets the idea from looking at these neutral, unmarked spaces that Adleman's real life is elsewhere - that he inhabits a mental landscape far from these rooms.
Adleman always knew he was going to be a scientist. As a kid, while his friends went surfing, he got up at 6 a.m. to watch Mr. Wizard perform science experiments on TV. His strongest subject was math. "It was just obvious to me," he says. "I felt as if I could have done all of high school mathematics in a week."
After completing an undergraduate degree in math at the University of California at Berkeley in 1968, Adleman dropped out of grad school to work as a computer programmer for the Federal Reserve Bank in San Francisco. There, he used the mainframe computer to run games like "Life," an early artificial life simulation.
After finishing graduate school in '76 (his second try) with a PhD in computer science (his thesis was on logic and number theory), Adleman was advised by his father to return to the bank - at least it offered a pension plan. Instead, Adleman took a teaching job at MIT for US$13,000 a year. Two other young researchers, Ron Rivest and Adi Shamir, occupied neighboring offices and they all became good friends. Yet Rivest and Shamir had a passion not initially shared by Adleman.
One day, the following year, Adleman noticed Rivest had a wild look in his eye. Rivest shoved into his friend's hands the draft of a paper by Whitfield Diffie and Martin Hellman announcing their theoretical discovery of public-key cryptography, a new way to encode information. Exactly how the scheme could be implemented was still unknown.
This required something called one-way functions - easy to compute in one direction, but practically impossible to compute in the reverse direction. For instance, multiplying two prime numbers together is easy, but working in the opposite direction (to factor out a number's prime components) is extremely difficult. Public-key cryptography would eventually capitalize on this fact to design public keys (the product of two prime numbers) to encrypt messages and secret keys (the factors of these prime numbers) to decrypt messages.
Adleman's friends couldn't shut up about one-way functions and secret code breaking; eventually their enthusiasm proved contagious. Rivest and Shamir kept popping off ideas for how to implement a public-key crypto system, and Adleman, the number-theory expert, was assigned to find the holes. Over the next few months, he cracked 42 potential systems. Some involved equations that took minutes to solve; others required a day or two of hard thinking.
One night, following a Passover dinner with some friends, Adleman was awakened by a phone call. It was Rivest with public-key crypto system Number 43.
"I knew he'd come up with an unbeatable system," says Adleman. "You get a feel for these things if you think about them long enough; my aesthetic judgment told me he'd finally done it."
Rivest stayed up all night drafting a research paper, which he presented to his colleagues the following morning. Published in the February 1978 Communications of the ACM under the joint authorship of Rivest, Shamir, and Adleman, the paper was officially titled "A Method for Obtaining Digital Signatures and Public-Key Cryptosystems." (The method is widely known today by the group's initials "RSA.")
"I thought this would be the least important piece of all my work," Adleman says. "I was so naive about cryptography and its applications."
But the three soon became international figures. Mail from all over the world began piling up in Rivest's office, including suspicious-looking letters from the department of defense in Bulgaria. Then, the National Security Agency got in touch. Adleman had never heard of the NSA, the government's secret spy apparatus (remember, this was the '70s); the spies were calling to say that the US government classifies cryptography as a munition, and that if they mailed their article overseas, they would be prosecuted for illegal arms dealing.
Too late! The genie was already out of the bottle. Toward the end of the '70s, crypto conferences had sprung up across the United States and Europe - cryptography was fast becoming a mathematical discipline of its own. "Ever since our article appeared, it has never stopped," says Adleman, "scientifically, commercially, politically."
Rivest, Shamir, and Adleman later decided to go into the crypto business. "It was like, 'Heh, we'll build a high-tech industrial corporation in our spare time,'" says Adleman. The papers were signed in Adleman's Los Angeles apartment in 1982 - he was now president of RSA Inc.
So, how did Adleman shape up as a businessman? He throws back his head and laughs. "In my hands the business went into the toilet," he says. "I was terrible. Just awful. We eventually reorganized the company and hired a real president." He's referring to James Bidzos, who joined RSA in 1986. Adleman is still a shareholder and advisor to the company whose future he sees as "relatively bright."
If It's Digital, It Can Count
It was while working on cryptography and other computer-security problems that Adleman began drifting into rather unusual waters for a mathematician. "Typically around the age of 40, mathematicians break off and come up for air," he says. "They don't lose their love for mathematics, but they look around for something new." When Adleman took a peek elsewhere, he saw biology. Although he coined the term "computer virus" to describe malign, self-replicating computer programs, it was his graduate student, Fred Cohen - now president of Management Analytics, an information security consulting group based in Monroe Falls, Ohio - who in 1983 released (in a controlled experiment) the world's first computer virus.
At the same time, Adleman recognized that AIDS was dominating scientific literature. He started reading up on immunology and hanging around the UCLA medical school, attending lectures on topics such as T cells and the immune system.
In short order, Adleman had thought his way into another discovery. He believed an effective treatment for AIDS lay in selectively removing one type of T cell - known as CD8 cells - from an infected individual. A natural homeostatic mechanism in the body would then automatically replace the CD8s with much-needed CD4 cells - those killed by HIV. Adleman and Dr. David Wofsy, an immunology professor at the University of California at San Francisco, began experimenting on genetically altered mice to prove their hypothesis. Part of their findings, now confirmed by other scientists at Johns Hopkins, were published in the February 1, 1993, issue of the Journal of Acquired Immune Deficiency Syndromes.
It is indicative of the current revolution in life sciences that Adleman, a mathematician, can poke his nose into biology and discover something important. "Sciences reach a point where they become mathematized," he says, coining a new phrase. This process begins at the fringes, but, at some point, the central issues in the field become sufficiently understood that they can be thought about mathematically. It occurred in physics about the time of the Renaissance; it began in chemistry after John Dalton developed atomic theory; and it is just now happening in biology.
"When I was an undergraduate in the '60s," says Adleman, "I thought biology was stuff that smelled funny in the refrigerator. Now, biology is finite strings over a four-letter alphabet and functions performed by enzymes on these strings."
As biology joins the ranks of other hard sciences, a tantalizing prospect opens up for Adleman. After going through an age of specialization, the sciences are now reuniting into a common mode of inquiry. "The next generation could produce a scientist in the old sense," he says, "a real generalist, who could learn the physics, chemistry, and biology, and be able to contribute to all three disciplines at once."
The key to this scientific renaissance is mathematics. "People speak of mathematics as the language of science," he says, "but to me, mathematics is the ultimate science.
It's weightless science. It's supersonic science. You can study entire universes inside your brain and complete an experiment the sec-ond you conceive of it." While waiting for the Galileo of the 21st century to discover the unified theory of everything, Adleman is doing a good job himself of connecting previously unrelated disciplines.
It was while trying to delve deeper into the biology of AIDS that Adleman found himself in bed reading the work of James Watson, co-discoverer, with Francis Crick, of the structure of DNA. Adleman was reading Watson's chapter on polymerase, the enzyme that reproduces DNA. Polymerase attaches to single-stranded DNA at a special site, and then proceeds to run down the strand, nucleotide by nucleotide, building a complementary copy as it goes. Adleman was struck by the idea that this biological process is nearly identical to the way computers work. "You could use DNA to compute," he says. "All you needed was to cut, paste, and copy DNA in the right order."
Deoxyribonucleic acid - DNA for short - is a molecule made by stringing together four nucleotides, or building blocks: A (adenine), T (thymine), G (guanine), and C (cytosine). DNA exists in virtually every one of our cells - we have about a pound of the stuff inside us. The fact that DNA zips itself up into helixes using four base pairs instead of two - like the 1s and 0s in silicon-based computers - is mathematically irrelevant. Both systems are equally good for encoding information. "DNA is essentially digital," says Adleman. This means it can count. "In a digital system, virtually any set of primitive operations will allow you to do a computation," he says. "It's just a matter of putting them together in the right sequence."
Once he got the idea of using DNA to compute, Adleman had to think of a problem for it to solve. Hamilton's traveling salesman was the ticket. Could DNA find a single itinerary that would allow our airborne entrepreneur to travel efficiently through seven cities with fourteen interconnecting flights? A simplified version of Adleman's experiment, using four cities instead of seven, looks like this: Atlanta, Baltimore, Chicago, and Detroit are the four cities in question. Nonstop flights can be taken between the following:
Atlanta - Chicago
Chicago - Detroit
Chicago - Baltimore
Baltimore - Detroit
Starting in Atlanta and ending in Detroit, can one find three sequential flights that take you through all four cities? The answer is "Yes." You fly from Atlanta to Chicago, from Chicago to Baltimore, and from Baltimore to Detroit. Any child good at crossword puzzles can solve this problem. The question is: Can DNA? If it can, then you throw a few more cities into the equation (making the problem too hard for the world's fastest supercomputers) and watch DNA do some really amazing computations. But let's return to our simplified four-city example.
A DNA name comprised of six letters was assigned to each city, chosen at random from the four-letter DNA alphabet. (Adleman actually used 20-letter names).
City DNA Name
Flights between cities were assigned a DNA flight number. This number was created by combining the last three letters from the DNA name of the originating city with the first three letters from the DNA name of the destination city:
FLIGHT DNA NAMES DNA #
Atlanta-Chicago ATGCGAGCTTAG CGAGCT
Chicago-Detroit GCTTAGGTCCGG TAGGTC
Chicago-Baltimore GCTTAGCGATCC TAGCGA
Baltimore-Detroit CGATCCGTCCGG TCCGTC
Every strand of DNA has a complementary strand made by substituting T for A, G for C, and vice versa. (A can only link with T, G only with C.) When these complementary strands get near each other, they stick together. This is what gives DNA its double-stranded spiral structure. Each city then has a complementary DNA name:
CITY DNA NAME COMP. DNA NAME
Atlanta ATGCGA TACGCT
Baltimore CGATCC GCTAGG
Chicago GCTTAG CGAATC
Detroit GTCCGG CAGGCC
Genetic engineering, with its snip-and-clip methodologies, makes it easy to design molecules with a desired sequence. Employing these techniques, Adleman synthesized 30 trillion molecules for each of his seven cities and another 30 trillion molecules for each of the 14 routes. When thrown into a test tube holding a fiftieth of a teaspoon of aqueous solution, these 60 trillion DNA sequences stuck together; they formed long chains of DNA flight numbers "splinted" together by DNA complements.
DNA FLIGHT # DNA FLIGHT #
COMPLEMENTARY DNA NAME
Remember, the goal of this abbreviated experiment is to find a flight path, starting in Atlanta, ending in Detroit, that connects all four cities and passes through each of them only once.
After every genetic strand is splinted with its complement, the answer is contained in the string of DNA letters (a molecule) that meets the following requirements. It must begin with the DNA flight number for a connecting flight out of Atlanta (CGA). It must end with the DNA flight number for a connecting flight into Detroit (GTC). And it must contain the DNA names of all the intervening cities, in a sequence that solves the problem. But one hurdle remains.
"Hey, waiter, there's a Hamiltonian path in my soup!" Adleman jokes about the difficulty of fishing this winning molecule out of his test tube.
Employing techniques ranging from affinity separation to polymerase chain reaction, he flushed out all the molecules from his test tube that either started in the wrong place, ended in the wrong place, were too long, too short, or otherwise defective in representing a winning itinerary. Free of molecular misfits, Adleman was left with strings of DNA molecules in whose alphabet was encoded the solution to his problem.
Although it took only a second to fill his soup with Hamiltonian paths, it took a week to fish them out.
Because of the massively parallel reactions involved in biochemistry (molecules working together at the same time), Adleman's DNA computer, in terms of the number of operations performed by its trillions of molecules, was a hundred times faster than the best of today's serial supercomputers. Its energy consumption was a billion times more efficient than electronic computers, and its storage capabilities were a trillion times denser than the best of today's storage media, such as videotape. But clearly this was a technology in dire need of some automation; we have to get better at fishing Hamiltonian paths out of our soup.
Adleman published his findings in the November 11, 1994, issue of Science magazine, where his article provoked a rash of adulatory comments. "It's more than just cute," explained Ronald Graham, adjunct director of information science at Bell Laboratories in New Jersey, to a newspaper reporter in late 1994. "It makes you think in a different direction."
Other scientists marveled that a guy working alone and outside his normal discipline had suddenly invented a new kind of computer. To highlight the importance of Adleman's work, Science ran an editorial alongside his article. Written by David Gifford, a computer scientist at the Massachusetts Institute of Technology, it lauded Adleman's experiment as the first step in a process that "will revolutionize the way we think about both computer science and molecular biology."
Gifford was rather more reserved when I phoned him in April at MIT and asked him to comment on Adleman's molecular computer. "It's not a molecular computer," he says, straight off. "Adleman's technique can only solve certain kinds of combinatorial problems. It is not a universal or programmable computer like an IBM PC."
Due to the remarkable speed at which this new field is advancing, Gifford's reservations are now moot. The breakthrough needed to build a universal molecular computer has already been made. At a small math conference in Santa Fe, New Mexico, in the fall of 1994, Adleman was chatting about his work with good friend Richard Lipton, a computer scientist at Princeton; Lipton saw immediately what had to be done next. By December, he'd authored a paper, which instantaneously became both the blueprint and manifesto for universal molecular computing. Called "Speeding Up Computation via Molecular Biology," Lipton's paper, so far, has been "published" only on the Internet (from ftp://ftp.cs.princeton.edu/pub/people/rjl/bio.ps).
And Lipton's breakthrough? He invented a coding scheme for translating DNA base pairs into strings of 1s and 0s. He also came up with some innovative techniques for stirring the genetic soup. Something as simple as pouring together the contents of test tubes filled with genetically sequenced molecules allows DNA to simulate the electronic gates by which computers make their yes-no decisions.
In one stroke Lipton had endowed molecular computers with Boolean algebra - the process computers use for "thinking." Named after the mid-19th-century British mathematician George Boole, this form of symbolic logic, which offers simple rules for decision making, is the foundation on which modern computer technology is built. DNA soup, retrofitted with symbolic logic, can now puzzle out the answers to a wide variety of computational problems, which, theoretically, makes it as universal and programmable as any personal computer.
So what will this DNA computer look like? "It will fill a bathtub, not the universe," says Lipton, "and it will be incredibly cheap to build." A pound of DNA in 1,000 quarts of fluid, about three-feet square, will hold more memory than all the computers ever made. The chemicals are inexpensive; DNA runs virtually on its own power, and the soup, with a little splicing, can be reused from one experiment to the next. Lipton estimates that a superparallel DNA computer, offering trillions of processors working simultaneously, could be built for $100,000.
In April of this year, when Adleman planned a trip to the East Coast to lecture on DNA computers at Columbia University, Lipton seized the moment to send out a message on the Net calling scientists to an impromptu daylong seminar at Princeton that would feature Adleman.
Two hundred researchers showed up and turned the gathering into a landmark conference on molecular computing. They were bubbling over with enthusiasm for applying molecular computers to everything from architectural design and the invention of new drugs to cryptography and quantum mechanics.
The catchiest presentation at the conference came from Lipton and two of his graduate students, Dan Boneh and Christopher Dunworth. They have designed a DNA computer they believe is capable of cracking the federal Data Encryption Standard (DES). This cryptographic algorithm is used to encode government information and other national secrets. Using a genetic attack, the Princeton researchers have discovered a method of decrypting the DES in three months. They jokingly call their yet-to-be-published paper "DNA Hackers."
Inspired by Lipton's breakthrough, Adleman followed up his Science article with a second paper, "On Constructing a Molecular Computer," (found at ftp://usc.edu/pub/csinfo/papers/adleman/molecular_computer.ps ). Here, Adleman envisions souped-up DNA computers running a million times faster than the fastest of today's supercomputers. He also foresees the invention of hundreds of new kinds of computers - chemical, catalytic, organic, inorganic.
Lipton published a landmark paper of his own in the April 28, 1995, issue of Science.
He extended the huge parallelism of DNA computers to another set of previously unsolved problems in Boolean logic known collectively as the Satisfaction Problem. The editorial preface to Lipton's article credited him with creating a "search machine" capable of sorting through "astronomical numbers of possible answers in search of the correct one. This involves searching a universe of solutions so large it would defeat any conventional computer."
All computers are special-purpose computers. They are skilled at solving certain - but not all - kinds of problems. Electronic computers, which might more aptly be called sequential computers, are good at solving long, thin problems - ones that require a large number of operations, one after the other. Molecular computers, on the other hand, are good at solving problems that are wide and short and can be decomposed into a huge number of tasks, each one requiring just a few steps to solve.
We all carry a computer good at solving problems that lie somewhere between the long and the wide - our brain. It has a trillion processors working at a couple of hundred operations per second. This is fewer processors than the massive parallelism available in a DNA computer, and those processors are working far slower than the processors of a supercomputer. Still, the brain is endowed with a rich connectivity that makes it excellent at solving a particularly complex and challenging kind of problem: how to live in a complicated world.
In Adleman's mind, almost everything around us, from soup to nuts, can be turned into a computer. "At one extreme, you can view everything in the world as a computation," he says. "The universe and its interactions might be thought of as some huge cellular automaton involved in its own peculiar form of computation."
By forcing the connection between computers and life, Adleman is making us rethink the meaning of both. Clearly, we have a lot of figuring left to do - but we also have new means for doing it.