Top

Natural Computing

Published in:

11-04-2019

Molecular computing for Markov chains

Authors: Chuan Zhang, Ziyuan Shen, Wei Wei, Jing Zhao, Zaichen Zhang, Xiaohu You

Published in: Natural Computing | Issue 3/2020

Activate our intelligent search to find suitable subject content or patents.

search-config

AI-assisted search

Off

Abstract

In this paper, it is presented a methodology for implementing arbitrarily constructed time-homogenous Markov chains with biochemical systems. Not only discrete but also continuous-time Markov chains are allowed to be computed. By employing chemical reaction networks as a programmable language, molecular concentrations serve to denote both input and output values. One reaction network is elaborately designed for each chain. The evolution of species’ concentrations over time well matches the transient solutions of the target continuous-time Markov chain, while equilibrium concentrations can indicate the steady state probabilities. Additionally, second-order Markov chains are considered for implementation, with bimolecular reactions rather than unary ones. An original scheme is put forward to compile unimolecular systems to DNA strand displacement reactions for the sake of future physical implementations. Deterministic, stochastic and DNA simulations are provided to enhance correctness, validity and feasibility.

previous article A proposal of quantum data representation to improve the discrimination power

next article A class of discrete dynamical systems with properties of both cellular automata and L-systems

Dont have a licence yet? Then find out more about our products and how to get one now:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

über 102.000 Bücher
über 537 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Finance + Banking
Management + Führung
Marketing + Vertrieb
Maschinenbau + Werkstoffe
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

inform now

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 390 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Maschinenbau + Werkstoffe

Jetzt Wissensvorsprung sichern!

inform now

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 340 Zeitschriften

aus folgenden Fachgebieten:

Bauwesen + Immobilien
Business IT + Informatik
Finance + Banking
Management + Führung
Marketing + Vertrieb
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

inform now

Adleman LM (1994) Molecular computation of solutions to combinatorial problems. Science 266(5187):1021CrossRef

Anderson DF, Kurtz TG (2011) Continuous time Markov Chain models for chemical reaction networks. Springer, New York, pp 3–42

Bennett CH (1982) The thermodynamics of computation—a review. Int J Theor Phys 21(12):905CrossRef

Berry G, Boudol G (1992) The chemical abstract machine. Theor Comput Sci 96(1):217MathSciNetMATHCrossRef

Bolch G, Greiner S, de Meer H, Trivedi KS (2006) Queueing networks and Markov chains: modeling and performance evaluation with computer science applications. Wiley, New YorkMATHCrossRef

Cardelli L (2013) Two-domain DNA strand displacement. Math Struct Comput Sci 23(2):247MathSciNetMATHCrossRef

Cardona M, Colomer M, Conde J, Miret J, Miró J, Zaragoza A (2005) Markov chains: computing limit existence and approximations with DNA. Biosystems 81(3):261CrossRef

Chen HL, Doty D, Soloveichik D (2014) Deterministic function computation with chemical reaction networks. Nat Comput 13(4):517MathSciNetMATHCrossRef

Ching WK, Huang X, Ng MK, Siu TK (2013) Markov chains. Springer, Berlin, pp 141–176CrossRef

DeGroot MH, Schervish MJ (2012) Probability and statistics. Addison-Wesley, Boston

Érdi P, Tóth J (1989) Mathematical models of chemical reactions: theory and applications of deterministic and stochastic models. Manchester University Press, ManchesterMATH

Gillespie DT (1976) A general method for numerically simulating the stochastic time evolution of coupled chemical reactions. J Comput Phys 22(4):403MathSciNetCrossRef

Hjelmfelt A, Weinberger ED, Ross J (1991) Chemical implementation of neural networks and turing machines. Proc Natl Acad Sci 88(24):10983MATHCrossRef

Horn F, Jackson R (1972) General mass action kinetics. Arch Ration Mech Anal 47(2):81MathSciNetCrossRef

Jiang H, Salehi SA, Riedel MD, Parhi KK (2013a) Discrete-time signal processing with DNA. ACS Synth Biol 2(5):245CrossRef

Jiang H, Riedel MD, Parhi KK (2013b) Proceedings of the IEEE/ACM international conference on computer-aided design (ICCAD), pp 721–727

Jiang H, Riedel M, Parhi KK (2011) Proceedings of the design automation conference, pp 836–841

Kannan KS, Vallinayagam V, Venkatesan P (2007) Markov chain Monte Carlo methods in molecular computing. In: IJISE

