Erik Winfree, PhD - US grants

EIA-0093486
Winfree, Erik
California Institute of Technology

PECASE: Foundations of Autonomous Biomolecular Computation

The project is developing autonomous, programmable biochemical systems that operate in a microscopic drop of liquid to achieve chemical tasks, such as nanostructure fabrication. Theoretical models of autonomous biomolecular computation to implement these models experimentally using DNA molecules, and to quantitatively characterize individual molecular logic components and the larger systems built from them are being performed. Beyond the specific context of DNA, this research is creating a prototype of autonomous biomolecular computing systems and explore fundamental robustness issues in nanoscale computing, such as cross-talk between species and stochastic events due to thermal noise and diffusion. The project is aiming to leverage their advanced control over biochemical systems to begin establishing a broader foundation for reliable molecular computing.

Two new courses are being developed introducing students to the necessary concepts and tools required to begin work in biomolecular computation. This research is establishing an experimental system for exploring computation by biological molecules, and is providing fundamental knowledge and principles for nanoscale computation, such as models of computation, molecular algorithms, physical limits, errors and error correction. Although biomolecular systems are massively parallel, asynchronous, stochastic, and hard to design, the PI is researching on new programming principles, leading to a science of molecular computation.

Abstract
CTS-0103002
N. Seeman, et al., New York University

This proposal was received in response to Nanoscale Science and Engineering (NSE) solicitation, NSF-00119, in the category Nanoscale Interdisciplinary Research Teams (NIRT). This is a collaborative activity between New York University, California Institute of Technology and Dow Chemical Co. using GOALI model. The goal is to synthesize and demonstrate operational nanoscale machines or devices. The level of control offered by DNA systems can be exploited to make intricate DNA nanostructures, including self-assembling DNA that forms two-dimensional and three-dimensional arrays. Modeling and simulation is a critical part of this project, in order construct and test the DNA nanostructures.

It is proposed to combine the activities of New York University, California Institute of Technology and Dow Chemical laboratories to achieve a demonstration of DNA based nanomechanical devices useful for performing fast calculations, for sensors that detect specific molecules in the environment, or to improve the properties or performance of a material. Practical design and manufacture of nanoscale machines and devices requires overcoming numerous challenges in synthesis, processing, characterization, design, optimization, and fabrication. The approach will be first to prototype the designs computationally, optimizing the particular base-pair sequences, making sure that the particular lengths and spacings will lead to proper clearances, and testing the operation of the device, including the dynamics. The project will focus on nanomechanical devices of three types.
o The B-Z based nanomotor. A DNA based nanomotor predicated on the B to Z DNA
transitions under different salt conditions.
o A DNA sequence-specific mechanical device
o A DNA based switch based on principles similar to the DNA sequence-
specific mechanical device.

EIA-0113443
Winfree, Erik
California Institute of Technology

Title: Biomolecular Computing by DNA/Enzyme Systems

Dr. Erik Winfree and Dr. Hideo Mabuchi are working together to develop techniques and instruments for high-precision quantitative analysis of the DNA molecular devices. These are being designed, characterized and optimized to investigate issues such as robustness and error-tolerance of these DNA molecular devices. The technical objectives being achieved in this project are: development of spFRET instrument capable of counting individual photons from single molecules; characterization of conformal states, kinetics, and thermodynamics of DNA switches; characterization of the activities of two enzymes, RNAP and RNase, on the DNA switches; development of stochastic models of in vitro transcriptional circuits; and investigation of robust algorithms and error-control for transcriptional circuits.

Through this project, the PIs are establishing a set of experimental systems and techniques for exploring computation by biological molecules. This will provide fundamental knowledge and principles for nanoscale computation, such as models of computation, molecular algorithms, physical limits, sources of error and error correction strategies. Thus the aim is to leverage the advanced control over biochemical systems to begin establishing a broader foundation for reliable molecular computing.

