A Reaction Network Scheme Which Implements Inference and Learning for Hidden Markov Models

Abhinav Singh; Carsten Wiuf; Abhishek Behera; Manoj Gopalkrishnan

doi:10.1007/978-3-030-26807-7_4

A Reaction Network Scheme Which Implements Inference and Learning for Hidden Markov Models

Abhinav Singh^*, Carsten Wiuf, Abhishek Behera, Manoj Gopalkrishnan

^*Corresponding author for this work

Department of Mathematical Sciences

2 Citations (Scopus)

Abstract

With a view towards molecular communication systems and molecular multi-agent systems, we propose the Chemical Baum-Welch Algorithm, a novel reaction network scheme that learns parameters for Hidden Markov Models (HMMs). Each reaction in our scheme changes only one molecule of one species to one molecule of another. The reverse change is also accessible but via a different set of enzymes, in a design reminiscent of futile cycles in biochemical pathways. We show that every fixed point of the Baum-Welch algorithm for HMMs is a fixed point of our reaction network scheme, and every positive fixed point of our scheme is a fixed point of the Baum-Welch algorithm. We prove that the â€œExpectationâ€� step and the â€œMaximizationâ€� step of our reaction network separately converge exponentially fast. We simulate mass-action kinetics for our network on an example sequence, and show that it learns the same parameters for the HMM as the Baum-Welch algorithm.

Original language	English
Title of host publication	DNA Computing and Molecular Programming - 25th International Conference, DNA 25, Proceedings
Editors	Yan Liu, Chris Thachuk
Number of pages	26
Publisher	Springer
Publication date	2019
Pages	54-79
ISBN (Print)	9783030268060
ISBN (Electronic)	9783030268077
DOIs	https://doi.org/10.1007/978-3-030-26807-7_4
Publication status	Published - 2019
Event	25th International Conference on DNA Computing and Molecular Programming, DNA 2019 - Seattle, United States Duration: 5 Aug 2019 → 9 Aug 2019

Conference

Conference	25th International Conference on DNA Computing and Molecular Programming, DNA 2019
Country/Territory	United States
City	Seattle
Period	05/08/2019 → 09/08/2019
Sponsor	International Society of Nanoscale Science, Computing, and Engineering, Microsoft Research (USA), National Science Foundation (USA), University of Washington

Series	Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume	11648 LNCS
ISSN	0302-9743

Access to Document

10.1007/978-3-030-26807-7_4

Cite this

Singh, A., Wiuf, C., Behera, A., & Gopalkrishnan, M. (2019). A Reaction Network Scheme Which Implements Inference and Learning for Hidden Markov Models. In Y. Liu, & C. Thachuk (Eds.), DNA Computing and Molecular Programming - 25th International Conference, DNA 25, Proceedings (pp. 54-79). Springer. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics) Vol. 11648 LNCS https://doi.org/10.1007/978-3-030-26807-7_4

A Reaction Network Scheme Which Implements Inference and Learning for Hidden Markov Models. / Singh, Abhinav; Wiuf, Carsten; Behera, Abhishek et al.

DNA Computing and Molecular Programming - 25th International Conference, DNA 25, Proceedings. ed. / Yan Liu; Chris Thachuk. Springer, 2019. p. 54-79 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), Vol. 11648 LNCS).

Research output: Chapter in Book/Report/Conference proceeding › Article in proceedings › Research › peer-review

Singh, A, Wiuf, C, Behera, A & Gopalkrishnan, M 2019, A Reaction Network Scheme Which Implements Inference and Learning for Hidden Markov Models. in Y Liu & C Thachuk (eds), DNA Computing and Molecular Programming - 25th International Conference, DNA 25, Proceedings. Springer, Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 11648 LNCS, pp. 54-79, 25th International Conference on DNA Computing and Molecular Programming, DNA 2019, Seattle, United States, 05/08/2019. https://doi.org/10.1007/978-3-030-26807-7_4

Singh A, Wiuf C, Behera A, Gopalkrishnan M. A Reaction Network Scheme Which Implements Inference and Learning for Hidden Markov Models. In Liu Y, Thachuk C, editors, DNA Computing and Molecular Programming - 25th International Conference, DNA 25, Proceedings. Springer. 2019. p. 54-79. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), Vol. 11648 LNCS). doi: 10.1007/978-3-030-26807-7_4

Singh, Abhinav ; Wiuf, Carsten ; Behera, Abhishek et al. / A Reaction Network Scheme Which Implements Inference and Learning for Hidden Markov Models. DNA Computing and Molecular Programming - 25th International Conference, DNA 25, Proceedings. editor / Yan Liu ; Chris Thachuk. Springer, 2019. pp. 54-79 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), Vol. 11648 LNCS).

