Have scientists broken the principle of quantum uncertainty?

DNA computers - will tomorrow's computers work with DNA instead of silicon?


1 DNA computer - will tomorrow's computers work with DNA instead of silicon? by Stefan Lorkowski and Paul Cullen Silicon chips have been the basis for the development of increasingly powerful computers for over 20 years. Increasing the performance requires that the units of a chip are reduced in size and more components are accommodated in a smaller space. For physical reasons (quantum uncertainty, wavelength of electromagnetic radiation) miniaturization cannot be continued indefinitely. The ability to perform arithmetic operations on molecules could solve this problem and revolutionize computer technology. Nucleic acid molecules are information carriers that meet the requirements of performing arithmetic operations on a molecular level. In contrast to conventional computers, nucleic acid-based computers work in parallel and have four decision options instead of the two alternatives of a binary system. Adleman was one of the first scientists to deal with solving mathematical problems using nucleic acids (1). In Science magazine he published a solution to the "traveling salesman problem". Since then, the vision of a DNA computer has ceased to be pure science fiction. The mathematical problem of finding a route to a given place without visiting a place several times puts the most powerful computers to the test. It is common to all solution algorithms that the number of solutions, and thus the computing time, increases exponentially with the number of locations. Hence, even for today's computers, it is difficult to find solutions to such problems. For a computer working in parallel, the working time only increases linearly with the number of variables. To solve the puzzle, Adleman used DNA oligonucleotides O i made up of 20 bases with a random sequence. These oligonucleotides O i represented individual locations i of the trip. Then oligonucleotides O i were con-13 with 20 bases

2, which corresponded to the routes between two travel points. The first ten bases of the 5 'end of these oligonucleotides O i were identical to the last ten bases of the 3' end of the oligonucleotides O i and the ten bases of their 3 'end matched the first ten bases of the 5' end of the Oligonucleotides O i match (Fig. 1). The oligonucleotides Ô i complementary to the oligonucleotides O i were then mixed with the oligonucleotides O i. The hybridization products were ligated and the ligation products represented possible routes of travel. In a further step, the ligation products were amplified in a PCR in order to select solutions that did not have location 0 as the starting point and location 6 Fig. 1 Left: Possible solution to the problem of a traveling salesman for a travel route with seven locations (i = 0 Starting point and i = 6 end point): 0 1, 1 2, 2 3, 3 4, 4 5, 5 6. Right: an oligonucleotide O i is used for each of the travel locations i (O 2, O 3 and O 4 are shown for places 2, 3 and 4). Oligonucleotides O i are selected for the route between two locations (oligonucleotides for routes between locations 2 and 3 and locations 3 and 4 are shown). Oligonucleotides O i of individual locations overlap with oligonucleotides O i of adjacent travel routes, so that complementary oligonucleotides Ô i can hybridize with oligonucleotides O i of adjacent routes during the hybridization. 14th

3 as the end point of the trip. For this purpose, the primer for location 0 (oligonucleotide O 0) and the primer Ô 6 complementary to the sequence of the oligonucleotide at location 6 were used. The PCR products were separated in an agarose gel. Correctly sized bands (a seven coordinate travel route corresponds to a PCR product of 140 bases) were eluted. The eluate was then gradually purified using a biotin / avidin bead system. For this purpose, the oligonucleotides Ô i were coupled to beads. The eluate was successively purified with the seven fractions of the coupled oligonucleotides Ô i, so that at the end only PCR products remained in the eluate which contained all sequence segments O i. Finally, the eluate was amplified in 1 PCR batches, the primer O 0 and a primer Ô i being used in one reaction. The PCR products were a b c d e f g h i Fig. 2 Chessboard to illustrate the solution to the Springer problem with a DNA / RNA computer. separated in the gel. When traveling to seven locations, the amplification must produce products with a size of 40, 60, 80, 100, 120 and 140 bases. The solution to the problem can be determined by sequencing the largest band. 15th

