TY - GEN

T1 - Markov chain computations using molecular reactions

AU - Salehi, Sayed Ahmad

AU - Riedel, Marc

AU - Parhi, Keshab K

N1 - Publisher Copyright:
© 2015 IEEE.
Copyright:
Copyright 2016 Elsevier B.V., All rights reserved.

PY - 2015/9/9

Y1 - 2015/9/9

N2 - Markov chains are commonly used in numerous signal processing and statistical modeling applications. This paper describes an approach to implement any first-order Markov chain using molecular reactions in general and DNA in particular. Markov chain consists of two parts: a set of states, and state transition probabilities. Each state is modeled by a unique molecular type, referred as a data molecule. Each state transition is modeled by a unique molecular type, referred 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 Markov chain is computed by equilibrium concentration of data molecules. We demonstrate our method for the Gambler's Ruin problem as an instance of the Markov chain process. Both stochastic chemical kinetics and mass-action kinetics validate the computed probabilities using the proposed model. The molecular reactions are then mapped to DNA strand displacement reactions. The error in the probability of ruin computed by the proposed model is shown to be less than 1% for DNA strand displacement reactions.

AB - Markov chains are commonly used in numerous signal processing and statistical modeling applications. This paper describes an approach to implement any first-order Markov chain using molecular reactions in general and DNA in particular. Markov chain consists of two parts: a set of states, and state transition probabilities. Each state is modeled by a unique molecular type, referred as a data molecule. Each state transition is modeled by a unique molecular type, referred 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 Markov chain is computed by equilibrium concentration of data molecules. We demonstrate our method for the Gambler's Ruin problem as an instance of the Markov chain process. Both stochastic chemical kinetics and mass-action kinetics validate the computed probabilities using the proposed model. The molecular reactions are then mapped to DNA strand displacement reactions. The error in the probability of ruin computed by the proposed model is shown to be less than 1% for DNA strand displacement reactions.

KW - DNA strand-displacement

KW - Gambler's ruin problem

KW - Markov chain

KW - Molecular computation

KW - molecular reaction

UR - http://www.scopus.com/inward/record.url?scp=84961380494&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=84961380494&partnerID=8YFLogxK

U2 - 10.1109/ICDSP.2015.7251963

DO - 10.1109/ICDSP.2015.7251963

M3 - Conference contribution

AN - SCOPUS:84961380494

T3 - International Conference on Digital Signal Processing, DSP

SP - 689

EP - 693

BT - 2015 IEEE International Conference on Digital Signal Processing, DSP 2015

PB - Institute of Electrical and Electronics Engineers Inc.

T2 - IEEE International Conference on Digital Signal Processing, DSP 2015

Y2 - 21 July 2015 through 24 July 2015

ER -