Synthetic molecular machines for active self-assembly : prototype algorithms, designs, and experimental study

Computer science and electrical engineering have been the great success story of the twentieth century. The neat modularity and mapping of a language onto circuits has led to robots on Mars, desktop computers and smartphones. But these devices are not yet able to do some of the things that life takes for granted: repair a scratch, reproduce, regenerate, or grow exponentially fast–all while remaining functional.

This thesis explores and develops algorithms, molecular implementations, and theoretical proofs in the context of “active self-assembly” of molecular systems. The long-term vision of active self-assembly is the theoretical and physical implementation of materials that are composed of reconfigurable units with the programmability and adaptability of biology’s numerous molecular machines. En route to this goal, we must first find a way to overcome the memory limitations of molecular systems, and to discover the limits of complexity that can be achieved with individual molecules.

One of the main thrusts in molecular programming is to use computer science as a tool for figuring out what can be achieved. While molecular systems that are Turing-complete have been demonstrated [Winfree, 1996], these systems still cannot achieve some of the feats biology has achieved.

One might think that because a system is Turing-complete, capable of computing “anything,” that it can do any arbitrary task. But while it can simulate any digital computational problem, there are many behaviors that are not “computations” in a classical sense, and cannot be directly implemented. Examples include exponential growth and molecular motion relative to a surface.

Passive self-assembly systems cannot implement these behaviors because (a) molecular motion relative to a surface requires a source of fuel that is external to the system, and (b) passive systems are too slow to assemble exponentially-fast-growing structures. We call these behaviors “energetically incomplete” programmable behaviors. This class of behaviors includes any behavior where a passive physical system simply does not have enough physical energy to perform the specified tasks in the requisite amount of time.

As we will demonstrate and prove, a sufficiently expressive implementation of an “active” molecular self-assembly approach can achieve these behaviors. Using an external source of fuel solves part of the the problem, so the system is not “energetically incomplete.” But the programmable system also needs to have sufficient expressive power to achieve the specified behaviors. Perhaps surprisingly, some of these systems do not even require Turing completeness to be sufficiently expressive.

Building on a large variety of work by other scientists in the fields of DNA nanotechnology, chemistry and reconfigurable robotics, this thesis introduces several research contributions in the context of active self-assembly.

We show that simple primitives such as insertion and deletion are able to generate complex and interesting results such as the growth of a linear polymer in logarithmic time and the ability of a linear polymer to treadmill. To this end we developed a formal model for active-self assembly that is directly implementable with DNA molecules. We show that this model is computationally equivalent to a machine capable of producing strings that are stronger than regular languages and, at most, as strong as context-free grammars. This is a great advance in the theory of active self- assembly as prior models were either entirely theoretical or only implementable in the context of macro-scale robotics.

We developed a chain reaction method for the autonomous exponential growth of a linear DNA polymer. Our method is based on the insertion of molecules into the assembly, which generates two new insertion sites for every initial one employed. The building of a line in logarithmic time is a first step toward building a shape in logarithmic time. We demonstrate the first construction of a synthetic linear polymer that grows exponentially fast via insertion. We show that monomer molecules are converted into the polymer in logarithmic time via spectrofluorimetry and gel electrophoresis experiments. We also demonstrate the division of these polymers via the addition of a single DNA complex that competes with the insertion mechanism. This shows the growth of a population of polymers in logarithmic time. We characterize the DNA insertion mechanism that we utilize in Chapter 4. We experimentally demonstrate that we can control the kinetics of this re- action over at least seven orders of magnitude, by programming the sequences of DNA that initiate the reaction.

In addition, we review co-authored work on programming molecular robots using prescriptive landscapes of DNA origami; this was the first microscopic demonstration of programming a molec- ular robot to walk on a 2-dimensional surface. We developed a snapshot method for imaging these random walking molecular robots and a CAPTCHA-like analysis method for difficult-to-interpret imaging data.

A computer-aided investigation of motion detection units in the fly

This work deals with two related areas: processing of visual information in the central nervous system, and the application of computer systems to research in neurophysiology.

