Markov chain computations using molecular reactions

Sayed Ahmad Salehi, Marc D. Riedel, Keshab K. Parhi

Research output: Chapter in Book/Report/Conference proceedingConference contributionpeer-review

21 Scopus citations

Abstract

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.

Original languageEnglish
Title of host publication2015 IEEE International Conference on Digital Signal Processing, DSP 2015
Pages689-693
Number of pages5
ISBN (Electronic)9781479980581, 9781479980581
DOIs
StatePublished - Sep 9 2015
EventIEEE International Conference on Digital Signal Processing, DSP 2015 - Singapore, Singapore
Duration: Jul 21 2015Jul 24 2015

Publication series

NameInternational Conference on Digital Signal Processing, DSP
Volume2015-September

Conference

ConferenceIEEE International Conference on Digital Signal Processing, DSP 2015
Country/TerritorySingapore
CitySingapore
Period7/21/157/24/15

Bibliographical note

Publisher Copyright:
© 2015 IEEE.

Keywords

  • DNA strand-displacement
  • Gambler's ruin problem
  • Markov chain
  • Molecular computation
  • molecular reaction

ASJC Scopus subject areas

  • Signal Processing

Fingerprint

Dive into the research topics of 'Markov chain computations using molecular reactions'. Together they form a unique fingerprint.

Cite this