Logic Gates - Emma Garren

Background: Logic Gates and Truth Tables

A logic gate, the building block for digital circuits, is a computing unit that performs a logical operation on one or more inputs and produces a single output. Gates are identified by their function, and each type of logic gate can be represented with a distinctive symbol. Inputs to outputs are read from left to right. A small circle on the right indicates the inversion of the output. A double line on the left indicates that the function is "exclusive."

A truth table is a useful way to describe the behavior or function of a logic gate. Logic states for both inputs and outputs are designated with 0's and 1's. Click here to see some common logic gates and their truth tables.

Logic gates can be placed in parallel or serial combinations in order to perform more complex functions. Here, two parallel outputs, D and E, act as inputs to the function of output Q:

Figure 1. Combination of logic gates: Q = D OR E = (NOT(A OR B)) OR (B AND C)

(Image by John Hewes, 2007)

Logic Gates in Synthetic Biology

Synthetic biology applies many of the principles of engineering to the field of biology in order to create biological devices which can ultimately be integrated into increasingly complex systems. These principles include standardization of parts, modularity, abstraction, reliability, predictability, and uniformity (Adrianantoandro et al., 2006). The application of engineering principles to biology is complicated by the inability to predict the functions of even simple devices and modules within the cellular environment. Some of the confounding factors are gene expression noise, mutation, cell death, undefined and changing extracellular environments, and interactions with the cellular context (Adrianantoandro et al., 2006).

While for digital logic, inputs are either on or off (1 or 0), biological logic is sometimes leads to intermediate induction levels (Voigt, 2006). However, due to their sigmoid-shaped dose response curves, gene regulation systems can be considered genetic analog-digital converters. The signal is either ON or OFF for a wide range of input concentrations, with the system changing between the ON and OFF states in a relatively small concentration window (Kramer et al., 2004).

In synthetic biology, logic gates are created by engineering the biochemical reactions that regulate various cellular processes, such as transcription, translation, protein phosphorylation, allosteric regulation, ligand/receptor binding, and enzymatic reactions. Although the diversity of biochemical reactions can make it difficult to combine different devices, these logic gates can be used to build complex systems with functions that have many practical applications. Mathematical modeling is used to predict the dynamics of the signaling and regulatory networks resulting from the logic gates.

Biomolecular Logic Gates: In Vitro

In vitro studies have been used to design combinations of molecules that have emergent properties related to information processing--molecular computing devices. Both the inputs and outputs consist of molecular species, with the output being a biologically active molecule. The extent to which these devices will be used with the cellular context is unclear--however, they are bound to inspire new directions for research in synthetic biology, and have potential applications in biochemical sensing, pathway engineering, and medical diagnosis and treatment.

Protein-based Logic Gates

Enzymes:

• Two coupled enzymes perform in parallel the 'AND' and 'InhibAND' logic gate operations. (Baron et al., 2006) Summary:
• Logic Gates and Elementary Computing by Enzymes. (Baron et al., 2006) Summary:

Synthetic Peptide Networks:

• Boolean Logic Functions of a Synthetic Peptide Network. (Ashkenasy and Ghadiri, 2004) Summary:

Signaling Proteins:

• Engineering synthetic signaling proteins with ultrasensitive input/output control. (Dueber et al., 2007) Summary: Many eukaryotic signaling proteins have natural, modular "input" and "output" domains: the "inputs" participate in steric or conformational autoinhibitory reactions, and the "outputs" are catalytically, constitutively active domains. Simple synthetic switch functions can be engineered by swapping the regulatory and catalytic domains. This paper describes the engineering of "ultrasensitive switches" for use in more complex regulatory networks, by combining multiple identical modular autoinhibitory domains that function cooperatively. Mathematical models are used to simulate the behavior of these multivalent domain switches and explore the effect of autoinhibitory interaction number and affinity: an external input ligand alters the population distribution of active vs. inactive enzymes, where individual states are "fully repressed in the presence of any intramolecular interactions and fully active only in the absence of all intramolecular interactions" (661). The predictions from the models are tested using synthetic switches built by linking the catalytic output domain of the protein N-WASP to novel peptide input, demonstrating that it is possible to engineer nonlinear switches based on the cooperativity of simple autoinhibitory components. Other complex switches, such as ones that integrate three input signals, have also been built using this approach.

Deoxyribozyme-based Logic Gates

Deoxyribozyme-based gates are controlled by oligonucleotide inputs, and have been used to engineer logic gates that perform:

• multiple logical operations in parallel
• single-step signaling cascades
• a feedback cycle that acts as an exponential chain reaction

These papers provide examples of deoxyribozyme-based logic gates:

• Deoxyribozyme-Based Ligase Logic Gates and Their Initial Circuits. (Stojanovic et al., 2005) Summary:
• Deoxyribozyme-Based Three-Input Logic Gates and Construction of a Molecular Full Adder. (Lederman et al., 2006) Summary:
• Construction of Molecular Logic Gates with a DNA-Cleaving Deoxyribozyme (Chen et al., 2006) Summary:

DNA-based Logic Gates

• Modular Multi-Level Circuits from Immobilized DNA-Based Logic Gates. (Frezza et al., 2007) Summary:
• DNA Logic Gates Based on Structural Polymorphism of Telomere DNA Molecules Responding to Chemical Input Signals. (Miyoshi et al., 2006) Summary:
• Photonic boolean logic gates based on DNA aptamers. (Yoshida and Yokobayashi, 2006) Summary:
• Parallel Molecular Computations of Pairwise Exclusive-OR (XOR) Using DNA "String Tile" Self-Assembly. (Yan et al., 2003) Summary:

An autonomous molecular computer for logical control of gene expression. (Benenson et al., 2004)

Overview:

This gate uses sequence recognition to control enzyme catalysis of covalent bond formation and breakage, producing an ssDNA output.

• Input: Specific combination mRNA levels, serving as a simple model of a disease state (cancer)
• Output: “Drug” (or drug repressor) in the form of a single-stranded DNA sequence with known anti-cancer activity

Design:

Figure 2. Logical design of the molecular computer.

An in vitro system is designed to recognize a specific combination of mRNA levels as its inputs, and performs a logical operation that results in the production of a molecule that can affect gene expression. The input mRNA levels have been designed to mimic a simplistic version of gene expression modeling cancer, and the output is a drug-like ssDNA with known anticancer activity. Therefore, the molecular computer is analogous to "a computational version of 'diagnosis'" (424).

Function:

Figure 3. Operation of the molecular computer.

The molecular computers consist of a double-stranded DNA sequence with unique 7-bp sequences that recognize the “input” RNA. Each mRNA indicator is processed one at a time. An “inactivation tag” results in the displacement of the transition molecule, which destroys the computation fragment. An “activation tag” results in activation of the transition molecule. There are two separate molecular computers working simultaneously—one that releases the drug (a specific single-stranded DNA sequence) upon “positive diagnosis,” and another that releases the drug suppressor in response to “negative diagnosis.” The drug (or drug repressor) is incorporated into the DNA fragment as an inactive loop, protected by the double-stranded recognition sequences. If all of the transitions are “positive,” the ultimate output is drug administration (release of ssDNA). If any of the steps results in a “negative” transition, the output is a drug repressor. The design is flexible in that any sufficiently long mRNA molecule can be used as an indicator, and any ssDNA or short RNA molecule (up to at least 21-bp) can be designed as the output. PCR was used to for the experimental demonstration of both diagnosis and drug administration, and it is shown that the amount of active drug increases with the confidence of positive diagnosis. Future work could test the effectiveness of using alternate inputs (such as proteins), alternate outputs (such as RNA interference), as well as testing the function of the molecular computer in vivo.

Enzyme-Free Nucleic Acid Logic Circuits. (Seelig et al., 2006)

Overview:

• Input: 2 DNA strands - F(in) and G(in)
• Gate: 3 DNA strands - E(q), F(f), and G
• Output: Fluorescence - release of F(f)

Nucleic acid devices are simplified by the predicability of base pairing. Although previous research has engineered nucleic acid logic switches based on hybridization and conformational changes in vivo, and this paper designs chemical logic gates that are capable of being combined into large, reliable circuits. These logic gates embody the following digital design principles: logic, cascading, restoration, fan-out, and modularity.

The benefits of this approach are that both inputs and outputs are in the same form, which makes cascading possible (the output for one gate serves as the input for the next gate in the circuit).

Gate function is entirely determined by base pairing and breaking. Each gate is composed of one or more gate strands, and one output strand.

Figure 4. Two-input AND gate.

Restoration:

• When a gate fails to produce enough output when triggered, restoration increases a moderate output amount to the full activation level.
• When a gate "leaks" by spontaneously releasing the output strand, restoration decreases the small output amount to a negligible level.
• Gates for amplification and thresholding were used to implement signal restoration.