Certain classes of interneurons in the brain and optic lobes of the blowfly Calliphora phaenicia were previously shown to be sensitive to the direction of motion of visual stimuli. These units were identified by visual field, preferred direction of motion, and anatomical location from which recorded. The present work is addressed to the questions: (1) is there interaction between pairs of these units, and (2) if such relationships can be found, what is their nature. To answer these questions, it is essential to record from two or more units simultaneously, and to use more than a single recording electrode if recording points are to be chosen independently. Accordingly, such techniques were developed and are described.

One must also have practical, convenient means for analyzing the large volumes of data so obtained. It is shown that use of an appropriately designed computer system is a profitable approach to this problem. Both hardware and software requirements for a suitable system are discussed and an approach to computer-aided data analysis developed. A description is given of members of a collection of application programs developed for analysis of neuro-physiological data and operated in the environment of and with support from an appropriate computer system. In particular, techniques developed for classification of multiple units recorded on the same electrode are illustrated as are methods for convenient graphical manipulation of data via a computer-driven display.

By means of multiple electrode techniques and the computer-aided data acquisition and analysis system, the path followed by one of the motion detection units was traced from open optic lobe through the brain and into the opposite lobe. It is further shown that this unit and its mirror image in the opposite lobe have a mutually inhibitory relationship. This relationship is investigated. The existence of interaction between other pairs of units is also shown. For pairs of units responding to motion in the same direction, the relationship is of an excitatory nature; for those responding to motion in opposed directions, it is inhibitory.

Experience gained from use of the computer system is discussed and a critical review of the current system is given. The most useful features of the system were found to be the fast response, the ability to go from one analysis technique to another rapidly and conveniently, and the interactive nature of the display system. The shortcomings of the system were problems in real-time use and the programming barrier—the fact that building new analysis techniques requires a high degree of programming knowledge and skill. It is concluded that computer system of the kind discussed will play an increasingly important role in studies of the central nervous system.

Studies of dinucleoside monophosphates and monomer-polynucleotide interactions by proton magnetic resonance

The nature of the intra- and intermolecular base-stacking interactions involving several dinucleoside monophosphates in aqueous solution have been investigated by proton magnetic resonance spectrosocopy, and this method has been applied to a study of the interaction of polyuridylic acid with purine and adenosine monomers.

The pmr spectra of adenylyl (3' → 5') cytidine (ApC) and cytidylyl (3' → 5') adenosine (CpA) have been studied as a function of concentration and temperature. The results of these studies indicate that the intramolecular base-stacking interactions between the adenine and cytosine bases of these dinucleoside monophosphates are rather strong, and that the stacking tendencies are comparable for the two sequence isomers. The chemical shifts of the cytosine H₅ and adenine H₂ protons, and their variations with temperature, were shown to be consistent with stacked conformations in which both bases of the dinucleoside monophosphates are preferentially oriented in the anti conformation as in similar dApdC, and dCpdA (dA = deoxyadenosine; dC = deoxycytidine) segments in double helical DNA. The intramolecular stacking interaction was found to have a pronounced effect on the conformations of the ribose moieties, and these conformational changes are discussed. The concentration studies indicate extensive self-association of these dinucleoside monophosphates, and analysis of the concentration data facilitated determination of the dimerization constant for the association process as well as the nature of the intermolecular complexes.

The dependence of the ribose conformation upon the extent of intramolecular base-stacking was used to demonstrate that the base-base interaction in cytidylyl (3' → 5') cytidine (CpC) is rather strong, while there appears to be little interaction between the two uracil bases of uridylyl (3' → 5') uridine (UpU).

Studies of the binding of purine to several ribose and deoxyribose dinucleoside monophosphates show that the mode of interaction is base-stacking, and evidence for the formation of a purine-dinucleoside monophosphate intercalated complex is presented. The purine proton resonances are markedly broadened in this complex, and estimates of the purine linewidths in the complex and the equilibrium constant for purine intercalation are obtained.