Kharam AP, Jiang H, Riedel MD, Parhi KK (2011) Proceedings of the Pacific symposium on biocomputing, pp 302–313

Kurtz TG (1972) The relationship between stochastic and deterministic models for chemical reactions. J Chem Phys 57(7):2976CrossRef

Liekens A, Fernando C (2007) Turing complete catalytic particle computers. In: Advances in artificial life, pp 1202–1211

Lund K, Manzo AJ, Dabby N, Michelotti N, Johnson-Buck A, Nangreave J, Taylor S, Pei R, Stojanovic MN, Walter NG, Winfree E, Yan H (2010) Molecular robots guided by prescriptive landscapes. Nature 465(7295):206CrossRef

Magnasco MO (1997) Chemical kinetics is turing universal. Phys Rev Lett 78(6):1190CrossRef

McQuarrie DA (1967) Stochastic approach to chemical kinetics. J Appl Probab 4(03):413MathSciNetMATHCrossRef

Ouyang Q, Kaplan PD, Liu S, Libchaber A (1997) DNA solution of the maximal clique problem. Science 278(5337):446CrossRef

Păun G, Rozenberg G (2002) A guide to membrane computing. Theor Comput Sci 287(1):73MathSciNetMATHCrossRef

Qian L, Winfree E (2011) Scaling up digital circuit computation with DNA strand displacement cascades. Science 332(6034):1196CrossRef

Rothemund PWK (1995) A DNA and restriction enzyme implementation of turing machines. DNA Based Comput 27:75MathSciNetCrossRef

Salehi SA, Riedel MD, Parhi KK (2014) Proceedings of the IEEE Asilomar conference on signals, systems and computers, pp 1767–1772

Salehi SA, Riedel MD, Parhi KK (2015a) Proceedings of the IEEE international conference on digital signal processing (DSP), pp 689–693

Salehi SA, Jiang H, Riedel MD, Parhi KK (2015b) Molecular sensing and computing systems. IEEE Trans Mol Biol Multi Scale Commun 1(3):249CrossRef

Salehi SA, Parhi KK, Riedel MD (2016) Chemical reaction networks for computing polynomials. ACS Synth Biol 6(1):76CrossRef

Shen Z, Zhang C, Ge L, Zhuang Y, Yuan B, You X (2016) Proceedings of the IEEE international workshop on signal processing systems (SiPS) IEEE, pp 27–32

Soloveichik D (2009) CRNSimulator Mathematica Package. http://users.ece.utexas.edu/~soloveichik/crnsimulator.html. Accessed 20 Dec 2018

Soloveichik D, Cook M, Winfree E, Bruck J (2008) Computation with finite stochastic chemical reaction networks. Nat Comput 7(4):615MathSciNetMATHCrossRef

Soloveichik D, Seelig G, Winfree E (2010) DNA as a universal substrate for chemical kinetics. Proc Natl Acad Sci 107(12):5393CrossRef

Stemmer WP (1995) The evolution of molecular computation. Science 270(5241):1510CrossRef

Van Kampen NG (1995) Stochastic processes in physics and chemistry. Elsevier, LondonMATH

Yurke B, Mills AP (2003) Using DNA to power nanostructures. Genet Program Evolv Mach 4(2):111CrossRef

Zhang DY, Winfree E (2009) Control of DNA strand displacement kinetics using toehold exchange. J Am Chem Soc 131(47):17303CrossRef

Title: Molecular computing for Markov chains
Authors: Chuan Zhang
Ziyuan Shen
Wei Wei
Jing Zhao
Zaichen Zhang
Xiaohu You
Publication date: 11-04-2019
Publisher: Springer Netherlands
Published in: Natural Computing / Issue 3/2020
Print ISSN: 1567-7818
Electronic ISSN: 1572-9796
DOI: https://doi.org/10.1007/s11047-019-09736-8

Springer Professional

Abstract

Please log in to get access to your license.

Dont have a licence yet? Then find out more about our products and how to get one now:

Springer Professional "Wirtschaft+Technik"

Springer Professional "Technik"

Springer Professional "Wirtschaft"

Other articles of this Issue 3/2020

A pattern-driven solution for designing multi-objective evolutionary algorithms

Population-based bio-inspired algorithms for cluster ensembles optimization

A novel context-free grammar for the generation of PSO algorithms

A proposal for tuning the parameter in -integrals for application in fuzzy rule-based classification systems

Swarm optimization clustering methods for opinion mining

Preface

Premium Partner