Excerpt

Introduction

There is a sense in which chemical reactions perform computation, transducing energy as various molecules interact and alter one another and their environment. This idea of molecular computation provides multiple avenues of exploration as we as a species investigate various alternative notions of computation and their accompanying architectures: understanding the computational class of various reaction paradigms (Doty and Zhu 2018), implementing digital computation using chemical reactions (Soloveichik et al. 2008), mimicking chemical reactions using designer DNA sequences and their interactions (Soloveichik, Seelig, and Winfree 2010), and understanding the thermodynamic efficiency of computations performed by cells (Kempes et al. 2017).

We can interpret a number of biochemical reaction motifs as implementing an algorithm, often in an approximate or obfuscated way. For example, the process whereby a cell transitions from inactive to active mitosis is implemented by a robust biochemical switching mechanism: cyclin-dependent kinase (Cdk). At a structural level, this mechanism can be interpreted as a robust and biologically feasible implementation of an algorithm known as approximate majority (AM), which provides the asymptotically fastest way to reach a consensus between two possible outcomes across all members of a population (Cardelli and Csikász-Nagy 2012). As the name suggests, the final outcome approximately matches the opinion of the initial majority. This is an example of an algorithmic interpretation of a biochemical motif providing insight into the relationship between the structure of the underlying reactions and the overall function of the motif.

In recent work, Cardelli, Kwiatkowska, and Whitby (2018) go on to show how certain simple reaction motifs structurally related to AM provide a basis for performing asynchronous computation using chemical reaction networks (CRNs). The reliance of synchronous logic on a global clock makes molecular implementation difficult. This difficulty is bypassed in asynchronous logic using a Muller C-element, which can be utilized to synchronize various components.

Bibliography

Aris, R. 1965. “Prolegomena to the Rational Analysis of Systems of Chemical Reactions.” Archive for Rational Mechanics and Analysis 19 (2): 81–99.

Baez, J. C., and B. S. Pollard. 2017. “A Compositional Framework for Reaction Networks.” Reviews in Mathematical Physics 29 (09): 1750028.

Banaji, M., and G. Craciun. 2010. “Graph-theoretic Criteria for Injectivity and Unique Equilibria in General Chemical Reaction Systems.” Advances in Applied Mathematics 44 (2): 168–184.

Cardelli, L. 2014. “Morphisms of Reaction Networks That Couple Structure to Function.” BMC Systems Biology 8 (1): 84.

Cardelli, L., and A. Csikász-Nagy. 2012. “The Cell Cycle Switch Computes Approximate Majority.” Scientific Reports 2:656.

Cardelli, L., M. Kwiatkowska, and M. Whitby. 2018. “Chemical Reaction Network Designs for Asynchronous Logic Circuits.” Natural Computing 17 (1): 109–130.

Cardelli, L., M. Tribastone, M. Tschaikowski, and A. Vandin. 2017. “Comparing chemical reaction networks: A categorical and algorithmic perspective.” Theoretical Computer Science (December).

Craciun, G., Y. Tang, and M. Feinberg. 2006. “Understanding Bistability in Complex Enzyme-Driven Reaction Networks.” Proceedings of the National Academy of Sciences of the United States of America 103 (23): 8697–8702.

Doty, D., and S. Zhu. 2018. “Computational Complexity of Atomic Chemical Reaction Networks.” In SOFSEM 2018: Theory and Practice of Computer Science, edited by A. M. Tjoa, L. Bellatreche, S. Biffl, J. van Leeuwen, and J. Wiedermann, 212–226. Cham, Switzerland: Springer International.

Fong, B. 2015. “Decorated Cospans.” Theory and Applications of Categories 30 (33): 1096–1120.

Fong, B., and D. I. Spivak. 2018. “Hypergraph Categories.” arXiv 1806.08304.

Kempes, C. P., D. Wolpert, Z. Cohen, and J. Pérez-Mercader. 2017. “The thermodynamic efficiency of computations made in cells across the range of life.” arXiv preprint arXiv:1706.05043.

Mertzios, G. B., S. E. Nikoletseas, C. L. Raptopoulos, and P. G. Spirakis. 2014. “Determining Majority in Networks with Local Interactions and Very Small Local Memory.” In International Colloquium on Automata, Languages, and Programming, 871–882. New York: Springer.

Peterson, J. L. 1977. “Petri Nets.” ACM Computing Surveys (CSUR) 9 (3): 223–252.

Polettini, M., and M. Esposito. 2014. “Irreversible Thermodynamics of Open Chemical Networks. I. Emergent Cycles and Broken Conservation Laws.” Journal of Chemical Physics 141 (2): 07B610_1.

Rao, R., and M. Esposito. 2016. “Nonequilibrium Thermodynamics of Chemical Reaction Networks: Wisdom from Stochastic Thermodynamics.” Physical Review X 6 (4): 041064.

Schnakenberg, J. 1976. “Network Theory of Microscopic and Macroscopic Behavior of Master Equation Systems.” Reviews of Modern Physics 48 (4): 571.

Shinar, G., and M. Feinberg. 2012. “Concordant Chemical Reaction Networks.” Mathematical Biosciences 240 (2): 92–113.

Soloveichik, D., M. Cook, E. Winfree, and J. Bruck. 2008. “Computation with Finite Stochastic Chemical Reaction Networks.” Natural Computing 7 (4): 615–633.

Soloveichik, D., G. Seelig, and E. Winfree. 2010. “DNA as a Universal Substrate for Chemical Kinetics.” Proceedings of the National Academy of Sciences of the United States of America 107 (12): 5393–5398.

Spars, J., and S. Furber. 2002. Principles of Asynchronous Circuit Design. New York: Springer.

BACK TO The Energetics of Computing in Life & Machines