| Publications about 'Boolean functions' |
| Articles in journal or book chapters |
| Implementing logic functions in living cells is a fundamental area of interest among synthetic biologists. The goal of designing biochemical circuits in synthetic biology is to make modular and tractable systems that perform well with predictable behaviors. Developing formalisms towards the design of such systems has proven to be difficult with the diverse retroactive effects that appear with respect to the context of the cell. Repressor-based circuits have various applications in biosynthesis, therapeutics, and bioremediation. Particularly using CRISPRi, competition for components of the system (unbound dCas9) can affect the achievable dynamic range of repression. Moreover, the toxicity of dCas9 via non-specific binding inhibits high levels of expression and limits the performance of genetic circuits. In this work, we study the computation of Boolean functions through CRISPRi based circuits built out of NOT and NOR gates. We provide algebraic expressions that allow us to evaluate the steady-state behaviors of any realized circuit. Our mathematical analysis reveals that the effective non-cooperativity of any given gate is a major bottleneck for increasing the dynamic range of the outputs. Further, we find that under the condition of competition between promoters for dCas9, certain circuit architectures perform better than others depending on factors such as circuit depth, fan-in, and fan-out. We pose optimization problems to evaluate the effects engineerable parameter values to find regimes in which a given circuit performs best. This framework provides a mathematical template and computational library for evaluating the performance of repressor-based circuits with a focus on effective cooperativity. |
| Powerful distributed computing can be achieved by communicating cells that individually perform simple operations. We have developed design software to divide a large genetic circuit across cells as well as the genetic parts to implement the subcircuits in their genomes. These tools were demonstrated using a 2-bit version of the MD5 hashing algorithm, an early predecessor to the cryptographic functions underlying cryptocurrency. One iteration requires 110 logic gates, which were partitioned across 66 strains of Escherichia coli, requiring the introduction of a total of 1.1 Mb of recombinant DNA into their genomes. The strains are individually experimentally verified to integrate their assigned input signals, process this information correctly, and propagate the result to the cell in the next layer. This work demonstrates the potential to obtain programmable control of multicellular biological processes. |
| Minimal synthesis of Boolean functions is an NP-hard problem, and heuristic approaches typically give suboptimal circuits. However, in the emergent field of synthetic biology, genetic logic designs that use even a single additional Boolean gate can render a circuit unimplementable in a cell. This has led to a renewed interest in the field of optimal multilevel Boolean synthesis. For small numbers (1-4) of inputs, an exhaustive search is possible, but this is impractical for large circuits. In this work, we demonstrate that even though it is challenging to build a database of optimal implementations for anything larger than 4-input Boolean functions, a database of 4-input optimal implementations can be used to greatly reduce the number of logical gates required in larger heuristic logic synthesis implementations. The proposed algorithm combines the heuristic results with an optimal implementation database and yields average improvements of 5.16% for 5-input circuits and 4.54% for 6-input circuits on outputs provided by the logic synthesis tool extit{ABC}. In addition to the gains in the efficiency of the implemented circuits, this work also attests to the importance and practicality of the field of optimal synthesis, even if it cannot directly provide results for larger circuits. The focus of this work is on circuits made exclusively of 2-input NOR gates but the presented results are readily applicable to 2-input NAND circuits as well as (2-input) AND/NOT circuits. In addition, the framework proposed here is likely to be adaptable to other types of 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, which communicate among themselves using diffusible small molecules (DSMs) and each of which implements a small sub-circuit. 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. |
| We examine the power of constant depth circuits with sigmoid threshold gates for computing boolean functions. It is shown that, for depth 2, constant size circuits of this type are strictly more powerful than constant size boolean threshold circuits (i.e. circuits with linear threshold gates). On the other hand it turns out that, for any constant depth d, polynomial size sigmoid threshold circuits with polynomially bounded weights compute exactly the same boolean functions as the corresponding circuits with linear threshold gates. |
This material is presented to ensure timely dissemination of scholarly and technical work. Copyright and all rights therein are retained by authors or by other copyright holders.
This document was translated from BibTEX by bibtex2html