DNA AND MOLECULARCOMPUT INGNatasha Jonoska, cha i r

Algorithmic Self-Assembly of DNA Tiles and its Application toCryptanalysis

Olivier Pelletier1

1Accenture Technology LabsSophia Antipolis, France

Olivier.Pelletier@accenture.com

Andr�e Weimerskirch2;1

2Electrical Eng. & Information Sciences Dept.Ruhr-Universit�at Bochum

Bochum, Germanyweika@crypto.ruhr-uni-bochum.de

Abstract

The early promises of DNA computing to de-liver a massively parallel architecture well-suited to computationally hard problemshave so far been largely unkept. Indeed, it isprobably fair to say that only toy problemshave been addressed experimentally. Re-cent experimental development on algorith-mic self-assembly using DNA tiles seem too�er the most promising path toward a po-tentially useful application of the DNA com-puting concept. In this paper, we explorenew geometries for algorithmic self-assembly,departing from those previously described inthe literature. This enables us to carry outmathematical operations like binary multi-plication or cyclic convolution product. Wethen show how to use the latter operation toimplement an attack against the well-knownpublic-key crypto system NTRU.

Keywords: DNA, self-assembly,

multiplication, convolution product,

cryptanalysis, NTRU, Wang tiles

1 Introduction

Since the seminal work of Adleman on the Travel-ing Salesman Problem (TSP) [2], DNA computing hasreceived a lot of attention both from a theoreticalpoint of view [6] and from an experimental perspec-tive [10, 7]. By using the DNA molecule as a carrier ofnon-genetic information, and biochemistry as a way toprocess this information, it is possible to build a mas-sively parallel computing architecture. The implemen-tation details vary from one experimental approach toanother, but it is certainly fair to describe the over-whelming majority of the reported experiences in thefollowing way: DNA molecules are used to represent

potential solutions and biochemical reactions are usedto test whether these solutions satisfy or not the crite-ria for being an actual solution of the problem. Eventhough a single biochemical step can take as much asone day to perform, the number of solutions testedin parallel is of the order of the Avogadro number(that is 1023 molecules), opening interesting compu-tational perspectives. Several authors have describedhow DNA computing could be used to solve diÆcultproblems like boolean satis�ability [6]. Adleman him-self has proposed an application to crack the DES en-cryption scheme [1]. DES is a standard symmetricencryption algorithm with a key of 56 bits, and a fewtest tubes of DNA would be enough to carry out abrute force attack on this cipher. Unfortunately, theseapproaches su�er from a number of drawbacks: (1)they are not always easy to implement in biochemistry,especially because they require puri�cation steps; (2)they rely essentially on brute force because they do noteasily make use of additional information that mightbe available about the problem. The price to pay formassive parallelism is a restricted exibility in "pro-gramming" the DNA molecules. For cryptographic ap-plications, this means that the "traditional" approachcannot take advantage of the known attacks on theweaknesses of a given algorithm.

Mao et al. [8] have recently shown that some de-gree of exibility can be introduced in DNA computingwhile retaining the intrinsic advantage of massive par-allelism. For that purpose they used DNA tiles thatare a biochemical implementation of the mathematicalconcept of Wang tiles [15]. We will describe these ob-jects in more detail in Section 2. SuÆce it to say fornow that the algorithmic self-assembly of Wang tilesis Turing Universal and that Mao et al. demonstratedthe experimental feasibility of this concept. We feelthat it is therefore appropriate to investigate in moredetail to what extent the algorithmic self-assembly ofDNA tiles can be used to solve problems that couldnot be practically solved using the "traditional" ap-

DNA AND MOLECULAR COMPUTING 139

proach based on the self-assembly of linear DNA. Inwhat follows, we demonstrate in particular that binarymultiplication and cyclic convolution product are rel-atively straightforward to implement (Section 3). Fur-thermore, we show that the practical implementationof our ideas requires the creation of a �nite numberof tiles well within the reach of current combinatorialchemistry. Finally we discuss how our ideas could beused to implement a cryptanalytic attack on the well-known public-key crypto system NTRU (Section 4).

2 Algorithmic Self-Assembly

2.1 Wang Tiles

The concept of algorithmic self-assembly is closely re-lated to that of Wang tiles. Wang showed that squaretiles with colored edges can emulate a Turing machine,if they are allowed to assemble in a way that wouldcover the plane, according to additional rule that edgesof the same color have to face each other [15]. This canbe intuitively understood by thinking of a given rowof tiles as representing a state of the Turing machinewhile the color encoding plays the role of the matchingrules. This shows that computing using Wang tiles isuniversal [16, 13].

2.2 Physical Implementation of Wang Tiles