Modularity and Scalability:

• Eleven gates (AND, OR, sequence translation, input amplification, and signal restoration) were used to compose a large, complex circuit.

Cellular Logic Gates: In Vivo

As stated above, there the cellular environment possesses many characteristics that complicate the implementation of biomolecular logic circuits, such as gene expression noise, mutation, cell death, undefined and changing extracellular environments, and interactions with the cellular context. Some researchers are trying to engineer the "minimal cell," either through top-down or bottom-up approaches, in order to produce a living unit that can perform logical operations without some of these excess confounding factors. These efforts were recently reviewed by Forster and Church (2006). However, many efforts at building cellular logic gates have succeeded, both in prokaryotes and eukaryotes, with wide-ranging applications. Below are summaries of a few examples.

Synthetic Oscillators and Switches

(Image from Figure 1 of Drubin et al., 2007. Permission pending.)

Figure 5. Schematic representation of the function of various engineered biological switches.

A. Repressilator (Elowitz and Leibler, 2000). The "repressilator," or synthetic cellular oscillator, can be built from a string of three repressors, each acting the repress the expression of the next gene in the circuit. Oscillatory output is read by GFP expression regulated by one of the repressors (in this case, tetracycline). The design is analogous to a series of three NOT gates.

B. Toggle switch (Gardner et al., 2000). A toggle switch can be designed from two repressor systems that cross-regulate each other's promoters, and is analogous to the construction of two independent IF gates. It is useful as a pathway module to create more complex programmable cells. Toggle switches can be used to engineer cellular memory.

D. RNA-based antiswitch. When the engineered RNA is bound to an inducer ligand, the structure changes to either expose or hide a region of RNA that is homologous to a region of the target mRNA (encompassing the translational start site). Thus, when the antisense region is exposed, translation of target mRNA is repressed. Synthetic switches in both eukaryotes (antiswitches) and prokaryotes (riboregulators and riboswitches) can be mediated via RNA devices.

Environmental signal integration by a modular AND gate. (Anderson et al., 2007)

AND gates allow cells to integrate multiple signals and can increase their specificity in sensing the environment. This is especially useful for engineering cells to sense environments that are not encountered naturally, or those that are too specific to be identified by a single environmental signal.

A logic gate achieves modularity when it can be used as a self-contained component of more complex systems, and is designed to interface with multiple different inputs and outputs. This paper demonstrates a modular AND gate in E. coli that uses promoters for both the inputs and the output. This design, unlike that of previously engineered prokaryotic logic gates, makes it relatively easy to use the same gate for different inputs and outputs.

Overview:

• Inputs:

1. Promoter that drives the expression of the gene for T7 RNA polymerase (T7ptag), containing two amber stop codons that prevent translation under normal circumstances.
2. Promoter that drives the expression of the gene for the SupD amber suppressor (supD), which decodes the amber stop codons as serine, and allows for translation of T7 RNA polymerase.

• Output: Gene expressed under the T7 promoter, which requires functional translation of both T7 RNA polymerase and the SupD amber suppressor.

The fluorescence data (see [Figure 2. Function of the AND gate. Figure 2]) was used to parameterize a transfer function model that was derived in order to understand how the range of the input promoters affects the function of the circuit.

Figure 1. Schematic representation of AND gate.

• Input 1: P(sal) controls the expression supD gene, and is activated by the addition of salicylate (Sal).
• Input 2: P(BAD) controls T7 RNA polymerase gene, and is activated by the addition of arabinose (Ara). Because a strong RBS for T7ptag resulted in high levels of basal expression, the RBS was mutagenized and tuned by screening for the presence of output only when both inducers were present.
• Output: GFPmut3_LAA (fast-folding GFP with a degradation tag)

Figure 2. Function of the AND gate.

There is 1000-fold induction of fluorescence in the presence of high concentrations of both inducers, arabinose and salicylate.

Figure 6. Modularity of the AND gate.

The modularity of the AND gate is demonstrated by reconnecting the gate to new inputs (natural promoters), and a new output (desired phenotype).

A. Exchanging the inputs:

• Input 1: The lux promoter, which responds to the quorum signal AI-1.
• Input 2: The mgrB promoter, which responds to the absence of exogenous magnesium via the PhoPQ two-component system.

B. Exchanging the output:

• Output: The inv gene, coding for invasin, a protein that allows bacteria to invade mammalian cells.

BioLogic Gates Enable Logical Transcription Control in Mammalian Cells. (Kramer et al., 2004)