A study of the interaction of unsubstitued purine with polyuridylic acid at 29°C by pmr indicated that purine binds to the uracil bases of the polymer by base-stacking. The severe broadening of the purine proton resonances observed provides strong evidence for the intercalation of purine between adjacent uracil bases of poly U. This interaction does not result in a more rigid or ordered structure for the polymer.

Investigation of the interaction between adenosine and polyuridylic acid revealed two modes of interaction between the monomer and the polymer, depending on the temperature. At temperatures above 26°C or so, monomeric adenosine binds to poly U by noncooperative A-U base stacking. Below this temperature, a rigid triple-stranded 1A:2U complex is formed, presumably via cooperative hydrogen-bonding as has previously been reported.

These results clearly illustrate the importance of base-stacking in non-specific interactions between bases, nucleosides and nucleotides, and also reveal the important role of the base-stacking interactions in cooperatively for med structures involving specific base-pairing where both types of interaction are possible.

On the distribution of the signs of the conjugates of the cyclotomic units in the maximal real subfield of the qth cyclotomic field, q A prime

Let F = Ǫ(ζ + ζ ^–1) be the maximal real subfield of the cyclotomic field Ǫ(ζ) where ζ is a primitive qth root of unity and q is an odd rational prime. The numbers u₁=-1, u_k=(ζ^k-ζ^-k)/(ζ-ζ^-1), k=2,…,p, p=(q-1)/2, are units in F and are called the cyclotomic units. In this thesis the sign distribution of the conjugates in F of the cyclotomic units is studied.

Let G(F/Ǫ) denote the Galoi's group of F over Ǫ, and let V denote the units in F. For each σϵ G(F/Ǫ) and μϵV define a mapping sgn_σ: V→GF(2) by sgn_σ(μ) = 1 iff σ(μ) ˂ 0 and sgn_σ(μ) = 0 iff σ(μ) ˃ 0. Let {σ₁, ... , σ_p} be a fixed ordering of G(F/Ǫ). The matrix M_q=(sgn_σj(v_i) ) , i, j = 1, ... , p is called the matrix of cyclotomic signatures. The rank of this matrix determines the sign distribution of the conjugates of the cyclotomic units. The matrix of cyclotomic signatures is associated with an ideal in the ring GF(2) [x] / (x^p+ 1) in such a way that the rank of the matrix equals the GF(2)-dimension of the ideal. It is shown that if p = (q-1)/ 2 is a prime and if 2 is a primitive root mod p, then M_q is non-singular. Also let p be arbitrary, let ℓ be a primitive root mod q and let L = {i | 0 ≤ i ≤ p-1, the least positive residue of defined by ℓⁱ mod q is greater than p}. Let H_q(x) ϵ GF(2)[x] be defined by H_q(x) = g. c. d. ((Σ xⁱ/I ϵ L) (x+1) + 1, x^p + 1). It is shown that the rank of M_q equals the difference p - degree H_q(x).

Further results are obtained by using the reciprocity theorem of class field theory. The reciprocity maps for a certain abelian extension of F and for the infinite primes in F are associated with the signs of conjugates. The product formula for the reciprocity maps is used to associate the signs of conjugates with the reciprocity maps at the primes which lie above (2). The case when (2) is a prime in F is studied in detail. Let T denote the group of totally positive units in F. Let U be the group generated by the cyclotomic units. Assume that (2) is a prime in F and that p is odd. Let F₍₂₎ denote the completion of F at (2) and let V₍₂₎ denote the units in F₍₂₎. The following statements are shown to be equivalent. 1) The matrix of cyclotomic signatures is non-singular. 2) U∩T = U². 3) U∩F²₍₂₎ = U². 4) V₍₂₎/ V₍₂₎² = ˂v₁ V₍₂₎²˃ ʘ…ʘ˂v_p V₍₂₎²˃ ʘ ˂3V₍₂₎²˃.

The rank of M_q was computed for 5≤q≤929 and the results appear in tables. On the basis of these results and additional calculations the following conjecture is made: If q and p = (q -1)/ 2 are both primes, then M_q is non-singular.