Recent advances in the �eld of materials science haveenabled the experimental study of algorithmic self-assembly (abbreviated as ASA in the following). The�rst system, studied by Rothemund [12], was made oftiles whose edges were coated with materials of dif-ferent hydrophobicity. The error rate was found tobe unacceptably high, even though some expected dis-tinctive features were observed. We remark that thehydrophobic/hydrophilic interaction used in these ex-periments was probably not speci�c enough to enforceproper edge matching (despite some very clever \ad-hoc" tricks used by the author). More recently Mao etal. [8] have shown that nanoscopic tiles can be man-ufactured using DNA that are the molecular equiva-lent of Wang tiles. These \Triple Crossover" tiles aremade of several strands of DNA interwoven to create asquare body made of DNA double helixes with single(reactive) strands of DNA sticking out from each edgeof the tile. In the following we will refer to those sin-gle strands of DNA as sticky ends because they havethe ability to bind to their Watson-Crick complement.This mechanism corresponds to the color matchingrule in the abstract Wang tiles system. The exper-imental investigation focused on the XOR operationof two binary strings. The size of the problem wasstill relatively small, but the result turned out to be

promising, with an error rate that was less than 2%.Therefore DNA seems to be the material of choice toimplement ASA on a wider scale. Indeed, materialsscientists have achieved a high degree of control overthe nanostructures that can be built using DNA, andthe interaction between single strands of DNA seemsto be speci�c enough to enable a self-assembly with anacceptable error rate.

2.3 Our Perspective: Algorithmic

Self-Assembly for Practical Problems

Even though ASA is universal, it does by no meansfollow that any problem can be practically addressedby this approach. Indeed, traditional DNA computingis also universal but, as mentioned above, the quantityof materials needed to perform a calculation preventsit to be used for anything but toy problems. Why isthere any reason to believe ASA is a more interestingapproach? The answer lies in the fact that DNA tilescan be more easily \programmed" to incorporate theconstraints of a given problem. It is therefore possibleto exercise some degree of control over the biochemicalreaction occurring in the test tubes, thus avoiding theconsiderable waste of materials that characterize thetraditional approach. Given the recent experimentaldevelopments mentioned above, we believe it is timelyto re ect on the best use that could be made of ASAfor practical purposes. Our approach is resolutely con-structive: we try to provide examples where ASA turnsout to be a practical way of solving otherwise diÆcultproblems. This means that we have to depart fromthe only geometry that has been studied so far (squarewith four sticky ends). We give examples where a big-ger number of sticky ends or a self-assembly not con-strained to proceed in a plane turn out to be advanta-geous. To use a very bold analogy, this is reminiscentof the common situation in traditional computer sci-ence where a problem is straightforward to program ina given language (say C) while it is hard to address inanother one (say assembly) 1.

3 Mathematical Operations in DNA

In this section we describe how to perform mathemati-cal operations in DNA for two examples. First we showhow to execute a multiplication in 2D. Then we intro-duce a method to carry out ASA in three dimensionsto execute a cyclic convolution product. We give anabstract overview of each operation, and then go moreinto details. Note that we did not do any practicalexperiments.

1The analogy breaks down pretty quickly as one tries togive it a more formal shape, but we hope it is still usefulto carry our message.

DNA AND MOLECULAR COMPUTING140

3.1 Multiplication

We implement the schoolbook method as shown in Fig-ure 1. As example we use a multiplication of two 3-bitnumbers. The binary input is given as vectors a and b

with result r as sum of the corresponding rows underrespect of carry overs. The spatial layout of the DNAafter self-assembly is very similar to that of electroniccircuits carrying out the same function [9].

(a2 a1 a0) x (b2 b1 b0)

a0 b0a1 b0a2 b0

a0 b1a1 b1a2 b1

a0 b2a1 b2a2 b2

r0r1r2r3r4

+

+

=

Figure 1: Multiplication schoolbook method.

Figure 2 depicts the basic DNA tiles that are needed.Tile (1) is used for the actual execution. The originalbinary operand values are represented by a and b whiles and c represent the intermediate sum and carry over,respectively. The result of this elementary operation,intermediate value and carry over, are denoted by s

0

and c0. It follows that

c0 = (ab+ c+ s)=2; s0 = (ab+ c+ s) mod 2

where integer division is used. There are 16 di�erentinput values determining the number of di�erent tilesof this kind. Tiles (2) and (5) are used to representoperand bits. The connection to the next and previousinput tile is denoted by j, while the �nal result of acolumn is connected at r. Tile (3) represents a resultbit which will connect to the sticky end r of inputtile (5) and the sum s

0 of tile (1). Furthermore weuse frame tiles to limit the physical expansion of theexecution. Frame tile (4) forwards the carry over valuec to the next left column. Further auxiliary tiles areused (start and end).

Figure 3 shows the arrangement of the DNA tiles toperform a multiplication. Note that we pad the secondoperand b with 0-bits to make reading of the resulteasier, and that the result tile connected to b0 is notpart of the result. The body tiles are denoted by v

i;j,

input tiles as aiand b

jrespective, and frame tiles by

F . Extra tiles are needed as starting and end point,denoted as S andE. We understand that di�erent kindof tiles need di�erent sticky ends to avoid ambiguity.However, there are enough combinations available [4].It is clear that this method can be applied to biggeroperands, and that it does not require the operands tohave the same length.

So far we have assumed that linear assemblies of input

Body Input

InputFrame

(b,c)

as

(b,c')

a

s'

a

c

c

0

s'

r

rj

(b,0)

j

j

j

jj

1. 2. 3.

4. 5.

Figure 2: DNA tiles for multiplication.

Sa0a1a2

b0

b1

b2

0

v0,0v1,0

v0,1

v0,2

r3

r4

F

F

F

EFFFE

F

F

v2,0

v1,1v2,1

v1,2v2,2

r40

00

E

r0

r1

r2

r3

r4

0

Figure 3: Multiplication in DNA.

tiles could be readily obtained. We now outline theway these inputs are \synthesized". Given a binarystring of N bits, we need 2N di�erent tiles indexedby their value (0 or 1) and their position within thestring (the DNA sequence connecting one digit to thenext one is of course unique for each pair of value andposition). Creating a given input simply consists inpicking out N such tiles with di�erent indices. Notethat, given the appropriate supply, if all the 2N tilesare mixed together it is possible to obtain the 2N possi-ble binary strings in a combinatorial fashion. By usingnon-identical concentrations for the two possible val-ues at a given position, it is also possible to induce aprobability distribution on the input strings. All in all,prior to any calculation involving two strings of lengthm and n, we need to synthesize sets of m+n di�erentinput tiles2, 16 body tiles, 4 + 2 frame tiles, 2 resulttiles, 3 end tiles, and 1 starting tile. Once the inputstrings have been synthesized our scheme requires onlyone reaction step. All the basic types of tiles are mixedtogether and the self-assembly can proceed. Readingthe �nal result could be done using the reporter strandtechnique described in [8]. We note that in our case

2Note that combinatorial a and b requires B(m+n) tileclasses where B is the base of a and b, i.e., 2(m + n) forbinary representation.

DNA AND MOLECULAR COMPUTING 141

the reporter strand would have to run through the en-tire 2D lattice. Alternatively, one could imagine thateach result tile would have a sticky end running per-pendicular to the plane of self-assembly. This wouldallow the formation of a linear self-assembled structureabove this plane, that could be used to produce a re-porter strand whose size would scale linearly with thesize of the solution3. Thus, even in the worst case, ourmultiplication scheme requires only two reaction stepsand the number of di�erent tiles required is growinglinearly with the size of the problem.

3.2 Cyclic Convolution Product

After showing an example of ASA using relativelycomplex tiles to produce a straightforward 2D self-assembly, we now introduce an operation which can beperformed more conveniently in 3 dimensions. Firstwe de�ne the cyclic convolution product. Let F =P

N�1

i=0Fixi = [F0; : : : ; FN�1] be a polynomial or a vec-

tor of length N . Then the cyclic convolution product? of two vectors of length N is de�ned as [5]:

A ? B = C with

Ck

=

kX

i=0

AiBk�i +

N�1X

i=k+1

AiBN+k�i

=X

i+j�k mod N

AiBj

The ? multiplication modulo q means that the coeÆ-cients C

kare reduced by q. From now on we will focus

on the modulo product. Figure 4 gives a geometri-cal description of the convolution product. The inputoperands are the vectors a and b. The x and y axis de-scribe the index of the operand bits. The �gure showsthe index k of c

kto which a

ibjcontributes. By re-

peating the input vector a the result coeÆcient ckcan

easily be obtained by adding the diagonal elements.

00

1

10

2

2

2

1

3

3

3

0

00

00

00

0

11

11

11

11

22

22

22

22

33

33

33

33

a

a

b

Figure 4: Geometrical description of convolution prod-uct.

3Note that the �rst \dummy" result tile comes in handyas a PCR primer.

We execute the convolution product in DNA accordingto the geometry just outlined. First we assemble the el-ementary multiplications in a \ground layer", then wegrow the crystal to the third dimension to obtain theresult. Figure 5 describes the body tile of the groundlayer. It has two input ends a and b, forwards theinput to the opposite side, and outputs the value ab

using a sticky end pointing in the direction perpen-dicular to the plane of self-assembly 4. Figure 6 showshow the ground layer is built. Again we use input tiles,frame tiles, and start and end tiles. Note that the �rstoperand a is �xed since it has to be repeated.

ab

a

b

b

a

Figure 5: Body tile for convolution product.

S b0 b1 b2 b3 E

a0

a1

a2

a3

a0

a1

a2

a3

E FF F F E

F

F

F

F

F

F

F

F

c3

c2

c1

c0

c3

Figure 6: Cyclic convolution product in DNA.

To add the coeÆcients, we use bridges which are as-sembled for each layer beforehand. The implementa-tion of the bridges ensures that the result coeÆcients

4It is depicted as a circle in Figure 5.

DNA AND MOLECULAR COMPUTING142

are modulo reduced. The bridges are built using con-nectors to the lower layer, a connector to the nextlayer, and spacer tiles5. Bridges broken down into theirconstitutive tiles are shown in Figure 7.

groundlayer

ck

1st layer

2nd layer

Figure 7: Bridge to add the coeÆcients.

The three dimensional arrangement of the bridges isshown in Figure 8. The bridges are arranged on topof the ground layer as outlined in Figure 6. The darkgrey connections represent bridge connections in the�rst layer, while the light grey connections stand forsecond layer bridges.

groundlayer

1st layer

2nd layer

c0

c1

c2

c3

Figure 8: Bridges in the 3D space (connections in theground layer are not pictured for simpli�cation).

To simplify the bridge building operation we assumethat the operands have a length which is a power of 2.To force the bridges to operate along the appropriatediagonal, it would be necessary to use a 2D lattice witha lower symmetry than the square symmetry used forconvenience in Figure 6 6. The result of the operationcan now be read at the sticky ends of the uppermostlayer. The coeÆcient C

N�1 appears twice and has

5whose number depends on the layer underconsideration

6To prevent that bridges are attached to the wrong tilessuch that at some sticky ends there is no bridge attachedat all one could use input tiles for a with alternate lengthin between.

to be ignored once. The diagonals which we do notconsider will not assemble up to the highest layer.

Note that input coeÆcients are integers instead ofbinaries. Therefore the number of tiles needed ismuch larger than for the multiplication. Let a

i2

f0; : : : ; s � 1g and bj2 f0; : : : ; t � 1g. Synthesis of

the input tiles requires 2N + N tile classes. Fixeda and combinatorial b requires 2N + tN tile classesthough. Including start, end, frame, input, and bodytiles we need 1+3+4+2N+N +st = 8+3N+st tileclasses for the �rst layer. Remember that the bridgetiles perform addition modulo q. Therefore we need q

2

di�erent bridge combinations, i.e., q2 connector tiles tothe upper layer and 2q connectors to the lower layer.Furthermore we need spacer tiles to build the bridges.Assuming that q is considerably larger than s and t

the number of di�erent tiles is in the order of q2 evenfor combinatorial b. If N = 2x then our structure willconsist of x+1 layers including the ground layer. Eachlayer will be grown one at at time, using bridges withthe appropriate spacing. The �nal result will thereforebe obtained in x+ 1 steps.

3.3 More Practical Considerations

The �rst problem that needs to be addressed is thatof the error rate during a computation. Theoreticalconsiderations taking into account the thermodynam-ics of the system are clearly outside of the scope ofthis paper, and we will therefore only lead a qualita-tive discussion. The process of self-assembly withina plane, that we use for our multiplication schemeand as the �rst step in our cyclic convolution prod-uct, is in essence very similar to the construction ofMao et al. for their XOR product. It is therefore likelythat an experimental error rate below 2% could be ex-pected. Much higher error rates could be expected forthe building of the successive layers in our convolutionproduct because cooperativity is much lower in this di-rection (the number of neighbors is much lower whichmeans less constraints). This would probably requirethe interaction energies between the sticky ends in thisdirection to be relatively high, in order to give a max-imum energetic penalty to possible \orphan" stickyends.

Any reader familiar with materials science will prob-ably already have more than a few objections to ourclaims. Indeed, we must acknowledge that, to date,no DNA tile has been synthesized that could be usedto implement our schemes directly. To what extentthis will be true in the future is of course absolutelyimpossible to tell. We will simply refer the reader tothe recent work accomplished by the group of Seeman[11] on the creation of DNA-based nanostructures and

DNA AND MOLECULAR COMPUTING 143

let him decide for himself how far experimental sci-ence is from being able to implement our ideas. We donot believe that our computation schemes alone wouldbe enough to motivate the considerable experimentalwork required to investigate the 3D ASA of DNA. Butwe should note that this technique is also very promis-ing for the much more researched problem of proteincrystallization. It is therefore not completely utopic toexpect experimental progress on that front. Also, eventhough the total number of di�erent types of tiles to besynthesized is not overwhelming and certainly withinthe reach of combinatorial chemistry techniques, evenfor operations on binary numbers of a few hundredbits, it remains to be seen which incentive an experi-mentalist could have to perform such an experiment.That's why we devote the next section of this articleto show that it might be possible to implement an at-tack on a strong public-key crypto system using ourstrategy for the cyclic convolution product.

4 Application to Cryptography

In the mid 90's it was shown that DNA computingcan be applied to break DES [3, 1]. These methodsare based on a brute force attack. Using the parallelnature of DNA computing all possible keys are tested.For symmetric encryption ciphers like DES a bruteforce attack often is the only practical attack due tolimited knowledge. However, for public-key methodsbrute force attacks are usually far out of computingpower range because the key length is chosen accordingto the best known attack. which requires much lesse�ort than brute force. DNA attacks are limited by thecomplexity of an attack step and the amount of DNA.In the following we will present the public-key systemNTRU and a simple brute force attack in DNA. Thenwe present the execution of an attack on NTRU whichreduces the amount of DNA by the square root. DNAtiles provide the appropriate exibility to implementboth attacks.

4.1 Overview of NTRU

4.1.1 Notation

In this section we will give a brief overview of NTRU.For further details see [5]. The NTRU system is basedon a ring R = Z =(XN�1) , three integers (N; p; q) andfour sets L

f;L

g;L

�;L

mof polynomials of degreeN�1

with integer coeÆcients. We assume that gcd(p; q) =1, and that q is considerably larger than p. ElementsF 2 R are written as a polynomial or vector

F =

N�1X

i=0

Fixi = [F0; F1; : : : ; FN�1]

Multiplication in R is done using the cyclic convolutionproduct ? as de�ned in Section 3.2. Multiplicationmodulo q means that the coeÆcients of the convolutionproduct are reduced modulo q.

4.1.2 Key Creation

Assume two entities called Bob and Alice who want toexchange messages over an insecure channel. First Bobchooses elements f 2 L

fand g 2 L

g. For simplicity

we assume that f has coeÆcients in f0; 1g and that ghas coeÆcients in f0; : : : ; s� 1g. The polynomial f ischosen such that it has exactly d coeÆcients of value 1and N�d coeÆcients of value 0. Bob computes f�1

q�

f�1 mod q and h � f

�1q

? g mod q. Bob's private keyis the polynomial f and his public key is h.

4.1.3 Encryption

To encrypt a plain text message m 2 Lmusing Bob's

public key h, Alice selects a random element r 2 L�

and computes the cipher text e � (r ? h+m) mod q.

4.1.4 Decryption

To decrypt the cipher text e using the private keyf , Bob �rst computes a � f ? e mod q where hechooses the coeÆcients of a in the interval from �q=2to q=2. Now Bob recovers the plain text message asm � (f�1 mod p) ? a mod q.

4.2 Brute Force Attack

The goal of the attack is given all parameters (N; p; q),the sets L

f;L

g;L

�;L

m, and a public key h to recover

the private key f . Let us assume that polynomialsin L

ghave coeÆcients in f0; : : : ; s � 1g. As before

any f 2 Lfhas d coeÆcients of value 1 and N � d

coeÆcients of value 0. An attacker can recover theprivate key by trying all possible f 2 L

fand testing if

g0 = f?h mod q has small entries, i.e., if the coeÆcientsare between 0 and s � 1. Similarly, an attacker cantry all g 2 L

gand test if f 0 = g ? h

�1 mod q hasonly coeÆcients 0 or 1. In practice, L

gis smaller than

Lf, so the security is determined by the number of

elements in Lg.

The attack can be implemented in DNA as follows.For all g 2 L

gcompute the cyclic convolution product

g ?h�1 mod q as explained in Section 3.2. Choose h�1

as the operand which is repeated. Use the massive par-allelism of DNA to compute the convolution product ofh�1 with all the possible g. Reading of the operation

result is done by the reporter strand method. Amongall the results, the one consisting only of 0 or 1 7 is the

7Remember that each digit of the result can take q

DNA AND MOLECULAR COMPUTING144

private key. To get it we need to run q � 2 separationsteps.

This attack does not scale up well. It is limited byq which determines the number of di�erent tiles. Atypical value for q is 64 or 128 [5] which means thatmore than 4,000 di�erent tile classes are needed. An-other restriction is given by the total amount of DNA.The number of DNA tiles to be used in the compu-tation cannot be expected to be much more than theAvogadro number (about 1023). Therefore this kindof attack is roughly limited to 280 di�erent possibili-ties for g. Since the coeÆcients of g are not limited tobinary values there can be 280 di�erent possible poly-nomials of length 64. Usually the key space is de�nedas the set of possible keys. In our case we extend thede�nition such that the key space is the set which isused for an attack, i.e., for NTRU this is usually L

g

since it is smaller than Lf. The key security is de-

�ned as the number of steps, or in our case di�erentinputs, that have to be performed or tried before thekey is found using the best known attack. The bestknown attack is shown in the next section and reducesthe e�ort by a square factor, i.e., the key security isthe square root of the number of elements in the keyspace. Thus we can break an NTRU system having akey security of 240 for a proper value s. However, atypical key security for NTRU in high security scenar-ios is about 280, i.e., L

ghas 2160 elements. In the next

section we give a future perspective how this can beachieved.

4.3 Meet-in-the-Middle Attack

The meet-in-the-middle attack reduces the e�ort to�nd the private key. Compared to a brute force at-tack this attack reduces the amount of DNA which isrequired for a successful attack by the square root, orin other words the key space which can be broken isquadratic in size. We will give a brief overview of theattack. Detailed information is given in [14]. Remem-ber that the private key f has exactly d ones and N�dzeros. The idea of the attack is to search for f in theform (f1; f2) where f1 and f2 each have d=2 ones andare N=2 in length. Then try all possibilities for f1 andf2 such that (f1; f2)?h mod q has coeÆcients between0 and s� 1. This can be done eÆciently as follows.

Choose at random N=2 of the N possible positionsin f . Assume that d=2 of these N=2 positions haveones in the actual private key f . The probability thatthis assumption holds is approximately 1 to

pd, so the

following has to be repeated aroundpd times before

f is found. Now relabel the positions such that thechosen N=2 positions determine the vector f1 and the

values.

other N=2 positions f2. The next step is to enumer-

ate over f1. Usually this takes only�N=2

d=2

�steps but in

DNA we probably have to iterate over all 2N=2 binaryvectors. Since d is chosen such that the key space isvery large the relative di�erence is very small. First(f1; 0) ?h mod q is computed and put into a bin basedon its �rst k coeÆcients. If the convolution producthas coeÆcients F0; : : : ; Fk�1 then it is put into a bin(Ij0; : : : ; I

jk�1) where I

ji� F

iare integer intervals.

The size of the intervals are determined by k. Thenall possible values for f2 are enumerated. The con-volution product �(0; f2) ? h mod q is put into a bin(J

j0; : : : ; J

jk�1) that is de�ned by intervals that are

slightly larger as the previous ones (each bin is ex-actly by s-1 larger). Finally the bins are compared. Ifthe assumption about the position of the ones in f inthe �rst step was right then there is a matching pairf1 and f2 such that f1 is in (I

j0; : : : ; I

jk�1) and f2 in

(Jj0; : : : ; J

jk�1), and the private key can be derived as

f = (f1; f2).

In DNA the attack is executed as follows. First chooseN=2 random positions in f . The marked positions arerepresented by f1 which is assembled using DNA tilessuch that the marked positions are chosen combinato-rial and the unmarked positions are set to 0. This caneasily be done by encoding the position into the DNAtiles that represent f1 as described before. Execute(f1; 0)?h mod q in parallel for all possible combinationsof f1 as explained in Section 3.2. The polynomial h isthe �xed operand which is repeated. Now constructDNA tiles for f2 in the same manner as before butset marked bits to 0 and iterate over unmarked bits,and execute �(0; f2) ? h mod q. To put a product intoa bin we use special DNA tiles with two sticky endsthat translate an integer value into the correspondinginterval. These tiles are di�erent for the two convolu-tion products in the sense that the interval sizes aredi�erent. Tiles for the �rst convolution product canconnect to tiles for the second product with the sameintervals, i.e., tiles representing I

jiwill be glued to

tiles representing Jji. Apply these tiles to the convo-

lution products. Assuming that the mobility of theDNA supra molecular assemblies is not too small, twoof them will stick together. If such a tandem struc-ture can be found the original assumption was right,and the private key can be determined by reading theinput tiles f1 and f2. The actual reading stage is prob-lematic here, as the reporter strand method likely doesnot seem to work. We suggest another approach wherethe DNA structures are �rst �ltered according to theirmolecular weight, and those corresponding to tandemunits are examined by atomic force microscopy8.

8If the recent developments in coupled NMR and AFMbecome mainstream, then reading could be done by coor-

DNA AND MOLECULAR COMPUTING 145

Assuming that a brute force attack can be mountedto break a key security of 240 the described meet-in-the-middle attack in DNA might break systems witha key security of 280. However, many assumptions arevery optimistic for the near future. Furthermore weunderstand that using a higher security level, e.g., akey security of 2285 as proposed in [5] puts public-keysystems like NTRU far out of range for a successfulcryptanalysis in DNA.

5 Conclusions

We have presented two computation schemes for thebinary multiplication and cyclic convolution productusing the algorithmic self-assembly of DNA tiles. Forthat purpose, we introduced new conceptual designsfor DNA tiles that should allow for a practical im-plementation of these operations. Indeed, we empha-size the fact that even though DNA tiles are by them-selves universal, tiles with di�erent designs will per-form very di�erently on a given problem: designinge�ective DNA tiles for a given computation can bethought as \DNA programming". The most interest-ing feature of our system of DNA tiles is that it turnsout to be exible enough to go beyond a simple bruteforce algorithm: it would indeed be possible to use itto implement an attack on a public-key crypto system.Among the open questions, we have to acknowledgethat we do not have any estimations on the expectederror rate. We are currently trying to address this is-sue.

References

[1] L.M. Adleman, P.W.K. Rothemund, S. Roweis, E.Winfree. On applying molecular computation tothe Data Encryption Standard. In Proceedings of

2nd DIMACS workshop on DNA based computers,held at Princeton University, USA, 1996.

[2] L.M. Adleman. Molecular Computation of Solu-tions to Combinatorial Problems. Science, vol.266, pages 1021{1024, 1994.

[3] D. Boneh, C. Dunworth, and R.J. Lipton. Break-ing DES using a molecular computer. Tech. Re-port CS-TR-489-95, Princeton University, USA,1995.

[4] U. Feldkamp, W. Banzhaf, H. Rauhe. A DNA Se-quence Compiler. In Proceedings of 6th DIMACS

Workshop on DNA Based Computers, held atUniversity of Leiden, Netherlands, 2000.

dinating atoms with very di�erent resonance frequencies tothe input tiles.

[5] J. Ho�stein, J. Pipher, J.H. Silverman. NTRU:A Ring-Based Public Key Cryptosystem. In Pro-

ceedings of ANTS III, vol. 1423 of LNCS, pages267{288, Springer-Verlag, 1998.

[6] R.J. Lipton. DNA Solution of Hard Computa-tional Problems. Science, vol. 268, pages 542{545,1995.

[7] Q. Liu, L. Wang, A.G. Frutos, A.E. Condon, R.M.Corn, L.M. Smith. DNA Computing on Surfaces.Nature, vol. 403, pages 175{179, 2000.

[8] C. Mao, T.H. LaBean, J.H. Reif, and N.C. See-man. Logical computation using algorithmic self-assembly of DNA triple-crossover molecules. Na-ture, vol. 407, pages 493{496, 2000.

[9] B. Parhami. Computer Arithmetic: Algorithms

and Hardware Designs. Oxford University Press,New York, 2000.

[10] Q. Ouyang, P.D. Kaplan, L. Shumao, A. Libch-aber. DNA Solution of the Maximal Clique Prob-lem. Science, vol. 278, pages 446{449, 1997.

[11] N.C. Seeman et al. New Motifs in DNA Nanotech-nology. In Proceedings of 5th Foresight Confer-

ence. To be published in Nanotechnology (2001).

[12] P.W.K. Rothemund. Using lateral capillary forcesto compute by self-assembly. In Proceedings of Na-tional Academy of Science, vol. 97n3, pages 984{989, 2000.

[13] P.W.K. Rothemund, E. Winfree. The Program-Size Complexity of Self-Assembled Squares. InProceedings of the Thirty-Second Annual ACM

Symposium on Theory of Computing, May 2000,Portland, USA.

[14] J.H. Silverman. A Meet-In-The-Middle Attack onan NTRU Private Key. NTRU Technical Report

#4, 1997.

[15] H. Wang. Proving theorems by pattern recogni-tion. II. Bell System Technical Journal, vol.40,pages 1{42, 1961.

[16] E. Winfree, F. Liu, L.A. Wenzler, N.C. Seeman.Design and Self-Assembly of two-dimensionalDNA Crystals. Nature, vol. 394, pages 539{544,1998.

DNA AND MOLECULAR COMPUTING146

A DNA-based three-state device

Bernard YurkeBell Laboratories

Lucent TechnologiesMurray Hill, NJ 07974

Friedrich C. Simmel∗

Bell Laboratories,Lucent Technologies

Murray Hill, NJ 07974

Abstract

A simple DNA-based nanomechanical deviceis presented which can be switched betweenthree different conformations by the addi-tion of appropriate signal molecules. Two ofthese conformations are mechanically rigid.The device consists of two arms formed bydouble-stranded DNA, connected by a single-stranded hinge. The device can be in a closedor stretched configuration, and in an inter-mediate relaxed state. The operation of thedevice is monitored by fluorescence resonanceenergy transfer and gel electrophoresis exper-iments. The closing of the supramoleculararms is affected by the salt concentration,probably due to electrostatic interactions ofthe device with itself.

1 INTRODUCTION

Its molecular recognition properties make DNA apromising molecule for the development of molec-ular nanotechnology. DNA has already been uti-lized to build a number of complex nanoscale struc-tures [1, 2, 3]. Moreover, in recent experiments theremarkable properties of DNA could even be used toinduce motion on a molecular scale [4, 5, 6, 7, 8, 9, 10].The basis for molecular engineering with DNA is the– under appropriate conditions – highly specific basepair (bp) recognition between the DNA bases adenine(A) and thymine (T), and between guanine (G) andcytosine (C) [11]. By the choice of base sequence, DNAstrands can be made “sticky” or non-interacting. The“programmability” of these interactions renders DNAparticularly interesting as a self-assembly molecule asit offers much more design freedom than availablein other self-assembly approaches [12]. In the caseof nanomechanical devices, the information-carrying

character of DNA is not only utilized for the assemblyof the devices but also as a means of addressing (andtherefore controlling) their conformational transitions.Here we present a simple DNA-based device which canbe switched between three different mechanical states.Starting from a relaxed intermediate conformation, thedevice can either be transferred to a stretched or to atightened state, depending on the “fuel” or “signal”strand added to it. From these configurations the de-vice can be returned to the original state, and there-fore this simple molecular machine can be controllablycycled through its different states. Earlier DNA con-structs like DNA tweezers [5], DNA actuator [6, 8] orDNA scissors [7] based upon the same operation princi-ple were switchable only between a flexible and a rigidconformation. A combination of tweezers and actuatorresulted in a three-state device (TSD) which could beswitched between two rigid and one flexible state [10].In the present work, we provide additional evidencefor the proper operation of this TSD. We also inves-tigate the influence of ionic strength on the differentconformations of the device and thereby demonstratethe flexibility of the relaxed state as opposed to therigidness of the stretched and the tightened state.

2 DESCRIPTION OF THE DEVICE

The three-state device in its relaxed conformationis assembled from the 40 nucleotide (nt) long DNAstrand Q and the 84 nt long strand R (Fig. 1). Qand R form two 18 bp long “arms,” connected by4 nt and 48 nt long single-stranded sections. The≈ 13.6 nm long arms are mechanically stiff elements onthis length scale, as they are considerably shorter thanthe persistence length of double-stranded DNA (about50 nm [13]). The single-stranded sections, however,are rather flexible [14]. During the device’s operationthe 4 nt section acts as a hinge, whereas the long 48 ntsection is used to address and induce the motion of the

DNA AND MOLECULAR COMPUTING 147

+

+

+

+

+

+

(a)

(b)

(c)

(d)

F2

QRF2F2

R

Q F1

QRF2

F1F1

QRF1

QRF1 QRF1

QR

QR F2F2

Figure 1: Schematic representation of the operationprinciple of the three-state device: (a) The TSD con-sists of two single strands of DNA, Q and R. Theyhybridize together to form two double-stranded armsconnected by a hinge and a long single-stranded sec-tion. The TSD is stretched by the fuel strand F1 whichhybridizes to the single-stranded part of QR. (b) Theremoval strand F1 can attach to an unhybridized sec-tion of F1 (depicted in gray) and remove F1. This re-stores the relaxed conformation. (c) F2 can hybridizewith QR in a different manner and thus close the armsof the device. (d) Similar to (b) the relaxed state canbe restored by the addition of F2.

TSD.

The conformational transitions of the TSD are de-picted in Fig. 1: The relaxed device (QR) can be trans-ferred into the stretched configuration (QRF1) withthe help of the 48 nt long fuel strand F1 (Fig. 1 (a)).As F1 hybridizes with the long single-stranded sectionof QR, the formation of the DNA duplex straightensthe TSD. In Fig. 1 (b) the TSD is returned to its re-laxed state. F1 is equipped with a short eight baselong section (drawn in gray) which does not hybridizeto QR. At this overhang section F1 can be attacked byF1 which is a strand complementary to F1. The fuelstrand F1 is removed from QRF1 by F1 in a processknown as “branch migration” [15]. In this process,both QR and F1 compete for binding to F1. Dur-ing branch migration, the branch point, at which thethree strands R, F1 and F1 meet, performs a randomwalk along R. When the branch point makes its firstpassage, the strand displacement process is completed

a b c d e f g h

Figure 2: Fluorescence image of the result of a 10%polyacrylamide gel electrophoresis run of the TSD andits components. DNA strands run from the top to thebottom of the gel; smaller complexes run faster. Lanes(a) and (h) contain strand Q, lanes (b) and (g) the re-laxed TSD (Q + R). Lane (c) contains the stretchedTSD (QR + F1). In lane (d) the fuel strand has beenremoved again (QRF1 + F1). In lane (e) the TSD isin its closed conformation (QR + F2). The band shiftis smaller than in lane (c) as F2 is shorter than F1.Finally, in (f) the closing strand has been removed torestore the relaxed state of the TSD (QRF2 + F2).Only complexes containing the fluorescently labeledstrand Q are visible in this image. The smears abovethe main bands are caused by multimerization prod-ucts. Several Q strands can be linked together by Rstrands and several QR complexes can be crosslinkedby fuel strands. This effect has been extensively dis-cussed in Refs. [5, 6, 8]

and the “inert” waste product F1F1 falls off the nowrelaxed TSD.

The tightening (or closing) motion of the TSD is shownin Fig. 1 (c). Here, a different 40 nt long fuel strandF2 is used which hybridizes to R in a manner reverseto that of the straightening transition. F2 pulls thetwo arms of the device close together. A short ring-like section of R is left unhybridized to facilitate theattack of the second removal strand F2 which again re-stores the relaxed configuration by branch migration(Fig. 1 (d)). Using the appropriate fuel and removalstrands, the TSD can be switched arbitrarily betweenits three conformations QR, QRF1, and QRF2.

3 METHODS

Oligonucleotides were synthesized, labeled and puri-fied by Integrated DNA Technologies, Inc. (IDT).The sequences for the strands can be found in ref-erences [6, 10]. The operation of the TSD is checked

DNA AND MOLECULAR COMPUTING148

QR QRF1

QRF2

Figure 3: The TSD operation is monitored with fluo-rescence measurements at three different salt concen-trations: The devices start in the relaxed configuration(QR). By the addition of fuel strand F2 they are trans-ferred into the closed conformation (QRF2). Fromthere, they are returned to state QR with the removalstrand F2. Subsequently, the TSD is brought into thestretched state QRF1 by the addition of fuel strandF1. Removal of this strand with its complement F1

completes one operation cycle. The changes in the flu-orescence levels are due to FRET and correspond tochanges in the separation between the fluorescent dyesattached to the arm of the TSD (see Fig. 1).

with gel electrophoresis and fluorescence resonance en-ergy transfer experiments. For the latter, strand Qis labeled at the 5’ end with the fluorescent dye TET(2’,4’,5’,7’-Tetrachloro-5(6)-carboxyfluorescein) and atthe 3’ end with TAMRA (N,N,N’,N’-Tetramethyl-5(6)-carboxyrhodamine) (symbolized by the black cir-cles and triangles in Fig. 1). TET and TAMRAform a fluorescence resonance energy transfer (FRET)pair [16] with a Forster distance R0 of approximately5 nm. The emission band of TET (the “donor”) andthe absorption band of TAMRA (the “acceptor”) over-lap and TET can transfer its excitation energy nonra-diatively to TAMRA. This quenches the TET fluores-cence. The energy transfer efficiency depends stronglyon the distance between donor and acceptor. At a

distance R0 between the dyes, the efficiency of energytransfer is 50%. To estimate dye separations, we usean experimentally obtained calibration curve [5, 17].For the FRET experiments, the relaxed devices are as-sembled by mixing stoichiometric amounts of 25 µMsolutions of strands Q and R in TE buffer (10 mMTris(hydroxymethyl)-aminomethane (Tris), pH 8.0,1 mM ethylene diamine tetraacetic acid (EDTA)) anddiluting these mixtures in reaction buffer to a fi-nal concentration of 1 µM. As reaction buffers weused TE buffer with added salt (TE/200 mM NaCl,TE/500 mM NaCl, TE/1M NaCl) or “physiologicalbuffer” (potassium phosphate buffer, pH 7.2, with[K+]=140 mM, [Na+]=10 mM and [Mg2+]=0.5 mM(intracellular values) [18]). The TSDs are switchedbetween their different conformations by the additionof stoichiometric amounts of 25 µM fuel or removalstrands, followed by rapid mixing. The fluorescenceof TET is excited with light from an Argon ion laser(λ = 514.5 nm) chopped at a frequency of 130 Hz.The fluorescence light is filtered with a 10 nm band-pass filter centered at 540 nm and detected with a Siphotodiode at the chopper frequency.

For the gel electrophoresis experiments, strands aremixed in stoichiometric amounts at a concentration of2.5µM in TE buffer. Polyacrylamide gels were castat a concentration of 10% and run at 10 V/cm andT = 20oC. To visualize the bands, the gels were illu-minated using the laser system described above andphotographed through a bandpass filter with a digitalcamera.

4 RESULTS

In Fig. 2 the result of a gel run in a 10% polyacry-lamide gel is displayed. The band shifts correspond tothe molecular weight changes of the TSD during itsoperation. Lanes (a) and (h) contain only strand Q,whereas lanes (b) and (g) contain the relaxed confor-mation QR. In the remaining lanes the TSD is cycledonce through its states: Straightened (lane c), relaxed(lane d), closed (lane e) and relaxed again (lane f).The band shifts visible on the gel image correspond tothe increase or decrease of the molecular weight of theTSD with the attachment or removal of fuel strands.

Typical FRET signals collected during the operationof the TSD are shown in Fig. 3 for three different saltconcentrations. The fluorescence of the device in itsstraightened conformation (QRF1) has been normal-ized to one, as this conformation is least influenced bythe salt concentration. In the straightened conforma-tion, the sample displays its maximum fluorescence, asin this state the two dyes are furthest apart from each

DNA AND MOLECULAR COMPUTING 149

other and therefore FRET is least efficient. In the in-termediate state (QR), TET and TAMRA are closerto each other, and therefore the fluorescence is partlyquenched. This effect is stronger for higher salt con-centrations. In the closed state QRF2, the two dyesare brought very close to each other, and thereforethe TET fluorescence is quenched most efficiently. Inthis conformation, the fluorescence of the device is alsolower for higher salt concentrations. However, its sen-sitivity is not as strong as for the relaxed state. Thetransitions between the conformations display secondorder kinetics with reaction half-times on the order oft1/2 = 10 s – 100 s. The reactions are generally fasterfor higher salt concentrations [19].

For possible biomedical applications it is importantto investigate whether nanomechanical devices as theTSD are operable under physiological conditions. Tothis end, a wide range of salt concentrations, pH val-ues and temperatures have been investigated. It isfound that the temperature dependence of the reac-tion kinetics exhibits the expected Arrhenius-like be-havior. The fluorescence signal changes are highestfor high (monovalent) ion concentrations and low tem-peratures, whereas they are relatively insensitive tochanges in the pH value [19]. For Fig. 4, the TSD hasbeen operated in physiological buffer at T = 37oC. Thehalf-times for completion of the reactions are compara-ble to the ones for the data presented above: The lowersalt concentrations slow the reactions down, whereasthe higher temperature speeds them up. The changesin the fluorescence intensity are considerably less un-der physiological conditions than at lower tempera-tures and higher salt concentrations.

QRF1

QRF2

QR

QRF2

0 5000 10000

0.7

0.8

0.9

1.0

Flu

ore

scence

Time (s)

QRQR

Figure 4: The TSD is also operable under physiologicalconditions (physiological buffer at T = 37oC). Underthese conditions the reaction kinetics and the fluores-cence signal levels are altered. Higher temperaturespeeds up the reactions; the lower salt concentrationshave the opposite effect. Also, the fluorescence inten-sity changes decrease with higher temperature.

5 DISCUSSION

The gel electrophoresis band shifts in Fig. 2 and thefluorescence changes in Fig. 3 are in full agreementwith the proposed operation scheme for the TSD fromFig. 1. From the fluorescence levels one can deducethe distances between the dyes for the different con-formations at different salt concentrations. In thestretched state their separation is 13.6 nm which isjust the length of a 40 bp double helix. In the relaxedstate the separations between the dyes are 8.2 nm,6.2 nm and 5.1 nm for sodium ion concentrations of200 mM, 500 mM and 1 M, respectively. In the closedstate the corresponding separations are approximately3.7 nm, 2.7 nm and 2.0 nm. This shows that at highsalt concentrations the device can be switched betweentwo rigid conformations which is a major improvementover earlier devices based on the same operation prin-ciple [5, 6]. These devices could only be switched be-tween one rigid and one flexible conformation. The

Figure 5: Model of closed TSD at low salt concen-tration. Reduced screening leads to mutual electro-static repulsion of the arms. This partly unzips thefuel strand F2 from R.

flexibility of the relaxed configuration would severelyconstrain the performance of the two-state devices ifoperated against an externally applied force. With thethree-state device and its two rigid conformations thislimitation is overcome. It can be expected that theTSD is capable of actually performing work against anexternal force if it is switched between the tightenedand stretched configurations. However, our results in-dicate that at low salt concentrations the closed stateof the TSD also becomes distorted. Due to the re-duced screening of electrostatic interactions at low ionconcentrations, the arms of the device begin to pushon each other and the distance between the arms in-creases. This explains the increase of the fluorescenceintensity in the closed state for low salt concentra-tions. At low enough salt concentrations, the mutualrepulsion becomes strong enough to break base pairs(Fig. 5). A quantitative treatment of this effect mightprovide a possibility to calibrate the forces generatedby the TSD. In the relaxed state, the reduced screen-ing at lower salt concentrations probably results in the

DNA AND MOLECULAR COMPUTING150

stiffening of the single-stranded section of strand Rwhich also pushes the dyes further apart.

The TSD is an example of a chemically addressablemolecular device. The fuel strands F1 and F2 canbe thought of as signal strands with which one canexternally control the conformational changes of thedevice. Based on this principle, more elaborate molec-ular devices could be developed which are capable of alarger number of conformational changes controllablein a similar fashion as the TSD. Alternatively, a pop-ulation of devices could be devised, which are capableof interacting with each other with the help of sig-nal strands. A possible application of this might liein the assembly of nanoscale components in a certainspatiotemporal order, e.g., the installation of molec-ular electronic components. Interacting DNA devicesmight also be used to construct chemical reaction net-works performing particular tasks. It has to be men-tioned that the construction of complex machines ornetworks faces similar problems as DNA-based com-putation: The number of machines (or conformations,interactions, etc.) is limited by the number of dis-tinct base sequences available which robustly assembleinto the correct structures without unwanted cross-hybridizations. Otherwise, incorrectly assembled de-vices, extensive crosslinking and high error rates inaddressing the devices will make an operation of themachines impracticable.

Apart from nanotechnology and molecular electronics,possible applications of DNA nanodevices can also befound in the biomedical area. Molecular devices couldbe used as drug delivery systems or biosensors. Withresults obtained in the field of DNA-based computing,one could even combine the mechanical operation ofthe devices with information processing activities. Thestable operation of our DNA devices under physiolog-ical conditions makes such a biomedical applicationquite plausible, even though for such an applicationthe usual problems of gene delivery would have to besolved first.

6 CONCLUSIONS

We have demonstrated the construction and operationof a DNA-based molecular device which is switchablebetween three different conformations. Two of theseconformations are mechanically robust. Due to thehighly charged nature of DNA, the device operationis strongly affected by changes in the salt concentra-tion of the reaction buffer. However, the device is stilloperable under physiological conditions.

Acknowledgments

Financial support by the Alexander von HumboldtFoundation through the Feodor Lynen program isgratefully acknowledged (F.C.S).

∗present address: Center for NanoScience and Sektion

Physik, Ludwig-Maximilians-Universitat, Geschwister-

Scholl-Platz 1, 80539 Munchen, Germany.

References

[1] J. Chen and N. C. Seeman, Nature 350, 631(1991).

[2] C. Mao, W. Sun, and N. C. Seeman, Nature 386,137 (1997).

[3] E. Winfree, F. Liu, L. A. Wenzler, and N. C. See-man, Nature 394, 539 (1998).

[4] C. Mao, W. Sun, Z. Shen, and N. C. Seeman,Nature 397, 144 (1999).

[5] B. Yurke, A. J. Turberfield, A. P. Mills Jr.,F. C. Simmel, and J. L. Neumann, Nature 406,605 (2000).

[6] F. C. Simmel and B. Yurke, Phys. Rev. E 63,041913 (2001).

[7] J. C. Mitchell and B. Yurke, DNA 7, Seventh In-ternational Meeting on DNA-Based Computers,Springer Lecture Notes in Computer Science, inprint (2002).

[8] F. C. Simmel and B. Yurke, DNA 7, Seventh In-ternational Meeting on DNA-Based Computers,Springer Lecture Notes in Computer Science, inprint (2002).

[9] H. Yan, X. Zhang, Z. Shen, and N. C. Seeman,Nature 415, 62 (2002).

[10] F. C. Simmel and B. Yurke, Applied Physics Let-ters 80, 883 (2002).

[11] V. A. Bloomfield, D. M. Crothers, and I. TinocoJr., Nucleic Acids, University Science Books,Sausalito (2000).

[12] J. J. Storhoff and C. A. Mirkin, Chem. Rev. 99,1849-1862 (1999).

[13] S. B. Smith, Y. Cui, and C. Bustamante, Science271, 795 (1996).

DNA AND MOLECULAR COMPUTING 151

[14] B. Tinland, A. Pluen, J. Sturm, and G. Weill,Macromolecules 30, 5763 (1997).

[15] I. G. Panyutin and P. Hsieh, Proc. Natl. Acad.Sci. USA 91, 2021 (1994).

[16] L. Stryer and R. P. Haugland, Proc. Nat. Acad.Sci. USA 58, 719 (1967).

[17] F. C. Simmel and B. Yurke, Proc. SPIE 4332,419 (2001).

[18] B. Alberts, D. Bray, J. Lewis, M. Raff, K. Robertsand J. D. Watson, Molecular Biology of the Cell,3rd ed., Garland Publishing, New York (1994).

[19] F. C. Simmel, B. Yurke, and R. J. Sanyal, sub-mitted to J. Nanosc. Nanotech. (2002).

DNA AND MOLECULAR COMPUTING152