### 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 language | English (US) |
---|---|

Title of host publication | Conference Record of 51st Asilomar Conference on Signals, Systems and Computers, ACSSC 2017 |

Editors | Michael B. Matthews |

Publisher | Institute of Electrical and Electronics Engineers Inc. |

Pages | 478-483 |

Number of pages | 6 |

ISBN (Electronic) | 9781538618233 |

DOIs | |

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 |

### Publication series

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

Volume | 2017-October |

### Other

Other | 51st Asilomar Conference on Signals, Systems and Computers, ACSSC 2017 |
---|---|

Country | United States |

City | Pacific Grove |

Period | 10/29/17 → 11/1/17 |

### Fingerprint

### Keywords

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

### Cite this

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

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

*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

}

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 -