@inproceedings{aaad50d2a8f84dcc9d227dc42bb17849,

title = "A Reaction Network Scheme Which Implements Inference and Learning for Hidden Markov Models",

abstract = "With a view towards molecular communication systems and molecular multi-agent systems, we propose the Chemical Baum-Welch Algorithm, a novel reaction network scheme that learns parameters for Hidden Markov Models (HMMs). Each reaction in our scheme changes only one molecule of one species to one molecule of another. The reverse change is also accessible but via a different set of enzymes, in a design reminiscent of futile cycles in biochemical pathways. We show that every fixed point of the Baum-Welch algorithm for HMMs is a fixed point of our reaction network scheme, and every positive fixed point of our scheme is a fixed point of the Baum-Welch algorithm. We prove that the {\^a}€{\oe}Expectation{\^a}€� step and the {\^a}€{\oe}Maximization{\^a}€� step of our reaction network separately converge exponentially fast. We simulate mass-action kinetics for our network on an example sequence, and show that it learns the same parameters for the HMM as the Baum-Welch algorithm.",

author = "Abhinav Singh and Carsten Wiuf and Abhishek Behera and Manoj Gopalkrishnan",

year = "2019",

doi = "10.1007/978-3-030-26807-7_4",

language = "English",

isbn = "9783030268060",

series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",

publisher = "Springer",

pages = "54--79",

editor = "Yan Liu and Chris Thachuk",

booktitle = "DNA Computing and Molecular Programming - 25th International Conference, DNA 25, Proceedings",

note = "25th International Conference on DNA Computing and Molecular Programming, DNA 2019 ; Conference date: 05-08-2019 Through 09-08-2019",

}

TY - GEN

T1 - A Reaction Network Scheme Which Implements Inference and Learning for Hidden Markov Models

AU - Singh, Abhinav

AU - Wiuf, Carsten

AU - Behera, Abhishek

AU - Gopalkrishnan, Manoj

PY - 2019

Y1 - 2019

N2 - With a view towards molecular communication systems and molecular multi-agent systems, we propose the Chemical Baum-Welch Algorithm, a novel reaction network scheme that learns parameters for Hidden Markov Models (HMMs). Each reaction in our scheme changes only one molecule of one species to one molecule of another. The reverse change is also accessible but via a different set of enzymes, in a design reminiscent of futile cycles in biochemical pathways. We show that every fixed point of the Baum-Welch algorithm for HMMs is a fixed point of our reaction network scheme, and every positive fixed point of our scheme is a fixed point of the Baum-Welch algorithm. We prove that the â€œExpectationâ€� step and the â€œMaximizationâ€� step of our reaction network separately converge exponentially fast. We simulate mass-action kinetics for our network on an example sequence, and show that it learns the same parameters for the HMM as the Baum-Welch algorithm.

AB - With a view towards molecular communication systems and molecular multi-agent systems, we propose the Chemical Baum-Welch Algorithm, a novel reaction network scheme that learns parameters for Hidden Markov Models (HMMs). Each reaction in our scheme changes only one molecule of one species to one molecule of another. The reverse change is also accessible but via a different set of enzymes, in a design reminiscent of futile cycles in biochemical pathways. We show that every fixed point of the Baum-Welch algorithm for HMMs is a fixed point of our reaction network scheme, and every positive fixed point of our scheme is a fixed point of the Baum-Welch algorithm. We prove that the â€œExpectationâ€� step and the â€œMaximizationâ€� step of our reaction network separately converge exponentially fast. We simulate mass-action kinetics for our network on an example sequence, and show that it learns the same parameters for the HMM as the Baum-Welch algorithm.

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

U2 - 10.1007/978-3-030-26807-7_4

DO - 10.1007/978-3-030-26807-7_4

M3 - Article in proceedings

AN - SCOPUS:85070695913

SN - 9783030268060

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 54

EP - 79

BT - DNA Computing and Molecular Programming - 25th International Conference, DNA 25, Proceedings

A2 - Liu, Yan

A2 - Thachuk, Chris

PB - Springer

T2 - 25th International Conference on DNA Computing and Molecular Programming, DNA 2019

Y2 - 5 August 2019 through 9 August 2019

ER -

A Reaction Network Scheme Which Implements Inference and Learning for Hidden Markov Models

Abstract

Conference

Access to Document

Other files and links

Fingerprint

Cite this