4 This publication has inspired numerous scientists to come up with new approaches. In 1995, Baum developed ideas for the construction of storage media and databases on a DNA basis (2). Together with Boneh and Dunworth, Lipton developed a method to decode the data encryption standard system developed by the National Security Agency. The coding, which cannot be solved by binary computers due to possible solutions, can be solved with parallel DNA computers. Guarnieri et al. presented an algorithm in 1996 with which they could use DNA molecules to add two rational, non-negative binary numbers (3). The development of DNA computers continues to be a fascination. Publications in Nature and PNAS prove this. A working group led by Landweber and Lipton tried to solve a fundamental chess problem (4). This knight problem includes the question of how many positions two knights can be placed on a chessboard without being able to attack each other. With this problem, too, the number of solutions increases exponentially with the number of variables (number of fields). Since the Springer problem is difficult to solve with a mathematical approach, Landweber and her team constructed a system of 1024 nucleic acid strands with various combinations of RNA bases. Each strand of RNA represented a possible arrangement of the knights on the chessboard. To simplify the calculation, the playing field was reduced to nine fields. This reduced the number of possible combinations of jumpers from a few million on a conventional playing field to 512 arrangements. The group made a library that contained RNA molecules that represented all possible arrangements of the jumpers. A part of this library was hybridized with DNA molecules that corresponded to the presence of the knight on field a of the 3 x 3 chess field (Fig. 2). At the same time, the absence of the jumpers on fields f and h, which is necessary due to the presence of a jumper on field a, was caused by the addition of appropriate DNA molecules. After treatment with ribonuclease H to digest the ent- 16

5 standing RNA / DNA hybrids, the a / f and a / h arrangements of the jumpers were eliminated. In a second approach, DNA molecules corresponding to the absence of a jumper on field a were hybridized with part of the RNA library. After the RNase H treatment, all possible positions remained. Fig. 3 Calculation operations with a DNA computer immobilized on a substrate. of the first jumper in the eight remaining positions. The two reaction batches were mixed in order to combine all remaining positions of the jumpers. In order to eliminate the remaining arrangements, these reactions had to be repeated one after the other for fields b, c, d and f with the combined approach. After amplification, the PCR products were separated in gels. This resulted in band patterns that encoded solutions to the problem and could be read out directly. 17th

6 A research team led by Smith was able to produce a DNA computer that works with nucleic acids immobilized on a solid substrate (5). This could be the first step towards a DNA computer that can be connected to electronic components. Smith and his co-workers constructed a DNA computer that dealt with the satisfiability problem. This basically represents the same mathematical puzzle as the Springer problem, only in a more abstract form. Analogous to the RNA library used by Landweber and her colleagues, Smith et al. a library of DNA oligonucleotides that represented the wrong and right answers to your problem. The oligonucleotides were applied to a gold surface analogously to a DNA microarray for sequence or expression analysis. To eliminate the wrong answers, oligonucleotides were synthesized that represented correct answers and were complementary to the corresponding DNA molecules in the DNA library. First, the array was hybridized with DNA molecules that contained some of the correct solutions in the form of the complementary oligonucleotides. The partial solutions resulting from this criterion were detected as DNA / DNA hybrids. The remaining single-stranded nucleic acids (the wrong solutions) on the chip were cleaved by means of single-strand-specific exonucleases. The remaining double strands were denatured by heating and the array was again hybridized with DNA oligonucleotides which represented solutions based on a second criterion. Here, too, the remaining individual strands were split. After renewed denaturation, the array was used for further computing cycles until the chip was hybridized with all DNA molecules that represented solutions to the problem based on further criteria. After the last denaturation, there were only DNA molecules on the chip that met all the criteria, i.e. found a complementary DNA strand in each hybridization cycle (computing cycle). The remaining nucleic acids (the solutions) could be amplified and then identified by sequencing. 18th

7 Even if the performance of DNA computers is still far from the performance of today's computers with silicon technology, the calculating machines published so far represent promising approaches. The great advantage of nucleic acids as a storage medium is their high information density, which is far from that of a silicon chip and conventional storage media is superior. One gram of DNA contains as much information as CD-ROMs. The future will have to show whether improved processes can be developed that will make DNA-based computers and thus computing operations at the molecular level possible. Literature [1] Adleman, L. M. Molecular Computation of Solutions to Combinatorial Problems. Science 1994, 266: [2] Baum, E. B. Building an Associative Memory Vastly Larger Than the Brain. Science 1995, 268: [3] Guarnieri, F., Fliss, M., Bancroft, C. Making DNA Add. Science 1996, 273: [4] Faulhammer, D., Cukras, A.R., Lipton, R.J., and Landweber, L.F. Molecular Computation: RNA Solutions to Chess Problems. Proceedings of the National Academy of Sciences 2000, 97 (4): [5] Liu, Q., Wang, L., Frutos, A. G., Condon, A. E., Corn, R. M., and Smith, L. M. DNA Computing On Surfaces. Nature 2000, 403: Contact address: Stefan Lorkowski, Institute for Arteriosclerosis Research at the Westfälische Wilhelms-Universität Münster, Domagkstrasse 3, Münster, Telephone: /, Fax: / Paul Cullen, Ogham Diagnostics GmbH, Mendelstrasse 11, Münster 19