More Like this

1. DEVELOPING INTEGRATED DNA MOLECULAR CIRCUITS

   Bardales, Andrea C (December 2024, University of Central Florida)

   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. There is evidence that genetic heredity diseases and cancer can be the result of genetic heterogeneity, thus there is a need for diagnostics and therapeutic tools with multiplex and smart components to compute all the molecular drivers. DNA molecular computers mimics electronic computers by programming synthetic nucleic acids to perform similarly to central processing units. Considering how the evolution of integrated circuits made possible the revolution of silicon-based computers, integrated DNA molecular circuits can be developed to allow modular designing and scale to complex DNA nano-processors. This dissertation covers the development of four-way junction (4J) DNA logic gates that can be wired to result in functionally complete gates, and their immobilization on a modular DNA board that serves as a scaffold for logic gate integration, fast signal processing, and cascading. Connecting 4J DNA logic gates YES and NOT resulted in OR, NAND, and IMPLY logic circuits; the three circuits can operate under the input of miRNAs, either oncogenic or/and tumor-suppressors, and give two possible diagnoses: healthy or cancerous. The DNA board can expand as the DNA circuit grows in the number of integrated 4J units. Signal propagation across a wired of 4J YES logic gates showed signal completion in < 3 min, accounting for a signal propagation rate of 4.5 nm/min and that up to 6 units can be cascaded before the signal dissipates. Lastly, an approach to chemically ligate all oligonucleotide components of the DNA molecular device is presented, in which we also found a route for the bioconjugation of 5’ to 5’ and 3’ to 3’ oligonucleotides. 

   more » « less
2. Circuit Optimization using Arithmetic Table Lookups

   https://doi.org/10.1145/3729258  

   Malik, Raghav; Paranjape, Vedant; Kulkarni, Milind (June 2025, Proceedings of the ACM on Programming Languages)

   Fully Homomorphic Encryption (FHE) is a cryptographic technique that enables privacy-preserving computation. State-of-the-art Boolean FHE implementations provide a very low-level interface, usually exposing a limited set of Boolean gates that programmers must use to write their FHE applications. This programming model is unnecessarily restrictive: many Boolean FHE schemes supportprogrammable bootstrapping, an operation that allows evaluation of an arbitrary fixed-size lookup table. However, most modern FHE compilers are only capable of reasoning about traditional Boolean circuits, and therefore struggle to take full advantage of programmable bootstrapping. We present COATL, an FHE compiler that makes use of programmable bootstrapping to produce circuits that are smaller and more efficient than their traditional Boolean counterparts. COATL generates circuits usingarithmetic lookup tables, a novel abstraction we introduce for reasoning about computations in Boolean FHE programs. We demonstrate on a variety of benchmarks that COATL can generate circuits that run up to 1.5× faster than those generated by other state-of-the-art compilation strategies. 

   more » « less
3. Circuit complexity and functionality: A statistical thermodynamics perspective

   https://doi.org/10.1073/pnas.2415913122  

   Chamon, Claudio; Ruckenstein, Andrei E; Mucciolo, Eduardo R; Canetti, Ran (June 2025, Proceedings of the National Academy of Sciences)

   Circuit complexity, defined as the minimum circuit size required for implementing a particular Boolean computation, is a foundational concept in computer science. Determining circuit complexity is believed to be a hard computational problem. Recently, in the context of black holes, circuit complexity has been promoted to a physical property, wherein the growth of complexity is reflected in the time evolution of the Einstein-Rosen bridge (“wormhole”) connecting the two sides of an anti-de Sitter “eternal” black hole. Here, we are motivated by an independent set of considerations and explore links between complexity and thermodynamics for functionally equivalent circuits, making the physics-inspired approach relevant to real computational problems, for which functionality is the key element of interest. In particular, our thermodynamic framework provides an alternative perspective on the obfuscation of programs of arbitrary length—an important problem in cryptography—as thermalization through recursive mixing of neighboring sections of a circuit, which can be viewed as the mixing of two containers with “gases of gates.” This recursive process equilibrates the average complexity and leads to the saturation of the circuit entropy, while preserving functionality of the overall circuit. The thermodynamic arguments hinge on ergodicity in the space of circuits which we conjecture is limited to disconnected ergodic sectors due to fragmentation. The notion of fragmentation has important implications for the problem of circuit obfuscation as it implies that there are circuits of same size and functionality that cannot be connected via a polynomial number of local moves. Furthermore, we argue that fragmentation is unavoidable unless the complexity classes NP and coNP coincide, a statement that implies the collapse of the polynomial hierarchy of computational complexity theory to its first level. 

   more » « less
4. Manufacturing Reusable NAND Logic Gates and Their Initial Circuits for DNA Nanoprocessors

   https://doi.org/10.1002/chem.202003959  

   Molden, Tatiana_A; Grillo, Marcella_C; Kolpashchikov, Dmitry_M (December 2020, Chemistry – A European Journal)

   Abstract DNA‐based computers can potentially analyze complex sets of biological markers, thereby advancing diagnostics and the treatment of diseases. Despite extensive efforts, DNA processors have not yet been developed due, in part, to limitations in the ability to integrate available logic gates into circuits. We have designed a NAND gate, which is one of the functionally complete set of logic connectives. The gate's design avoids stem‐loop‐folded DNA fragments, and is capable of reusable operations in RNase H‐containing buffer. The output of the gate can be translated into RNA‐cleaving activity or a fluorescent signal produced either by a deoxyribozyme or a molecular beacon probe. Furthermore, three NAND‐gate‐forming DNA strands were crosslinked by click chemistry and purified in a simple procedure that allowed ≈10¹³gates to be manufactured in 16 h, with a hands‐on time of about 30 min. Two NAND gates can be joined into one association that performs a new logic function simply by adding a DNA linker strand. Approaches developed in this work could contribute to the development of biocompatible DNA logic circuits for biotechnological and medical applications. 

   more » « less
5. Distributed Implementation of Boolean Functions by Transcriptional Synthetic Circuits

   https://doi.org/10.1021/acssynbio.0c00228  

   Al-Radhawi, M. Ali; Tran, Anh Phong; Ernst, Elizabeth A.; Chen, Tianchi; Voigt, Christopher A.; Sontag, Eduardo D. (June 2020, ACS Synthetic Biology)

   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