Biological organisms are self-organized chemical systems that carry out algorithms encoded in the genetic
material, DNA. Biology thus provides clear proof that autonomous chemical systems can be programmed to
compute. The ability to program biomolecular systems that control chemical fabrication and informationprocessing tasks would result in a dramatic increase in the level of sophistication in bionanotechnology.
The Winfree laboratory has been developing programmable biomolecular systems based on algorithmic
self-assembly of DNA { a molecular fabrication technique that acts as a universal constructor that can in
principle create complex structures by embedding universal computation within the self-assembly processes, thus guiding the assembly of components based on an information-processing algorithm implemented by the
molecular tiles. This experimental and theoretical research has indicated that with current error rates as high as 10% and seldom lower than 1%, fault-tolerant techniques must be used when implementing biomolecularcomputing systems. The proposed research will develop such techniques for algorithmic DNA self-assembly by developing fault-tolerant tile sets that reduce major types of assembly error: (1) Proofreading tile sets, which correct errors that occur during normal growth, will be experimentally demonstrated, with the goal of achieving error rates less than 10

DNA is best known as the genetic storage medium for life. However, its unique structural properties make it attractive for engineering nanoscale structures and devices. Remarkably, synthetic DNA systems can be programmed to self-assemble into complex objects implementing dynamic mechanical tasks by appropriately designing the sequence of bases (A,C,G and T) comprising the constituent DNA strands. When mixed, the strands "hybridize" in prescribed ways by forming "base-pairs" between complementary bases (A with T, C with G). DNA nanotechnology explores and develops these capabilities for applications in nanorobotics, nanofabrication, biomolecular computation, biosensing, nanoelectronics and nanomedicine.
In principle, equilibrium and kinetic properties of a DNA strand can be characterized by the features of its "free energy landscape". Likely equilibrium structures correspond to deep valleys in the landscape, and the rate of conversion between two structures depends on the nature of the valleys and ridges separating them. The dynamics of a folding DNA strand define a path somewhat analogous to a ball rolling over the landscape. To analyze functional DNA systems with moving parts, it is important to identify large-scale landscape features that dominate experiments. Unfortunately, in practical problems, existing physical models define landscapes with fine-grained detail that obscures the large-scale features. For example, DNA systems commonly have theoretical landscapes containing more states than there are atoms in the universe, though experiments suggest that a small number of features dominate the landscape.
The project will develop algorithms for efficiently exploring large landscapes that cannot be enumerated explicitly, including coarse-graining approaches to simulate the temporal evolution of physically meaningful "macrostates" without having to simulate full "microstate" landscapes. These macrostate predictions will guide and interpret experimental studies of DNA systems of fundamental interest to current nanorobotics and biosensing efforts. Custom-built fluorescence instruments will probe free energy landscapes at the level of single molecules. While our expertise in DNA nanotechnology motivates our experiments on synthetic DNA, the new coarse-graining theory, computational algorithms, and experimental methods will be equally applicable to analysis of natural RNA molecules (such as the mutant of human telomerase RNA that is thought to cause dyskeratosis congenita by altering the free energy landscape of a conformational switch).
Our research objectives are integral with an education program dedicated to training undergraduates, graduate students, and postdocs in distinctly interdisciplinary research groups that currently involve Applied & Computational Mathematics, Applied Physics, Biochemistry, Bioengineering, Biology, Chemistry, Chemical Engineering, Computer Science, Computation & Neural Systems, and Physics. This is coupled with an outreach program that brings local high school science students to Caltech to discover DNA nanotechnology, meet with lab members in small informal groups, and generate enthusiasm for pursuing careers in science and engineering. We will also continue our policy of freely distributing the source code for our analysis and design software.

With this Chemical Bonding Center (CBC) Phase I, Step II award, the Division of Chemistry and the Office of Multidisciplinary Activities of the Mathematical and Physical Sciences Directorate jointly support the research of Milan N. Stojanovic, of Columbia University, who will lead a collaborative effort involving eight PIs from a variety of institutions to create a Center for Molecular Cybernetics. The unified goal of this center is to produce synthetic molecular machines that are powered by molecular bond formation. Chemical structures that will have two or more protruding appendages of DNA will be synthesized. These appendages, or arms of molecular "spiders", will have the ability to attach to or detach from a position on a surface in response to external stimulus. When a spider arm reattaches to a different position, the spider will move across the surface. The successful construction and description of these autonomously moving molecules will generate both scientific and public interest, and these studies have the potential to lead to applications in areas such as drug delivery and nanopatterning.

Chemical Bonding Centers are designed to focus innovative collaborative efforts that address a "big problem" which will lead to a major advance in chemistry or at the interface of chemistry and other sciences and will have the potential to attract broad scientific and public interest.

Artificial molecular-scale robots capable of cooperative and adaptive behavior currently reside firmly in the realm of science fiction. However, we will demonstrate that molecules behaving similarly to macroscopic robots can indeed display simple forms of cooperation and adaptation, when challenged with certain tasks. These "molecular robots" which we call "snakes" consists of chains of nucleic acids incorporating multiple catalytic units. They move ("walk") over landscapes covered with substrates, leaving a trail of cleaved substrates behind them. We will study the ability of these molecular robots to integrate additional catalytic segments (limbs) from the solution, or to form dimers, when we force them to perform longer walks. Those snakes that acquire additional limbs, or form cooperating dimers, while surviving harsh conditions, will be allowed to amplify. Such experiments will help create in the future molecular robots that display swarm intelligence and that are capable of distributive computing.

Self-assembly is the process by which small ``components'' spontaneously form intricate aggregate structures. DNA self-assembly is a key tool for nano-technology, nano-robotics, and molecular computation. More generally, biological organisms are self-organized chemical systems that carry out algorithms encoded in the genetic material, DNA. Biology thus provides clear proof that autonomous chemical systems can be programmed, and that they can function reliably on a grand scale -- biological organisms can be composed of as many as 1024 molecular components!

Recent experimental advances in the synthesis of artificial molecular systems have demonstrated that it is possible to program molecular self-assembly to carry out rudimentary logic. These experiments also suggested that the occurrence of errors is a major obstacle to scaling up DNA self-assembly and biologically inspired computation. This project will devise algorithmic tools and analysis techniques for error-correction and error-suppression in biologically inspired self-assembling and computational systems. It is our hope that our research will facilitate sophisticated tasks such as counting, growing molecular assemblies of pre-specified sizes (no larger, no smaller), and pattern recognition of complex chemical signals using inherently error-prone biomolecular operations at the nano-scale.

In order to design and analyze our error-correction mechanisms, we will use high level models which are both sufficiently realistic to be useful and sufficiently abstract to be amenable to analysis. The basic elements of our models will be DNA tiles, transcriptional circuits, and DNA hybridization catalysts. Thus, our research will target assembly of and computation with large molecules such as long chains of DNA rather than smaller molecules such as proteins and amino acids.

We will also develop course material on the basis of our research which will be taught at Caltech and at Stanford.

PI: Nadrian C. Seeman
Institution: New York University
Proposal Number: 0608889
Title: NIRT: Active Nanostructures for Nucleic Directed Synthesis of Organic Functional Polymers

This proposal was received in response to Nanoscale Science and Engineering initiative, NSF 05-610, category NIRT.

Summary: The goal of this project is to build on the DNA nanotechnology developed by the Seeman laboratory over the last four years to chemically manufacture a DNA nanomachine capable of synthesizing polymers with desired optical, electrical, and stereochemical properties that are difficult or impossible to achieve with normal polymer synthesis techniques. The aim is to develop and prototype the strategy to construct such polymers with a precision approaching that by which the ribosome constructs proteins. This project would bring to bear underlying tools that have been developed recently by Seeman (NYU), Goddard (Caltech), Winfree (Caltech), and Canary (NYU) under previous NIRT and SGER projects. They plan to use these tools to produce and demonstrate the artificial ribosome device. To accomplish this they plan to:
(1) Develop a translation device to convert a given sequence of monomers to polymers with precise length and sequence control (modifying the rotary device previously developed by Seeman)
(2) Use transcriptional circuitry developed by Winfree to control the nature and sequence of the polymer synthesized and to provide polymers that reflect the history of the system.
(3) Use multiscale first principles-based simulation tools developed by Goddard and Deng to design and optimize the polymer monomers and connections to achieve supramolecular active organic polymer structures with desired electronic or optical properties
(4) Use novel organic synthesis techniques developed by Canary to build DNA-polymer subunit conjugates to add polymer subunits to nucleic acid backbones. This chemistry-prototyping system already responds to a continuous message.

They plan to first introduce a translocation step in the nanodevice so that inputting a new message to the device will result in a new polymer product. The advantage of translocation (in contrast to the rotary device already developed by Seeman), is that longer products can be built without making larger devices. Ultimately they expect to generate the message via the transcriptional circuitry developed in the Winfree laboratory, thereby building polymers as a consequence of logical circuitry and in response to cues from the surrounding medium.

Intellectual Merit: This project attempts to develop a prototype DNA based machine capable of synthesizing organic polymers with the same flexibility and specificity displayed by the ribosome in synthesizing proteins. This is a grand challenge which would stimulate a number of research efforts to enable this for broader ranges of organic compounds. Nothing in the technology limits it to organic polymers. The project builds on many years of development in the Seeman, Goddard, Winfree, and Canary labs all to be brought to bear on this problem. The confluence of these disparate efforts would likely stimulate each of the research areas involved. To provide a useful target for this technology, the PIs plan to develop novel one and two dimensional nonlinear optical (NLO) polymers with very large hyperpolarizabilities (susceptibilities). Even more ambitious is the proposal to build a new type of nanostructure architecture based on assembling a 2D array of functional polymers (rather than the nanotubes or nanowires of other recent approaches). They suggest that these can be used to put logic units at the nodes rather than simple switches. This should stimulate many new ideas and proposals.

Broader Impacts: The NYU and Caltech PIs have aggressively pursued the active incorporation of underrepresented groups within their research operations and they have participated in special outreach programs aimed at both high school and K6 students with an emphasis on underrepresented groups. They are strongly committed to continuing and escalating these efforts under the NIRT program. For example, the Goddard group has played a vital role in Quality Education for Minorities (QEM) and Minorities in Mathematics, Science, and Engineering (MSE) programs at Caltech. NYU has involved many high school students in nanotechnology research and Seeman works closely with scientifically-oriented arts and entertainment groups.

Research and Education Theme: Nanoscale Devices and System Architectures

Background. One of the greatest contrasts between the biological organisms and human technology lies in how they are constructed. Plants and animals grow from the inside out, often from a single cell to an organism containing billions of cells, each of which is built from molecular components that are manufactured with atomic precision within the cell. In contrast, mankind's greatest engineering marvels, such as airplanes and skyscrapers and computers, are put together from the outside in, with components being manufactured in factories and assembled piece by piece. This distinction is often referred to as "bottom-up" vs "top-down" assembly in the biological "bottom-up" approach, the assembly process is guided by the components themselves, while in the engineering "top-down" approach, there is an entity conceptually above the object being built that supervises and guides the manufacturing process. Human engineering has mastered top-down methods to create systems of great complexity (but has not extended them to the atomic and molecular scale) and has exploited bottom-up methods for the synthesis of diverse molecular, polymeric and crystalline structures (but has not created information-rich structures of great complexity).
Project Goals. Our goal is to demonstrate how bottom-up techniques can create complex atomically-defined structures, as biology does, by embedding information and computational processes within the molecules themselves. In biological development, a program (the genome) uses biochemistry to guide the growth process and determine the ultimate form of the organism. In the parlance of computer science, a system that can be programmed to accomplish any task that can be accomplished is called a "universal" system. A universal computer can be programmed to perform any computation, while a universal constructor can be programmed to carry out any construction task. Recent work has theoretically shown that universal molecular self-assembly is possible and has experimentally demonstrated that the approach shows promise, using DNA as a construction material to create functional molecular devices so-called "DNA nanotechnology". In this proposal, we aim to bring DNA nanotechnology to the point where universal bottom-up self-assembly can be achieved well enough that immediate technological applications can be demonstrated.
Specific Aims. We aim to make major advances both in our ability to program complex self-assembly logic and in our ability to interface the DNA structures to chemically-, optically-, and electronically-relevant materials. We will focus on four main goals, which span the range from long-term fundamental work to near-term development: (1) self-assembly of a template for a complex molecular-scale electronic circuit; (2) programming the behavior of molecular walking motors to transport components in nanofabrication tasks; (3) attaching carbon nanotube wires to create small nanoscale electronic circuits; and (4) integrating bottom-up and top-down fabrication by placing and orienting self-assembled components at target locations on silicon wafers with functional electrical contacts.
Uniquely, the aims of this research require simultaneously development of two novel computing systems: the first, inspired by biological self-assembly and development, operates at the level of molecular machines and biochemistry, and will be programmed to construct the second, composed of carbon nanotubes assembled into nanoscale circuits, which operates at the electrical level like conventional computing devices.
Broader Impact. An important aspect of this project will be the training of young scientists (undergraduates, graduate students, and postdocs) capable of spanning the interdisciplinary subjects involved in this work.

"Biochemical reactions in vivo are regulated by elaborate control circuits that modulate their activity in response to internal and external signals. The RNA world hypothesis suggests that such sophisticated biochemical organization can be achieved with nucleic acids alone, and indeed DNA and RNA have been shown to provide a versatile construction material for engineering molecular structures and devices, including catalytic and logical control elements as well as small circuits. The design of biochemical circuits is likely to play as large a role in biological engineering as the design of electrical circuits has played in the engineering of electro-mechanical devices, motivating the development of methods to construct large and complex circuits of nucleic acid gates for digital and analog tasks.

In this project, the investigators will integrate previously developed nucleic acid circuit components into a unifying design framework, develop improved circuit components, construct circuits of increasing complexity, and develop a compiler that takes an abstract specification of (analog or
digital) circuit function and produces a biochemical implementation using automatically-designed DNA molecules. Example circuits include amplifiers, oscillators, latch memories, a chemical Rossler attractor displaying chaotic dynamics, and a digital circuit for binary addition."

Behavior-based robotics was established around the idea that robots could be constructed by connecting elementary sensor and actuator modules, without the need to form any internal representation of the world in which they operate. When designed appropriately, such robots, both as individuals and as groups, exhibit complex and seemingly ?intelligent? behaviors, solving challenging tasks in real time, while reacting only to their local environment and obeying sets of local rules. In part, this approach to robotics was inspired by considering natural systems, such as self-organization and adaptability of social insects in their colonies. An analogous approach to initiate the development of the field of behavior-based molecular robotics will be performed over the next three years, leading to groups of molecules that would appear to an observer to show a variety of task-oriented behaviors or some form of purposeful and dynamic self-organization.

Individual behavior-based molecular robots are single molecules displaying multiple sensors-actuators. When exposed to artificial landscapes displaying substrates keyed to their sensors-actuators, the molecules start executing elementary steps, determined, in a stochastic sense, by their constantly changing local environments. On some landscapes, called prescriptive, individual molecular robots and their collectives will execute algorithms mimicking wound-up automata with sequence control mechanisms. In contrast, on non-deterministic landscapes, the robots and their collectives will demonstrate properties emerging from internal organization of individual sensors and actuators and through local interactions between molecules and their environments. Importantly, these new interpretations of molecular behaviors will allow radically different experiments from all previous approaches to molecular robotics, while keeping experimental designs realistic, leading to embodiment in the physical world.

There is great potential for adapting biopolymer molecules such as RNA and DNA to meaningful computational tasks and purposes. Having the ability to program molecules at many orders of magnitude larger scale than at present using new algorithms and software analogues has the potential to change the way we analyze, understand and manipulate molecular systems. It can lead to practical applications of significant benefit to society across a wide range of national initiatives in materials, nano-biotechnology, tissue engineering, regenerative medicine, and many other emerging areas. This ambitious Expedition addresses the exciting challenge of developing initial foundational steps toward creating large-scale molecular programs. This experimental technology Expedition aims to develop a functional abstraction hierarchy to create molecular programming languages, compilers, tools and models; a theoretical framework for the analysis and design of molecular programs; validation of the above utilizing molecular programs with orders of magnitude higher scale of components than at present; and testing of the developed molecular programming technologies on real-world applications. This high-risk/high-payoff research will increase our understanding of the relationship between computation and the physical world, how information can be stored and processed by molecules, and the possibilities and limits of what can be computed and fabricated. Outreach includes summer undergraduate and minority student research fellowships, K-12 visiting days, boot camps, workshops and many other efforts to create a broader molecular programming research community.

DNA is well-known for its role in biology as the genetic material. In recent years, however, DNA has begun to be used as a material for creating technology. In particular, DNA can be used to make complex nanometer-scale patterns which, in turn, can be used as templates to arrange nanometer-scale devices. For example, DNA patterns might be used to organize nanowires and nanoswitches to create computer circuits much smaller, cheaper, and faster than current semiconductor computer chips.

Recently the investigators invented a method called DNA origami, whereby a long DNA strand is folded into any desired pattern. The method is powerful but has limitations: current DNA origami only contain 200 pixels, which means they can organize at most 200 different devices---not enough to create a complex circuit. In practice it takes 10-20 pixels to align a single carbon nanotube wire on DNA origami, so the most complex device created using DNA origami is a field effect transistor composed of two crossed carbon nanotube wires. Another difficulty is that DNA origami are made in solution, but must be used on surfaces like silicon. Transferring DNA origami to silicon currently results in random placement and orientation, but to build circuits DNA origami must positioned accurately.

The investigators are interested in overcoming these limitations. They are working on: (1) combining DNA origami into larger patterns with larger numbers of pixels by treating DNA origami as puzzle pieces that fit together based on "stacking interactins", (2) precisely placing and orienting DNA origami on lithographically-defined sticky patches on silicon, and (3) using DNA origami to organize multiple carbon nanotubes to create more complex circuits, such as NAND logic gates.

Student travel support for DNA17
Conference title: 17th International Conference on DNA Computing and
Molecular Programming (DNA17)
Location: California Institute of Technology, Pasadena, California, USA
Dates: September 19?23, 2011
Website: http://dna17.caltech.edu



Summary
This is an unsolicited proposal for 12,000 USD for student travel support for the 17th International Conference on DNA Computing and Molecular Programming (DNA17). The primary purpose of the proposal is to give travel assistance to students who are giving oral or poster presentations at the conference. The selection procedure for travel awards is described in detail below and is designed to give priority to women and underrepresented minorities, and to research quality. Approximately 20 successful student applicants, from US institutions (excluding Caltech), will be funded for travel and accommodation, with an expected average award of 600 USD per student.


Intellectual Merit
The annual International Conference on DNA Computing and Molecular Programming (DNAx) is the premier forum where scientists with diverse backgrounds come together with the common purpose of advancing the engineering and science of biology and chemistry from the point of view of computer science, physics, and mathematics. Continuing this tradition, the 17th International Conference on DNA Computing and Molecular Programming (DNA17), under the auspices of the International Society for Nanoscale Science, Computation and Engineering (ISNSCE), will focus on the most recent experimental and theoretical results that promise the greatest impact. A steady stream of papers in the field appear in Nature and Science, as well as other top journals such as Nature Nanotechnology, Nature Chemistry, Nature Biotechnology, Angewandte Chemie, JACS, Physical Review Letters, Physical Review Letters, SIAM Journal on Computing ? and the authors of these papers regularly attend DNAx conferences to present their work in a preliminary form.


Broader Impact
By funding travel to students we are actively encouraging and incentivizing a new generation of researchers to attend the conference. We are giving special priority to women and minority applicants whose papers or posters were accepted at the conference. Students who attend DNA17 will get exposure to early versions of work that will go on to be published in top venues and, furthermore, they will have the opportunity to interact with, and potentially collaborate with, researchers who are producing work of the highest quality.

This project will explore the future of molecular programming area via a Special Session at the 17th
International Conference on DNA Computing & Molecular Programming (DNA17). The conference will take
at California Institute of Technology, Pasadena, California, USA on September 19, 2011. The conference website is http://dna17.caltech.edu. The goals of the event are to elucidate future directions and specific challenges for the field of DNA computation and molecular programming, and to facilitate discussion on how these visions are to be met. The DNA17 conference is the flagship conference in this emerging area.

A report will be provided to NSF after the event, consisting of a short statement from each invited panelist and a summary of each panel discussion by the organizers. The panel discussions will provide a timely assessment of the field and the challenges and opportunities for the future, which will be useful to conference attendees and other researchers working in this area as they formulate their next research directions.

Requested funds will primarily go to support registration and travel expenses for the invited panelists,
as well as incidental costs associated with the impromptu parallel sessions.

This project will develop and evaluate methods by which large numbers of humans, together with computers, can advance the field of synthetic biology by assembling a corpus of creative designs of molecular machines built from DNA segments as well as other molecular structures. Specifically, it will develop a massively-distributed DNA machine construction game that will enable human worldwide collective creativity to be applied to problems ranging from the design of novel self-organizing materials to smart therapeutics that can sense and respond to their environment. The innovative approach is to cast problems of constructing molecular nano-machines with specific functions as a collaborative machine design game governed by the rules of DNA strand interactions.

This approach points to a new paradigm for future science, in which a large group of people together with computers work on difficult creative problems, finding solutions that could not be found by computers alone, or by people alone, or without the massive participation of users. If successful, this approach could change science profoundly, with wide-ranging impact on many disciplines including nanotechnology, biochemistry, medicine, and even social and economic behavior analysis. Although the project specifically focuses on games that use DNA strands as principal building blocks of nano-machines, the potential set of applications is large, and encompasses three of the most significant problems facing humanity today.

The primary goal of the computer game is to develop and focus collective creativity towards a design space of machines governed by DNA molecular mechanisms. It is currently not known whether this form of sophisticated scientific design creativity can be developed rapidly with non-experts. It is also unknown whether this developed creativity can exceed the current capabilities of the scientific community. This project aims to answer a number of fundamental questions: How does one develop computer games to maximize targeted human design creativity? What are the guiding principles of successful molecular design games? How do we generalize game-development principles to the widest possible range of synthetic biology problems? How can we develop a collective creative design process that outperforms any individual creativity? How do we learn from the way people play the game, and distill their strategies towards stronger automated approaches?

The successful outcomes of this project can have a wide ranging impact on health and medicine. One such problem is the design of diagnostic devices and imaging technologies. The game players will work to develop DNA sensors and circuits that can autonomously analyze and interpret the information encoded in a set of molecular disease markers. This approach will enable new devices for multi-analyte testing in low resource settings and will lead to novel medical imaging technologies. Another challenge is design of novel targeted therapeutics, in this case novel RNA-based therapeutics that can autonomously sense and analyze their environment and activate a therapeutic response only where required. A third problem is design of novel materials. This project will develop DNA nanostructures with the potential for the massively parallel self-assembly materials with desired electronic, optical, or chemical properties. These materials will find applications in areas from artificial photosynthesis to biofuels production.

This effort will have positive broader impacts for informal science education. The game will reach out to people of all demographic profiles in hope of educating everyone about key molecular research challenges, empowering them to solve important scientific problems, and engaging them in research and science in general. Hopefully, the best scores in these games turn into seminal discoveries with deep impact on people's lives. Also, undergraduates will be involved directly in game development, and a course centered around prototyping of molecular games will be offered. Furthermore, the research team will work with education scientists to develop a new curriculum about DNA and how nature uses molecular mechanisms to achieve function. The curriculum will be anchored around the DNA Machine game and will be piloted in US high schools.

The dominant manufacturing paradigm for human technology has been top-down construction of objects, in the sense that a large entity manipulates smaller entities to put them together into a functional device. In contrast, for billions of years biological organisms have constructed objects using a bottom-up technology, in the sense that the pieces self-assemble or grow without outside assistance. For example, to make a complex molecular machine, enzymes within the cell might synthesize a number of proteins that then diffuse randomly until they bump into each other and click into place; while on a larger scale, a single cell might grow into an elephant.

The bottom-up manufacturing paradigm has advantages that top-down methods are unlikely ever to achieve, such as the ability to create meter-scale objects from components with atomic-scale (nanometer) resolution and chemical functionality but it requires a level of exquisite control over molecular structure and function that human science and technology has not yet attained. We believe that the primary missing ingredient is information science and technology: information must be encoded within synthetic molecules to control their behavior and to create programmable molecular systems.

In this research, the aim is to push the frontiers of information-based molecular self-assembly using DNA nanotechnology. The past fifteen years have seen the development of an abstract theory of algorithmic self-assembly (initiated by Winfree) that merges the mathematical theory of geometrical tiling, the statistical mechanical and kinetic theories of crystal growth, and the algorithmic theory of Turing machine computation. This theory shows how, in principle, synthetic DNA molecules called ?tiles? can be designed to carry information that directs their assembly into complex and sophisticated shapes and patterns. Just as a small program can produce a large and intricate output, a small tile set can result in the self-assembly of a large and intricate object the tile set is a program for controlling the molecular self-assembly process. Laboratory experiments in the past fifteen years have demonstrated the foundations of this theory using DNA tile sets on the order of two dozen tile types, i.e. very small molecular programs.

In the past year, a new molecular motif for DNA tiles (developed by Yin) has been used to self-assemble molecular structures using up to 1000 distinct tile types that each has a unique target position within the structure, like a self-assembled molecular-scale jigsaw puzzle. This is the simplest type of molecular program. A major goal of the proposed work is demonstrating that the new ?single strand tile? motif can be used to create significantly more complicated self-assembly programs than have been seen to date by reusing distinct tile types in many locations and in an algorithmic fashion, much like living systems that reuse the same molecules in many different ways. Sophisticated algorithmic tile reuse of two dozen to perhaps 1000 or more distinct components vastly expands the capabilities of self-assembly programs. To achieve this, proposed work will (a) improve techniques for an important subroutine for controlling molecular growth, a binary counting process that terminates after growing a pre-specified distance; (b) develop methods and molecular structures for nucleating the growth of single-strand tiles with pre-specified information that serves as ?input? to the molecular program; (c) demonstrate algorithmic growth of single-strand tiles that perform Turing machine and/or cellular automaton computations; (d) investigate proofreading techniques for reducing the rate of errors during self-assembly; and (e) create software tools that facilitate the design and analysis of these complex molecular systems.

Support is requested for the participation of ~15 researchers from US academic institutions for a three-day workshop, ``Advances in Molecular Programming and Computing: Toward Chemistry as a New Information Technology'', that aims to assess the current state, prospects, and challenges in this new research area. A similar number of researchers from European and Asian countries will be participating, supported by other funding sources. Participation from key industry representatives will also be encouraged.

The objective of the workshop is to articulate a vision for the advancement of the information science and technology aspects of molecular chemistry and biochemistry, ranging from molecular devices to DNA nanotechnology to synthetic biology as well as related areas involving information processing and programmability within engineered (and natural) molecular / chemical / biological systems. The concrete goal is to bring this emerging frontier more prominently to the attention of both US and non-US funding agencies, to explore it from theoretical, scientific, technological, and application perspectives, and to provide an unbiased assessment of its potential and challenges that will inform future decision-making. Through a written report, published along with original research and opinion articles as a formal proceedings, the workshop will explore how chemical and biochemical substrates might emerge as a new information technology in the coming century, and help articulate the challenges, the potential, and the need for vigorous research activity in this area, with an emphasis on how researchers (and funding agencies) with deep experience in information science and technology will be integral to developing this frontier.

Intellectual Merit: Molecular programming will provide new insights and solutions to grand challenges in biology, chemistry, materials science, and medicine. In manufacturing it will enable fabrication of complex products from the bottom-up (e.g., programmable materials and devices grown from molecules); in biological engineering it will bring deeper computer science principles to the design of programmable subsystems within living cells. The knowledge gained will clarify the relationship between computation and the physical world---how information can be stored and processed by molecules, the limits of what can be computed and fabricated, and how quickly computation or fabrication can be done for a given energetic cost. While molecular programming will leverage existing tools from computer science, control theory, electrical engineering, and bioengineering, it will also require new approaches to analyzing complex programs, circuits, and networks of molecules.

Broader Impact: This workshop will expand the network of scientists and engineers working in molecular programming and bring together a diverse community of researchers who will, over time, build this field.

The computing revolution began over two thousand years ago with the advent of mechanical devices for calculating the motions of celestial bodies. Sophisticated clockwork automata were developed centuries later to control the machinery that drove the industrial revolution, culminating in Babbage's remarkable design for a programmable mechanical computer. With the electronic revolution of the last century, the speed and complexity of computers increased dramatically. Using embedded computers we now program the behavior of a vast array of electro-mechanical devices, from cell phones and satellites to industrial manufacturing robots and self-driving cars. The history of computing has taught researchers two things: first, that the principles of computing can be embodied in a wide variety of physical substrates from gears to transistors, and second, that the mastery of a new physical substrate for computing has the potential to transform technology. Another revolution is just beginning, one whose inspiration is the incredible chemistry and molecular machinery of life, one whose physical computing substrate consists of synthetic biomolecules and designed chemical reactions. Like the previous revolutions, this "molecular programming revolution" will have the principles of computer science at its core. By systematically programming the behaviors of a wide array of complex information-based molecular systems, from decision-making circuitry and molecular-scale manufacturing to biomedical diagnosis and smart therapeutics, it has the potential to radically transform material, chemical, biological, and medical industries. With molecular programming, chemistry will become a major new information technology of the 21st century.

This Expeditions-in-Computing project aims to establish solid foundations for molecular programming. Building on advances in DNA nanotechnology, DNA computing, and synthetic biology, the project will develop methods for programmable self-assembly of DNA strands to create sophisticated 2D and 3D structures, dynamic biochemical circuitry based on programmable interactions between DNA, RNA, and proteins, and integrated behaviors within spatially organized molecular systems and living cells. These architectures will provide systematic building blocks for creating programmable molecular systems able to sense molecular input, compute decisions about those inputs, and act on their environment. To manage system complexity and to provide modularity, the project will establish abstraction hierarchies with associated high-level languages for programming structure and behavior, compilers that turn high-level code into lists of synthesizable DNA sequences, and analysis software that can predict the performance of the sequences. This will allow molecular programmers to specify, design, and verify the correctness of their systems before they are ever synthesized in the laboratory. In addition to these software tools, the project will study the theory of molecular algorithms in order to understand the potential and limitations of information-based molecular systems, what makes them efficient at the tasks they can perform, and how they can be effectively designed and analyzed. Putting the products of this fundamental research to the test, the project will pursue real-world applications such as molecular instruments for probing biological systems and programmable fabrication of nanoscale devices.

This project will expand the network of scientists and engineers working in molecular programming by building a diverse community of students, teachers, researchers, scientists, and engineers. This community will be fostered through the creation of publicly accessible software tools, courses, textbooks, workshops, tutorials, undergraduate research competitions, and popular science videos to teach the principles and methods of molecular programming and to engage young researchers and the public in this exciting new field. Industrial partnerships with relevant biotechnology and other high-tech companies will ensure fast transfer of knowledge generated into real-world products. Perhaps most importantly, as molecular programming becomes a widespread technology, it has the potential to transform industry with new complex nanostructured materials, to transform chemistry with integrated and autonomous control of reactions, to transform biology with advanced molecular instruments, and to transform health care with more sophisticated diagnostics and therapeutics.

This INSPIRE project is jointly funded by the Chemical Theory, Models, and Computational Methods program in the Division of Chemistry in the Directorate for Math and Physical Science, the Algorithmic Foundations program in the Division of Computing and Communication Foundations in the Directorate for Computer & Information Science, and the INSPIRE program in the Office of Integrative Activities. This project advances the objectives of the National Strategic Computing Initiative (NSCI), an effort aimed at sustaining and enhancing the U.S. scientific, technological, and economic leadership position in High-Performance Computing (HPC) research, development, and deployment.

DNA and RNA base-pairing (A pairs with T, C pairs with G for DNA; A pairs with U, C pairs with G for RNA) play central roles in the biological circuits that operate within living organisms. This base-pairing also offers a rich design space for the new engineering disciplines of molecular programming and synthetic biology. These engineering efforts are greatly assisted by the use of computational algorithms to design and analyze the base-pairing (secondary structure) properties of DNA or RNA strands before beginning more costly and time-consuming laboratory studies. Historically, the secondary structure models underlying these calculations have been parameterized based on experiments performed piecemeal over a period of decades, making it difficult to improve the models (still incomplete after 45 years of effort) or to extend the models (to new materials and experimental conditions critical to modern applications). Departing dramatically from this experimental parameterization approach, the proposed work will establish a computational parameterization framework, in which state-of-the-art computational chemistry methods with be used - for the first time - to perform atomistic simulations on a carefully chosen suite of small model problems, enabling automated parameterization of new secondary structure models from scratch. This strategy requires a high level of inter-disciplinarity beyond the capabilities of any individual research group, demanding computational and algorithmic expertise to perform modeling at both the atomistic level and the secondary structure level, and experimental expertise to test key ensemble properties predicted from new parameter sets. This effort draws together three laboratories (Miller, Pierce, Winfree) spanning three Caltech Divisions (Biology & Biological Engineering, Chemistry & Chemical Engineering, and Engineering & Applied Science) to achieve major impact on the molecular programming, synthetic biology, and life sciences research communities by dramatically improving current secondary structure models and by creating a repeatable, improvable, extensible computational framework for generating new models long into the future. Over the coming decades, the fields empowered by these advances are poised to generate transformative molecular and cellular technologies addressing challenges to science and society ranging from neuroscience and development, to diagnosis and treatment, and from renewable energy to sustainable manufacturing.

The programmable chemistry of nucleic acid base pairing is central to the circuits that orchestrate life and to the emerging engineering disciplines of molecular programming and synthetic biology. Existing secondary structure models have great utility for analyzing and designing functional DNA and RNA systems, but current equilibrium parameter sets are incomplete, apply to a limited set of experimental conditions, and are difficult to extend or improve as they are based on empirical parameters measured over the course of 45 years. Furthermore, essentially no kinetic parameters have been measured to date. Departing from this piecemeal experimental approach, the proposed work will parameterize equilibrium and kinetic secondary structure models - for the first time - using atomistic molecular simulations. State-of-the-art computational chemistry methods will be used to set up a forward compatible framework for parameter generation that is automated and repeatable, enabling researchers to rerun the parameterization suite from scratch to generate an entire parameter set for a new set of experimental conditions (salt, temperature, denaturant), for new synthetic analogs (LNA, 2?OMe-RNA), or for mixed-material interactions (DNA/RNA, RNA/2'OMe-RNA, RNA/LNA) that are crucial for modern in situ and in vivo applications. The computational framework will initially be validated via comparison to the subset of DNA and RNA parameters that have been most carefully measured in existing empirical models, followed by validation with respect to key equilibrium and kinetic results extracted from the experimental literature, or measured in the laboratory.

The promise of molecular programming lies in its ability to not only process information autonomously, but to do so in a biochemical context in order to sense and actuate matter. For its simplicity and its programmability, one attractive option for chemical information processing is built upon the DNA strand displacement (DSD) primitive, where a soup of rationally designed nucleotide sequences interact, react, and recombine over time in order to carry out sophisticated computation. The focus of this proposal is the creation of a reconfigurable DSD architecture akin to a molecular breadboard. Its purpose is to "scale-up" what is possible with this technology and to "scale-out" its adoption to new contexts and new areas of study. A small number of fast, robust and well-understood molecular components will be developed that compose seamlessly. The necessary tools to facilitate rapid circuit design and characterization will also be developed. The reconfigurable architecture will be designed to meet the challenges required in real-world applications ranging from point-of-care diagnostics to sensing and actuation within molecular systems. Due to its ease of use, we envision that this molecular breadboard will be an ideal vehicle to teach molecular programming and to facilitate wider adoption of DSD systems.


Building on a new leak reduction paradigm for DNA strand displacement systems, a new design for robust molecular computing gates will be developed, experimentally tested, and refined. By perfecting a set of molecular components suitable for use in modular and reconfigurable circuits, this will result in a fixed set of dozens of high quality gates that can be arbitrarily wired-up in order to create bespoke molecular circuits. A compiler will be developed that takes as input a circuit or logic function and provides as output the optimized set of biochemical "wires" necessary to activate the desired logic behavior. If successful, it will be possible to create and execute fast, leakless and robust molecular circuits, for circuits 2×-10× larger than have been previously demonstrated and with completion times 10×-100× faster. This increase in complexity creates an even greater need for design verification that will be addressed by the development of more efficient kinetic simulation software. The breadboard promises to be robust enough for immediate use in applications, such as diagnostics and molecular imaging, and in new contexts such as paper-based devices.

With a vision to establish novel molecular programming rules for engineering for developing synthetic systems inside or outside of living cells, the annual International Conference on DNA Computing and Molecular Programming has been one of the premier interdisciplinary forums where scientists with diverse backgrounds (e.g., in computer science, physics, chemistry, biology and mathematics) come together to present their highest quality research and discuss new ideas. This proposal aims to provide student travel support for the 24th International Conference on DNA Computing and Molecular Programming (DNA24), to be held at Jinan, China during October 8-12, 2018. By funding travel for U.S.-based students, the organizers are actively encouraging and incentivizing a new generation of researchers to benefit from participating in the conference, fostering the development of the next generation of molecular programmers, by encouraging students to attend, present their work, and interact with other important players in the field. Up to 15 successful student applicants will be supported, by providing assistance to women and underrepresented minorities who are delivering oral or poster presentations at the conference, and to graduate students who are otherwise unable to afford attending this conference. The availability of the awards to US citizens and students at US institutions will be included in conference announcements, soliciting applications.

This highly interdisciplinary conference emphasizes topics that bridge computation, biology, and nanotechnology and attracts researchers in the fields of computer science, mathematics, chemistry, molecular biology, and nanotechnology. The scope includes control of molecular folding and self-assembly to construct nanostructures; demonstration of switches, gates, devices, and circuits with biomolecules; molecular motors and molecular robotics; computational processes in vitro and in vivo; studies of fault-tolerance and error correction; synthetic biology and in vitro evolution; software tools for analysis, simulation, and design; a range of applications in engineering, physics, chemistry, biology, and medicine.

This award reflects NSF's statutory mission and has been deemed worthy of support through evaluation using the Foundation's intellectual merit and broader impacts review criteria.

As computing technology matures, it becomes possible to embed programmable computing devices into objects and materials where it was previously almost unthinkable: autonomous robots on Mars, ?smart dust? femtosatellites and ?smart paint? with embedded millimeter-scale electronic circuits, ?smart? molecular therapeutics with embedded biochemical circuits, genetically engineered living cells with embedded genetic regulatory networks controlling their activity, and ?smart? chemistry with programmable molecular robots that control the assembly and disassembly of molecular materials, for example. As miniaturization reaches the nanometer and molecular scale, both device fabrication and device operation become unreliable, ultimately dominated by stochastic effects. Despite decades of study, the theory of computation in the presence of high levels of stochasticity remains underdeveloped, and the practice of building stochastic computing systems is limited accordingly. While the majority of prior work has focused on error-tolerant designs that enable robust implementation of deterministic computation using unreliable and stochastic components, this project will investigate how the abundantly available stochastic operation of molecular devices can provide augmented computing power ? going beyond what a deterministic implementation could achieve with the same resources. As such, it will help establish a rigorous computer-science foundation for molecular information technology. Long-term, programmable molecular information technology is poised to eventually impact industry and society broadly, as programmable chemistry will enable information-based responsive molecular materials, advanced biomedical therapeutics and diagnostics, sophisticated chemical synthesis and molecular-scale instruments, and other applications of molecular nanotechnology. The proposal includes education and outreach plans to train and prepare students with emphasis on recruiting students from women and minority groups.

Initial investigations will consider models of computation that have been used in the rapidly developing fields of DNA nanotechnology and molecular programming: formal chemical-reaction networks, molecular tile self-assembly systems, polymer-reaction networks and reaction-diffusion systems. Recent work has shown that well-mixed chemical-reaction networks operating in small volumes can utilize their stochasticity to represent complex probability distributions, to perform information-processing tasks such as probabilistic inference, and to effectively search for solutions to complex combinatorial problems. This project aims to improve understanding of the benefits of stochastic molecular computation by building on these insights. First, it will establish a complexity theory for chemical-reaction networks that generate probability distributions. Second, it will explore how stochastic constraint satisfaction by chemical-reaction networks can lead to robust spatial pattern formation in self-organizing reaction-diffusion systems and other models that incorporate geometry. Third, it will develop an understanding of how stochastic self-assembly processes can augment the power of algorithmic self-assembly. A concrete outcome will be a demonstration of how the stochastic nucleation of self-assembled DNA structures can perform an information-processing task similar to pattern recognition by neural networks.

This award reflects NSF's statutory mission and has been deemed worthy of support through evaluation using the Foundation's intellectual merit and broader impacts review criteria.

The principles of neural computation, developed mostly over the past 50 years, have led to profoundly improved understanding of how brains process information and have served as the foundation for modern machine learning techniques. Only recently has it begun to be appreciated the extent to which these principles of neural computation apply more broadly and can be found operating within non-neural systems. In particular, the implications and potential of neural computing principles for designing advanced synthetic molecular systems are only beginning to be explored. Key principles include the power of high-dimensional pattern recognition using linear threshold units and winner-take-all competition, learning from experience to sculpt network connection strengths, the generation of complex patterns from the resonance of network dynamics, and the interplay between spatial structure and computing capabilities. Molecular programming using DNA nanotechnology now has sufficiently developed methods to design systems that explore and exploit these neural computing principles. This research will pioneer three new types of DNA neural networks: those capable of unsupervised learning of complex patterns in their environment, those capable of complex spatial pattern formation as reaction-diffusion systems, and those capable of exploiting the molecular-scale spatial organization of DNA nanostructures to perform more efficient computation in certain regimes of operation. In the long term, the incorporation of neural computation principles into future molecular systems will open doors to new applications ranging from biomedicine to materials science. In the medium term, an important impact of this project will be the future careers of the postdocs and graduate students who will benefit from the research experience and mentoring, whether they move on to academia, industry, or entrepreneurship. In the short term, the researchers will incorporate their scientific understanding into online software tools, continue to integrate research with education, provide undergraduates with mentored summer research, enhance the interdisciplinary research environment, and involve more women in science. They will also increase public engagement with science by presenting at public events, interviewing for popular science magazines, and creating artworks to illustrate their research.<br/><br/>Specific research goals for the development of the three new types of DNA neural networks are as follows. First, learning is arguably the most desirable property of synthetic molecular circuits. This project builds on the researchers’ current work demonstrating supervised learning and expands it to the broader category of unsupervised learning. A limitation of supervised learning is that a “teacher” must provide training examples that indicate what should be learned. Unsupervised learning addresses this limitation by exposing the molecular circuits to only what they encounter but not how they should respond; this new capability would be necessary for molecular robotic systems that operate autonomously, as cells do, within a molecular milieu. Second, reaction-diffusion pattern formation has been studied since Alan Turing’s seminal work on morphogenesis, both for its relevance to biological patterning and as an intrinsic physical mechanism of self-organization. However, the complexity of reaction-diffusion patterns has been limited. The researchers will leverage recent breakthroughs in deep learning techniques to design complex reaction-diffusion networks by example. They will use the differentiable programming approach, combined with the recent advances in the synthesis of large DNA neural networks and reliable DNA hydrogels as a spatial substrate for reaction-diffusion experiments. Finally, the researchers will perform a theoretical study that applies their expertise in DNA origami tiles and surface-localized chemical reaction networks to introduce a novel computing architecture for DNA neural networks. This architecture provides a new trade-off between design complexity and molecular operation that may scale better than prior approaches as the network size increases.<br/><br/>This award reflects NSF's statutory mission and has been deemed worthy of support through evaluation using the Foundation's intellectual merit and broader impacts review criteria.