skip to main content


Title: Distributed Implementation of Boolean Functions by Transcriptional Synthetic Circuits
Starting in the early 2000s, sophisticated technologies have been developed for the rational construction of synthetic genetic networks that implement specified logical functionalities. Despite impressive progress, however, the scaling necessary in order to achieve greater computational power has been hampered by many constraints, including repressor toxicity and the lack of large sets of mutually orthogonal repressors. As a consequence, a typical circuit contains no more than roughly seven repressor-based gates per cell. A possible way around this scalability problem is to distribute the computation among multiple cell types, each of which implements a small subcircuit, which communicate among themselves using diffusible small molecules (DSMs). Examples of DSMs are those employed by quorum sensing systems in bacteria. This paper focuses on systematic ways to implement this distributed approach, in the context of the evaluation of arbitrary Boolean functions. The unique characteristics of genetic circuits and the properties of DSMs require the development of new Boolean synthesis methods, distinct from those classically used in electronic circuit design. In this work, we propose a fast algorithm to synthesize distributed realizations for any Boolean function, under constraints on the number of gates per cell and the number of orthogonal DSMs. The method is based on an exact synthesis algorithm to find the minimal circuit per cell, which in turn allows us to build an extensive database of Boolean functions up to a given number of inputs. For concreteness, we will specifically focus on circuits of up to 4 inputs, which might represent, for example, two chemical inducers and two light inputs at different frequencies. Our method shows that, with a constraint of no more than seven gates per cell, the use of a single DSM increases the total number of realizable circuits by at least 7.58-fold compared to centralized computation. Moreover, when allowing two DSM’s, one can realize 99.995% of all possible 4-input Boolean functions, still with at most 7 gates per cell. The methodology introduced here can be readily adapted to complement recent genetic circuit design automation software. A toolbox that uses the proposed algorithm was created and made available at https://github. com/sontaglab/DBC/.  more » « less
Award ID(s):
1849588
PAR ID:
10175714
Author(s) / Creator(s):
; ; ; ; ;
Date Published:
Journal Name:
ACS Synthetic Biology
ISSN:
2161-5063
Format(s):
Medium: X
Sponsoring Org:
National Science Foundation
More Like this
  1. Abstract

    DNA devices have been shown to be capable of evaluating Boolean logic. Several robust designs for DNA circuits have been demonstrated. Some prior DNA‐based circuits are use‐once circuits since the gate motifs of the DNA circuits get permanently destroyed as a side effect of the computation, and hence cannot respond correctly to subsequent changes in inputs. Other DNA‐based circuits use a large reservoir of buffered gates to replace the working gates of the circuit and can be used to drive a finite number of computation cycles. In many applications of DNA circuits, the inputs are inherently asynchronous, and this necessitates that the DNA circuits be asynchronous: the output must always be correct regardless of differences in the arrival time of inputs. This paper demonstrates: 1) renewable DNA circuits, which can be manually reverted to their original state by addition of DNA strands, and 2) time‐responsive DNA circuits, where if the inputs change over time, the DNA circuit can recompute the output correctly based on the new inputs, that are manually added after the system has been reset. The properties of renewable, asynchronous, and time‐responsiveness appear to be central to molecular‐scale systems; for example, self‐regulation in cellular organisms.

     
    more » « less
  2. A functionally complete Boolean operator is sufficient for computational circuits of arbitrary complexity. We connected YES (buffer) with NOT (inverter) and two NOT four-way junction (4J) DNA gates to obtain IMPLY and NAND Boolean functions, respectively, each of which represents a functionally complete gate. The results show a technological path towards creating a DNA computational circuit of arbitrary complexity based on singleton NOT or a combination of NOT and YES gates, which is not possible in electronic computers. We, therefore, concluded that DNA-based circuits and molecular computation may offer opportunities unforeseen in electronics.

     
    more » « less
  3. Pang, J. (Ed.)
    Rationally designed molecular circuits describable by well-mixed chemical reaction kinetics can realize arbitrary Boolean function computation yet differ significantly from their electronic counterparts. The design, preparation, and purification of new molecular components poses significant barriers. Consequently, it is desirable to synthesize circuits from an existing “fridge” inventory of distinguishable parts, while satisfying constraints such as component compatibility. Heuristic synthesis techniques intended for large electronic circuits often result in non-optimal molecular circuits, invalid circuits that violate domain-specific constraints, or circuits that cannot be built with the current inventory. Existing “exact” synthesis techniques are able to find minimal feedforward Boolean circuits with complex constraints, but do not map to distinguishable inventory components. We present the Fridge Compiler, an SMT-based approach to find optimal Boolean circuits within a given molecular inventory. Empirical results demonstrate the Fridge Compiler’s versatility in synthesizing arbitrary Boolean functions using three different molecular architectures, while satisfying user-specified constraints. We showcase the successful synthesis of all 256 three-bit and 65,536 four-bit predicate functions using a large custom inventory, with worst-case completion times of only seconds on a modern laptop. In addition, we introduce a unique class of cyclic molecular circuits that cover a larger number of Boolean functions than their conventional counterparts over a common inventory, often with significantly smaller implementations. Importantly, and absent in previous approaches specific to molecular circuits, the Fridge Compiler is logically sound, complete, and optimal for the user-specified cost function and component inventory. 
    more » « less
  4. Due to nucleic acid's programmability, it is possible to realize DNA structures with computing functions, and thus a new generation of molecular computers is evolving to solve biological and medical problems. Pioneered by Milan Stojanovic, Boolean DNA logic gates created the foundation for the development of DNA computers. Similar to electronic computers, the field is evolving towards integrating DNA logic gates and circuits by positioning them on substrates to increase circuit density and minimize gate distance and undesired crosstalk. In this minireview, we summarize recent developments in the integration of DNA logic gates into circuits localized on DNA substrates. This approach of all‐DNA integrated circuits (DNA ICs) offers the advantages of biocompatibility, increased circuit response, increased circuit density, reduced unit concentration, facilitated circuit isolation, and facilitated cell uptake. DNA ICs can face similar challenges as their equivalent circuits operating in bulk solution (bulk circuits), and new physical challenges inherent in spatial localization. We discuss possible avenues to overcome these obstacles. 
    more » « less
  5. Abstract

    We study two-qubit circuits over the Clifford+CS gate set, which consists of the Clifford gates together with the controlled-phase gate CS = diag(1, 1, 1, i). The Clifford+CS gate set is universal for quantum computation and its elements can be implemented fault-tolerantly in most error-correcting schemes through magic state distillation. Since non-Clifford gates are typically more expensive to perform in a fault-tolerant manner, it is often desirable to construct circuits that use few CS gates. In the present paper, we introduce an efficient and optimal synthesis algorithm for two-qubit Clifford+CS operators. Our algorithm inputs a Clifford+CS operatorUand outputs a Clifford+CS circuit forU, which uses the least possible number of CS gates. Because the algorithm is deterministic, the circuit it associates to a Clifford+CS operator can be viewed as a normal form for that operator. We give an explicit description of these normal forms and use this description to derive a worst-case lower bound of$$5{{\rm{log}}}_{2}(\frac{1}{\epsilon })+O(1)$$5log2(1ϵ)+O(1)on the number of CS gates required toϵ-approximate elements of SU(4). Our work leverages a wide variety of mathematical tools that may find further applications in the study of fault-tolerant quantum circuits.

     
    more » « less