A Framework for Computing Discrete-Time Systems and Functions using DNA

Abstract

Due to the recent advances in the field of synthetic biology, molecular computing has emerged as a non-conventional computing technology. A broad range of computational processes has been considered for molecular implementation. In this dissertation, we investigate the development of molecular systems for performing the following computations: signal processing, Markov chains, polynomials, and mathematical functions. First, we present a \textit{fully asynchronous} framework to design molecular signal processing algorithms. The framework maps each delay unit to two molecular types, i.e., first-type and second-type, and provides a 4-phase scheme to synchronize data flow for any multi-input/multi-output signal processing system. In the first phase, the input signal and values stored in all delay elements are consumed for computations. Results of computations are stored in the first-type molecules corresponding to the delay units and output variables. During the second phase, the values of the first-type molecules are transferred to the second-type molecules for the output variable. In the third phase, the concentrations of the first-type molecules are transferred to the second-type molecules associated with each delay element. Finally, in the fourth phase, the output molecules are collected. The method is illustrated by synthesizing a simple finite-impulse response (FIR) filter, an infinite-impulse response (IIR) filter, and an 8-point real-valued fast Fourier transform (FFT). The simulation results show that the proposed framework provides faster molecular signal processing systems compared to prior frameworks. We then present an overview of how continuous-time, discrete-time and digital signal processing systems can be implemented using molecular reactions. We also present molecular sensing systems where molecular reactions are used to implement analog-to-digital converters (ADCs) and digital-to-analog converters (DACs). These converters can be used to design mixed-signal processing molecular systems. A complete example of the addition of two molecules using digital implementation is described where the concentrations of two molecules are converted to digital by two 3-bit ADCs, and the 4-bit output of the digital adder is converted to analog by a 4-bit DAC. Furthermore, we describe implementation of other forms of molecular computation. We propose an approach to implement any first-order Markov chain using molecular reactions in general and DNA in particular. The Markov chain consists of two parts: a set of states and state transition probabilities. Each state is modeled by a unique molecular type, referred to as a data molecule. Each state transition is modeled by a unique molecular type, referred to as a control molecule, and a unique molecular reaction. Each reaction consumes data molecules of one state and produces data molecules of another state. The concentrations of control molecules are initialized according to the probabilities of corresponding state transitions in the chain. The steady-state probability of the Markov chain is computed by the equilibrium concentration of data molecules. We demonstrate our method for the Gambler’s Ruin problem as an instance of the Markov chain process. We analyze the method according to both the stochastic chemical kinetics and the mass-action kinetics model. Additionally, we propose a novel {\em unipolar molecular encoding} approach to compute a certain class of polynomials. In this molecular encoding, each variable is represented using two molecular types: a \mbox{type-0} and a \mbox{type-1}. The value is the ratio of the concentration of type-1 molecules to the sum of the concentrations of \mbox{type-0} and \mbox{type-1} molecules. With the new encoding, CRNs can compute any set of polynomial functions subject only to the limitation that these polynomials can be expressed as linear combinations of Bernstein basis polynomials with positive coefficients less than or equal to 1. The proposed encoding naturally exploits the expansion of a power-form polynomial into a Bernstein polynomial. We present molecular encoders for converting any input in a standard representation to the fractional representation, as well as decoders for converting the computed output from the fractional to a standard representation. Lastly, we expand the unipolar molecular encoding for bipolar molecular encoding and propose simple molecular circuits that can compute multiplication and scaled addition. Using these circuits, we design molecular circuits to compute more complex mathematical functions such as $e^{-x}$, $\sin (x)$, and sigmoid$(x)$. According to this approach, we implement a molecular perceptron as a simple artificial neural network.