Modular and Robust Computation with Deterministic Chemical Reaction Networks

Thumbnail Image
Date
2016-01-01
Authors
Klinge, Titus
Major Professor
Advisor
James I. Lathrop
Jack H. Lutz
Committee Member
Journal Title
Journal ISSN
Volume Title
Publisher
Altmetrics
Authors
Research Projects
Organizational Units
Organizational Unit
Journal Issue
Is Version Of
Versions
Series
Department
Computer Science
Abstract

In this thesis, we present four results concerning the computing capabilities of chemical reaction networks (CRNs) under deterministic mass action semantics: (1) we introduce a modular method for computing concentration signals using CRN extension operators; (2) we present a thorough analysis of two CRN signal restoration algorithms that prevent certain concentration signals from degrading over time; (3) we introduce a new model called input/output chemical reaction networks (I/O CRNs) which generalizes the CRN model to allow receiving input signals over time; and (4) we investigate what I/O CRNs can compute robustly and prove that I/O CRNs are capable of robustly simulating any nondeterministic finite automaton (NFA).

CRN extension operators are operations that can be applied to a CRN to add extra functionality without affecting its original behavior. We show that common operators such as addition, multiplication, integration, and many others can be characterized as CRN extension operators. By iteratively applying these extensions, complex concentration signals can be modularly constructed from simple CRNs. To explore the full generality of these extensions, we introduce a notion of weakly CRN-computable signals and show that any CRN that can weakly compute a signal can be extended to exactly compute it.

The two signal restoration algorithms that we investigate are related to the approximate majority algorithm for population protocols originally developed by Angluin, Aspnes, and Eisenstat. Under deterministic semantics, these algorithms are commonly used to prevent discrete memory from deteriorating over time. We investigate the behavior of these algorithms in the presence of adversarial reactions and show that under modest conditions they are capable of maintaining discrete memory indefinitely. We also give tight analytical bounds on how these algorithms evolve over time.

The I/O CRN model that we introduce has two important impacts. (1) Concentration signals are a more natural way to provide arbitrarily long inputs to a CRN. Classical CRNs are restricted to encoding inputs into the initial state of the system which makes providing an arbitrarily long input (e.g. a binary string) quite difficult. (2) It promotes modular design of CRNs. Designing chemical systems from modular components that communicate via concentration signals is now possible, and we demonstrate its effectiveness in multiple constructions including our I/O CRN implementation of NFAs.

Our notion of robustness requires that an I/O CRN tolerate perturbations with respect to four things, namely, its initial state, rate constants, input signal, and the measurement of its output signal. We investigate what I/O CRNs are capable of computing under this notion of robustness, and we prove that I/O CRNs can robustly compute the regular languages by simulating an NFA in real time.

Comments
Description
Keywords
Citation
Source
Copyright
Fri Jan 01 00:00:00 UTC 2016