Molecular computation of complex Markov chains with self-loop state transitions

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

Research output: Chapter in Book/Report/Conference proceedingConference contribution

Abstract

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.

Original languageEnglish (US)
Title of host publicationConference Record of 51st Asilomar Conference on Signals, Systems and Computers, ACSSC 2017
EditorsMichael B. Matthews
PublisherInstitute of Electrical and Electronics Engineers Inc.
Pages478-483
Number of pages6
ISBN (Electronic)9781538618233
DOIs
StatePublished - Apr 10 2018
Event51st Asilomar Conference on Signals, Systems and Computers, ACSSC 2017 - Pacific Grove, United States
Duration: Oct 29 2017Nov 1 2017

Publication series

NameConference Record of 51st Asilomar Conference on Signals, Systems and Computers, ACSSC 2017
Volume2017-October

Other

Other51st Asilomar Conference on Signals, Systems and Computers, ACSSC 2017
CountryUnited States
CityPacific Grove
Period10/29/1711/1/17

Fingerprint

Markov chains
State Transition
Markov processes
Markov chain
Molecules
molecules
DNA
deoxyribonucleic acid
strands
Transition Probability
transition probabilities

Keywords

  • DNA strand-displacement
  • Markov chain
  • Molecular computation
  • molecular reaction
  • self-loop state transition

Cite this

Salehi, S. A., Riedel, M. D., & Parhi, K. K. (2018). Molecular computation of complex Markov chains with self-loop state transitions. In M. B. Matthews (Ed.), Conference Record of 51st Asilomar Conference on Signals, Systems and Computers, ACSSC 2017 (pp. 478-483). [8335385] (Conference Record of 51st Asilomar Conference on Signals, Systems and Computers, ACSSC 2017; Vol. 2017-October). Institute of Electrical and Electronics Engineers Inc.. https://doi.org/10.1109/ACSSC.2017.8335385

Molecular computation of complex Markov chains with self-loop state transitions. / Salehi, Sayed Ahmad; Riedel, Marc D.; Parhi, Keshab K.

Conference Record of 51st Asilomar Conference on Signals, Systems and Computers, ACSSC 2017. ed. / Michael B. Matthews. Institute of Electrical and Electronics Engineers Inc., 2018. p. 478-483 8335385 (Conference Record of 51st Asilomar Conference on Signals, Systems and Computers, ACSSC 2017; Vol. 2017-October).

Research output: Chapter in Book/Report/Conference proceedingConference contribution

Salehi, SA, Riedel, MD & Parhi, KK 2018, Molecular computation of complex Markov chains with self-loop state transitions. in MB Matthews (ed.), Conference Record of 51st Asilomar Conference on Signals, Systems and Computers, ACSSC 2017., 8335385, Conference Record of 51st Asilomar Conference on Signals, Systems and Computers, ACSSC 2017, vol. 2017-October, Institute of Electrical and Electronics Engineers Inc., pp. 478-483, 51st Asilomar Conference on Signals, Systems and Computers, ACSSC 2017, Pacific Grove, United States, 10/29/17. https://doi.org/10.1109/ACSSC.2017.8335385
Salehi SA, Riedel MD, Parhi KK. Molecular computation of complex Markov chains with self-loop state transitions. In Matthews MB, editor, Conference Record of 51st Asilomar Conference on Signals, Systems and Computers, ACSSC 2017. Institute of Electrical and Electronics Engineers Inc. 2018. p. 478-483. 8335385. (Conference Record of 51st Asilomar Conference on Signals, Systems and Computers, ACSSC 2017). https://doi.org/10.1109/ACSSC.2017.8335385
Salehi, Sayed Ahmad ; Riedel, Marc D. ; Parhi, Keshab K. / Molecular computation of complex Markov chains with self-loop state transitions. Conference Record of 51st Asilomar Conference on Signals, Systems and Computers, ACSSC 2017. editor / Michael B. Matthews. Institute of Electrical and Electronics Engineers Inc., 2018. pp. 478-483 (Conference Record of 51st Asilomar Conference on Signals, Systems and Computers, ACSSC 2017).
@inproceedings{905e93e0b6034427a31cb0da0acfe71f,
title = "Molecular computation of complex Markov chains with self-loop state transitions",
abstract = "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.",
keywords = "DNA strand-displacement, Markov chain, Molecular computation, molecular reaction, self-loop state transition",
author = "Salehi, {Sayed Ahmad} and Riedel, {Marc D.} and Parhi, {Keshab K.}",
year = "2018",
month = "4",
day = "10",
doi = "10.1109/ACSSC.2017.8335385",
language = "English (US)",
series = "Conference Record of 51st Asilomar Conference on Signals, Systems and Computers, ACSSC 2017",
publisher = "Institute of Electrical and Electronics Engineers Inc.",
pages = "478--483",
editor = "Matthews, {Michael B.}",
booktitle = "Conference Record of 51st Asilomar Conference on Signals, Systems and Computers, ACSSC 2017",

}

TY - GEN

T1 - Molecular computation of complex Markov chains with self-loop state transitions

AU - Salehi, Sayed Ahmad

AU - Riedel, Marc D.

AU - Parhi, Keshab K.

PY - 2018/4/10

Y1 - 2018/4/10

N2 - 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.

AB - 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.

KW - DNA strand-displacement

KW - Markov chain

KW - Molecular computation

KW - molecular reaction

KW - self-loop state transition

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

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

U2 - 10.1109/ACSSC.2017.8335385

DO - 10.1109/ACSSC.2017.8335385

M3 - Conference contribution

AN - SCOPUS:85051001195

T3 - Conference Record of 51st Asilomar Conference on Signals, Systems and Computers, ACSSC 2017

SP - 478

EP - 483

BT - Conference Record of 51st Asilomar Conference on Signals, Systems and Computers, ACSSC 2017

A2 - Matthews, Michael B.

PB - Institute of Electrical and Electronics Engineers Inc.

ER -