Transcription control modules, responsive to up to three small molecule inputs, were engineered in mammalian Chinese hamster ovary cells. These "BioLogic gates" provide the tools and building blocks to engineer more complex gene regulatory networks in eukaryotic cells. The gates use butyrolactone-, streptogramin-, tetracycline-, and macrolide-dependent transcription factors, each fused to a KRAB or VP16 repression domain.

1. NOT IF gate - two inputs
2. NOT IF IF gate - three inputs
3. NAND gate - parallel arrangement of two NOT gates
4. OR gate - parallel arrangement of two IF gates
5. NOR gate - constructed from two NOT gates in consecutive order
6. INVERTER gate - combination of two independent IF gates, acts as the inverse of the NOT IF gate

Cellular Logic with Orthogonal Ribosomes. (Rackham and Chin, 2006)

Overview:

Two-input logic gates were constructed in E. coli based on the interactions between synthetic O-rRNA and O-mRNA.

• Input: Orthogonal ribosomes (O-ribosomes), which translate O-mRNA, but do not significantly translate any of the thousands of cellular transcripts bearing cellular RBS sequences.
• Gate: Orthogonal mRNAs (O-mRNAs), which contain ribosome-binding sequences (RBSs) that do not direct the translation of downstream genes by endogenous ribosomes.
• Output: Fluorescence.

Three distinct O-ribosome-O-mRNA pairs were isolated, with molecular specificities for independent function. This was accomplished through directed evolution in two steps:

1. A library of new potential RBSs were placed upstream of a novel fusion of the genes encoding chloramphenicol acetyltransferase and uracil phosphoribosyltransferase, and screened against 5-fluorouracil to select for the O-mRNA sequences that were not translated by endogenous ribosomes.
2. The selected O-mRNAs were combined with a library of mutated 16s rRNA sequences, and these cells were grown in the presence of chloramphenicol to screen for those in which the mutant ribosomes translated the O-mRNAs.

The O-ribosome-O-mRNA pairs can be used to control almost any molecular interaction that can be linked to gene expression. In this case they were used to build an AND gate composed of two O-mRNA sequences: O-mRNA-A-omega, encoding the omega fragment of beta-galactosidase, and O-mRNA-C-alpha, encoding the alpha fragment of beta-galactosidase. Synthesis and assembly of a complete beta-galactosidase enzyme (both fragments) results in the cells hydrolyzing FDG into F (fluorescein), which is detected with a fluorometer. Cells programmed with both of the corresponding O-ribosome inputs, O-rRNA-A and O-rRNA-C, exhibited a 20-fold increase in fluorescence when compared with cells containing any other rRNA combinations.

Figure 1. O-ribosomes and Boolean logic.

Applications and Future Directions

Logic gates can be used to design increasingly complex circuits with far-reaching applications in:

• Genetic engineering
• Nanotechnology
• Industrial Fermentation
• Metabolic engineering:
  • increasingly complex synthetic gene circuits might be used to engineer and optimize novel metabolic pathways.
• Medicine:
  • Bacteria to deliver cancer treatment: the integration of multiple inputs can help bacteria sense and respond to increasingly specific environments, such as that of a tumor in the human body.
  • Pharmaceuticals: produced through metabolic engineering; "smart" drug delivery.

References

