This paper describes a systematic method for molecular implementation of complex Markov chain processes with self-loop transitions. Generally speaking, Markov chains consist 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. As we show in this paper, the produced data molecules are the same as the reactant data molecules for self-loop transitions. Although the reactions corresponding to self-loop transitions do not change the molecular concentrations of the data molecules, they are required in order for the system to compute probabilities correctly. The concentrations of control molecules are initialized according to the probabilities of corresponding state transitions in the chain. The steady-state probability of Markov chain is computed by equilibrium concentration of data molecules. We demonstrate our method for a molecular design of a seven-state Markov chain as an instance of a complex Markov chain process with self-loop state transitions. The molecular reactions are then mapped to DNA strand displacement reactions. Using the designed DNA system we compute the steady-state probability matrix such that its element (i, j) corresponds to the long-term probability of staying in state j, given it starts from state i. For example, the error in the computed probabilities is shown to be less than 2% for DNA strand-displacement reactions.
|Title of host publication||Conference Record of 51st Asilomar Conference on Signals, Systems and Computers, ACSSC 2017|
|Editors||Michael B. Matthews|
|Number of pages||6|
|State||Published - Apr 10 2018|
|Event||51st Asilomar Conference on Signals, Systems and Computers, ACSSC 2017 - Pacific Grove, United States|
Duration: Oct 29 2017 → Nov 1 2017
|Name||Conference Record of 51st Asilomar Conference on Signals, Systems and Computers, ACSSC 2017|
|Conference||51st Asilomar Conference on Signals, Systems and Computers, ACSSC 2017|
|Period||10/29/17 → 11/1/17|
Bibliographical noteFunding Information:
This work is supported by the National Science Foundation under grant number CCF-1423407.
© 2017 IEEE.
Copyright 2018 Elsevier B.V., All rights reserved.
- DNA strand-displacement
- Markov chain
- Molecular computation
- molecular reaction
- self-loop state transition
ASJC Scopus subject areas
- Control and Optimization
- Computer Networks and Communications
- Hardware and Architecture
- Signal Processing
- Biomedical Engineering