• Anderson, J. C., Voigt, C. A., Arkin, A. P. (2007). Environmental signal integration by a modular AND gate. Mol Syst Biol. 3:133. Abstract
• Andrianantoandro, E., Subhayu, B., Karig, D. K., Weiss, R. (2006). Synthetic biology: new engineering rules for an emerging discipline. Mol Syst. Biol. 2:2006.0028. Abstract
• Ashkenasy, G., Ghadiri, M. R. (2004). Boolean Logic Functions of a Synthetic Peptide Network. J Am Chem Soc. 126(36):11140-1. Abstract
• Baron, R., Lioubashevski, O., Katz, E., Niazov, T., Willner, I. (2006). Two coupled enzymes perform in parallel the “AND” and “InhibAND” logic gate operations. Org Biomol Chem. 4(6): 989-91. Abstract
• Baron, R., Lioubashevski, O., Katz, E., Niazov, T., Willner, I. (2006). Logic gates and elementary computing by enzymes. J Phys Chem A. 110(27):8548-53. Abstract
• Benenson, Y., Binyamin, G., Ben-Dor, U., Adar, R., Shapiro, E. (2004). An autonomous molecular computer for logical control of gene expression. Nature. 429:423-429. Abstract
• Boczko, E., Gedeon, T., Mischaikow, K. (2007). Dynamics of a simple regulatory switch. J Math Biol. 55(5-6):679-719. Abstract
• Chen, X., Wang, Y., Liu, Q., Zhang, Z., Fan, C., He, L. (2006). Construction of molecular logic gates with a DNA-cleaving deoxyribozyme. Angew Chem Int Ed Engl. 45(11):1759-62. Abstract
• Davidson, E.A., Ellington, A.D. (2007). Synthetic RNA circuits. Nat Chem Biol. 3(1):23-8. Abstract
• Dueber, J.E., Mirsky, E.A., Lim, W.A. (2007). Engineering synthetic signaling proteins with ultrasensitive input/output control. Nat Biotechnol. 25(6):660-662. Abstract
• Drubin, D. A., Way, J. C., Silver, P. A. (2007). Designing biological systems. Genes Dev. 21(3):242-54. Abstract
• Elowitz, M. B., & Leibler, S. (2000). A synthetic oscillatory network of transcriptional regulators. Nature. 403(6767):335-8. Abstract
• Farfel, J., Stefanovic, D. (2005). Towards practical biomolecular computers using microfluidic deoxyribozyme logic gate networks. University of New Mexico.
• Forster, A.C., Church G.M. (2006). Towards synthesis of a minimal cell. Mol Sys Biol. 2(45):1-10. PDF
• Frezza, B.M., Cockroft, S. L., Ghadiri, M.R. (2007). Modular Multi-level Circuits from Immobilized DNA-Based Logic Gates. J Am Chem Soc. (Epub ahead of print) Abstract
• Gardner, T.S., Cantor, C.R., Collins, J.J. (2000). Construction of a genetic toggle switch in Escherichia coli. Nature. 403(6767):338-42. Abstract
• Heinemann, M., Panke, S. (2006). Synthetic biology—putting engineering into biology. Bioinformatics. 22(22):2790-9. Abstract
• Kaznessis, Y. N. (2007). Models for synthetic biology. BMC Syst Biol. 1(1):47. Abstract
• Kramer, B. P., Fischer, C., Fussenegger, M. (2004). BioLogic Gates Enable Transcription Control in Mammalian Cells. Biotechnol Bioeng. 87(4):478-84. Abstract
• Lederman, H., Macdonald, J., Stefanovic, D., Stojanovic, M. N. (2006). Deoxyribozyme-based three-input logic gates and construction of a molecular full adder. Biochemistry. 45(4):1194-9. Abstract
• Narayanaswamy, R., Ellington, A.D. (2006). Engineering RNA-based circuits. Handb Exp Pharmacol. (173):423-45. Abstract
• Rackham, O., Chin, J. W. (2005). Cellular logic with orthogonal ribosomes. JACS 1227:17584-85. Abstract
• Rackham, O., Chin, J.W. (2006) Synthesizing cellular networks from evolved ribosome-mRNA pairs. Biochem Soc Trans. 34(2):328-9. Abstract
• Sayut, D.J., Kambam, P.K., Sun, L. (2007). Engineering and applications of genetic circuits. Mol Biosyst. 3(12):835-840. Abstract
• Seelig G., Soloveichik, D., Zhang, D. Y., Winfree, E., (2006). Enzyme-free nucleic acid logic circuits. Science. 314(5805): 1585-8. Abstract
• Stojanovic, M. N., Semova, S., Kolpashchikov, D., Macdonald, J., Morgan, C., Stefanovic, D. (2005). Deoxyribozyme-based ligase logic gates and their initial circuits. J Am Chem Soc. 127(19):6914-5. Abstract
• Voigt, C. A. (2006). Genetic parts to program bacteria. Curr Opin Biotechnol. 17:548-557. Abstract
• Wall, M. E., Hlavacek, W. S., Savageau, M. A. (2004). Design of gene circuits: lessons from bacteria. Nat Rev Genet. 5(1):34-42. Abstract
• Yan, H., Feng, L., LaBean, T.H., Reif, J.H. (2003). Parallel Molecular Computations of Pairwise Exclusive-Or (XOR) Using DNA "String Tile" Self-Assembly. J Am Chem Soc. 125:14246-14247. Abstract
• Yoshida, W., Yokobayashi, Y. (2007). Photon Boolean logic gates based on DNA aptamers. Chem Commun (Camb). (2):195-7. Abstract