Symmetry structure in discrete models of biochemical systems: natural subsystems and the weak control hierarchy in a new model of computation driven by interactions. (English) Zbl 1353.92043

Summary: Interaction computing is inspired by the observation that cell metabolic/regulatory systems construct order dynamically, through constrained interactions between their components and based on a wide range of possible inputs and environmental conditions. The goals of this work are to (i) identify and understand mathematically the natural subsystems and hierarchical relations in natural systems enabling this and (ii) use the resulting insights to define a new model of computation based on interactions that is useful for both biology and computation. The dynamical characteristics of the cellular pathways studied in systems biology relate, mathematically, to the computational characteristics of automata derived from them, and their internal symmetry structures to computational power. Finite discrete automata models of biological systems such as the lac operon, the Krebs cycle and p53-mdm2 genetic regulation constructed from systems biology models have canonically associated algebraic structures (their transformation semigroups). These contain permutation groups (local substructures exhibiting symmetry) that correspond to ‘pools of reversibility’. These natural subsystems are related to one another in a hierarchical manner by the notion of ‘weak control’. We present natural subsystems arising from several biological examples and their weak control hierarchies in detail. Finite simple non-Abelian groups are found in biological examples and can be harnessed to realize finitary universal computation. This allows ensembles of cells to achieve any desired finitary computational transformation, depending on external inputs, via suitably constrained interactions. Based on this, interaction machines that grow and change their structure recursively are introduced and applied, providing a natural model of computation driven by interactions.


92C40 Biochemistry, molecular biology
68Q80 Cellular automata (computational aspects)
Full Text: DOI Link


[1] DOI: 10.1016/j.jda.2007.06.003 · Zbl 1153.90336
[2] DOI: 10.1186/1752-0509-7-135
[3] DOI: 10.1093/bioinformatics/btl210
[4] DOI: 10.1016/0022-5193(69)90015-0
[5] DOI: 10.1016/j.jtbi.2005.03.018
[6] Thomas R d’Ari. R 1990 Biological feedback. Boca Raton, FL: CRC Press.
[7] DOI: 10.1016/j.biosystems.2008.05.019
[8] Arbib MA (ed.). 1968 Algebraic theory of machines, languages, and semigroups. New York, NY: Academic Press.
[9] Dömösi P Nehaniv CL . 2005 Algebraic theory of finite automata networks: an introduction. SIAM Series on Discrete Mathematics and Applications, vol. 11. Philadelphia, PA: Society for Industrial and Applied Mathematics. · Zbl 1070.68095
[10] Holcombe W . 1982 Algebraic automata theory. Cambridge, UK: Cambridge University Press. · Zbl 0489.68046
[11] Rhodes J . 2010 Applications of automata theory and algebra via the mathematical theory of complexity to biology, physics, psychology, philosophy, and games. Singapore: World Scientific Press. Foreword by MW Hirsch, edited by CL Nehaniv. (Original version: University of California at Berkeley, Mathematics Library, 1971.)
[12] Rhodes J Steinberg B . 2008 The q-theory of finite semigroups. Berlin, Germany: Springer. · Zbl 1186.20043
[13] Eilenberg S . 1976 Automata, languages, and machines, vol. B. New York, NY: Academic Press. · Zbl 0359.94067
[14] DOI: 10.1016/S0019-9958(67)90228-8 · Zbl 0164.32301
[15] Schrödinger E . 1967 Statistical thermodynamics. Cambridge, UK: Cambridge University Press.
[16] Egri-Nagy A Nehaniv CL . 2010 SgpDec–software package for hierarchical coordinatization of groups and semigroups, implemented in the GAP computer algebra system, v. 0.7.29. See http://sgpdec.sf.net .
[17] Egri-Nagy A Mitchell JD Nehaniv CL . 2014 SgpDec: cascade (de)compositions of finite transformation semigroups and permutation groups. In Mathematical Software–ICMS 2014. Lecture Notes in Computer Science, vol. 8592, pp. 75–82. Berlin, Germany: Springer. · Zbl 1403.20002
[18] Egri-Nagy A Nehaniv CL . 2004 Algebraic hierarchical decomposition of finite state automata: comparison of implementations for Krohn–Rhodes theory. In Implementation and Application of Automata: 9th Int. Conf., CIAA 2004, Kingston, Canada, 22–24 July 2004. Lecture Notes in Computer Science, vol. 3317, pp. 315–316. Berlin, Germany: Springer Verlag.
[19] Nehaniv CL Quick P . 2007 Emulation of synchronous automata networks with dynamically changing topologies by asynchronous automata networks. In Proc. 7th International Workshop on Information Processing in Cells and Tissues (IPCAT 2007), Oxford, UK, 29–31st August 2007, pp. 20–29. Brno, Czech Republic: Tribun EU.
[20] Gécseg F . 1986 Products of automata. EATCS Monographs in Theoretical Computer Science 7. Berlin, Germany: Springer.
[21] DOI: 10.1090/S0002-9947-1965-0188316-1
[22] Gross T Sayama H . 2009 Adaptive networks: theory, models and applications. New England Complex Systems Institute Studies on Complexity. Berlin, Germany: Springer.
[23] Sayama H . 2007 Generative network automata: a generalized framework for modeling complex dynamical systems with autonomously varying topologies. In Proc. 1st IEEE Symp. on Artificial Life (IEEE ALIFE 2007), Honolulu, HI, 1–5 April 2007, pp. 214–221. Piscataway, NJ: IEEE.
[24] Sayama H Laramee C . 2009 Generative network automata: a generalized framework for modeling adaptive network dynamics using graph rewritings. In Adaptive networks: theory, models and applications (eds T Gross, H Sayama), pp. 311–332. Berlin, Germany: Springer.
[25] Clifford AH Preston GB . 1967 The algebraic theory of semigroups, vol. 1, 2nd edn. Mathematical Surveys, no. 7. Providence, RI: American Mathematical Society.
[26] Howie JM . 1995 Fundamentals of semigroup theory. London Mathematical Society Monographs New Series, vol. 12. Oxford, UK: Oxford University Press.
[27] Lallement G . 1979 Semigroups and combinatorial applications. New York, NY: Wiley. · Zbl 0421.20025
[28] Ptashne M . 1992 A genetic switch: {\(\lambda\)} and higher organisms, 2nd edn. Oxford, UK: Blackwell Publishers.
[29] Ptashne M Gann A . 2001 Genes and signals. Cold Spring Harbour, NY: Cold Spring Harbor Laboratory Press.
[30] DOI: 10.1162/artl.2008.14.3.14305
[31] Egri-Nagy A Nehaniv CL . 2011 On straight words and minimal permutators in finite transformation semigroups. In Implementation and Application of Automata: 15th Int. Conf., CIAA 2010, Manitoba, Canada, 12–15 August 2010 (eds M Domaratzki, K Salomaa). Lecture Notes in Computer Science, vol. 6482, pp. 115–124, Berlin, Germany: Springer. · Zbl 1297.68173
[32] Margulis L Sagan D . 2002 Early life: evolution on the precambrian Earth, 2nd edn. Sudbury, MA: Jones and Bartlett.
[33] Berg JM Tymoczko JL Stryer L . 2006 Biochemistry, 6th edn, international version. New York, NY: W. H. Freeman.
[34] DOI: 10.1016/j.biosystems.2008.05.018
[35] Egri-Nagy A Dini P Nehaniv CL Schilstra MJ . 2010 Transformation semigroups as constructive dynamical spaces. In Digital ecosystems. Lecture Notes of the Institute for Computer Sciences, Social Informatics and Telecommunications Engineering, vol. 67, pp. 245–265. Berlin, Germany: Springer.
[36] Van Leeuwen I Munro AJ Sanders I Staples O Lain S . 2010 Numerical and experimental analysis of the p53–mdm2 regulatory pathway. In Digital Ecosystems: Third International Conference, OPAALS 2010, Aracuju, Sergipe, Brazil, 22–23 March 2010 (eds FAB Colugnati, LCR Lopes, SFA Barretto), pp. 266–284. Lecture Notes of the Institute for Computer Sciences, Social-Informatics and Telecommunications Engineering, vol. 67. Aracaju, Sergipe, Brazil: Springer.
[37] Egri-Nagy A Nehaniv CL Schilstra MJ . 2009 Symmetry groups in biological networks. 8th Information Processing in Cells and Tissues Conf. (IPCAT09), Ascona, Switzerland, 5–9 April 2009. Journal preprint.
[38] Kastan MB Kuerbitz SJ . 1993 Control of G1 arrest after DNA damage. Environ. Health Perspect. 101, 55–58.
[39] Dini P Egri-Nagy A Nehaniv CL Schilstra MJ VanLeeuwen I Munro AJ Lain S . 2010 D1.4: Mathematical models of gene expression computing. OPAALS Deliverable, see http://www.lse.ac.uk/media@lse/research/OPAALS/D01.4_Mathematical_Models_of_Gene_Expression_Computing.pdf .
[40] Petri CA . 1962 Kommunikation mit Automaten. Schriften des IIM 2. Bonn, Germany: Institut für Instrumentelle Mathematik.
[41] Reisig W 2011 Petri nets: an introduction. Berlin, Germany: Springer. · Zbl 0555.68033
[42] DOI: 10.1006/dbio.2002.0619
[43] Horváth G . 2008 Functions and polynomials over finite groups from the computational perspective. PhD dissertation, University of Hertfordshire, Hatfield, UK.
[44] DOI: 10.1016/S0019-9958(66)90229-4 · Zbl 0202.31502
[45] DOI: 10.1090/S0002-9939-1965-0175971-0
[46] Jones HF . 1998 Groups, representations and physics, 2nd edn. Amsterdam, The Netherlands: IOP Publishing.
[47] Gell-Mann M Ne’eman Y . 1964 The eightfold way. New York, NY: Benjamin.
[48] Reboredo FA Galli G . 2005 Theory of alkyl-terminated silicon quantum dots. J. Phys. Chem. B 109, 1072–1078. (doi:10.1021/jp0462254)
[49] DOI: 10.1088/0957-4484/17/20/006
[50] Raman KV . 2004 Group theory and its applications to chemistry. New Delhi, India: Tata McGraw-Hill.
[51] DOI: 10.1088/0305-4470/7/17/004
[52] DOI: 10.1016/S0375-9601(00)00142-0
[53] Wegener I 1987 The complexity of Boolean functions. Stuttgart, Germany: John Wiley & Sons Ltd, B. G. Teubner. · Zbl 0623.94018
[54] Werner H . 1978 Einführung in die allgemeine algebra. Mannheim, Germany: Bibliographisches Institut. · Zbl 0383.08001
[55] DOI: 10.1145/96559.96569 · Zbl 0711.68092
[56] DOI: 10.1023/A:1021819602497 · Zbl 1023.12002
[57] Spector L Clark DM Lindsay I Barr B Klein J . 2008 Genetic programming for finite algebras. In Proc. Genetic and Evolutionary Computation Conference (GECCO-2008), pp. 1291–1298. New York, NY: ACM Press.
[58] DOI: 10.1007/BF01300543 · Zbl 0182.35201
[59] Horváth G Nehaniv CL . In press. Length of polynomials over finite groups. J. Comp. Syst. Sci.
[60] Fröhlich A . 1958 The near-ring generated by the inner automorphisms of a finite simple group. J. London Math. Soc. 33, 95–107. · Zbl 0084.26202
[61] Michler G . 2006 Theory of finite simple groups, vol. 1. Cambridge, UK: Cambridge University Press. · Zbl 1146.20011
[62] DOI: 10.1016/0022-0000(89)90037-8 · Zbl 0667.68059
[63] DOI: 10.1016/j.tcs.2008.08.028 · Zbl 1153.68020
[64] Horváth G Szabó Cs . 2011 The extended equivalence and equation solvability problems for groups. Discrete Math. Theor. Comput. Sci. 13, 23–32. · Zbl 1286.68194
[65] DOI: 10.1016/j.jpaa.2012.02.007 · Zbl 1259.20041
[66] DOI: 10.1038/nature10532
[67] Indjeian V . 2014 Gene regulatory changes in fish and human skeletal evolution. Centre for Ecology and Evolution (CEE) Autumn Symposium on the Evolution of Gene Regulation, 3 November 2014.
[68] DOI: 10.3390/biology1030557
[69] McLean CYF . 2011 Computational analysis of the mammalian cis-regulatory landscape. PhD thesis, Stanford University, USA.
[70] DOI: 10.1038/nature09774
[71] DOI: 10.1162/106454600568285
[72] DOI: 10.1007/BF02478302
[73] DOI: 10.1007/BF02477890
[74] DOI: 10.1007/BF02476354
[75] Landauer C Bellman KL . 2002 Theoretical biology: organisms and mechanisms. In Proc. 5th Int. Conf. on Computing Anticipatory Systems: CASYS 2001, vol. 627 (ed. DM Dubois). AIP Conference Proceedings, pp. 59–70. Melville, NY: American Institute of Physics.
[76] DOI: 10.1007/BF02481188
[77] Sirmai J . 2013 Autopoiesis facilitates self-reproduction. Adv. Artif. Life 12, 417–424.
[78] DOI: 10.1093/bioinformatics/btn228 · Zbl 05511724
[79] Dittrich P . 2009 Artificial chemistry. In Encyclopedia of complexity and system science (ed. B Meyers), pp. 113–136. Berlin, Germany: Springer.
[80] DOI: 10.1007/s11538-006-9130-8 · Zbl 1298.92127
[81] Dittrich P . 2005 Chemical computing. In Unconventional programming paradigms: International Workshop UPP 2004 (eds J-P Banâtre, J-L Giavitto, P Fradet, O Michel), pp. 19–32. Lecture Notes in Computer Science 3566. Berlin, Germany: Springer.
[82] DOI: 10.1162/106454601753238636
[83] Matsumaru N Centler F Speroni di Fenizio P Dittrich P . 2007 Chemical organization theory as a theoretical base for chemical computing. Int. J. Unconventional Comput. 3, 285–309.
[84] Calude CS Paun G . 2001 Computing with cells and atoms: an introduction to quantum, DNA and membrane computing. London, UK: Taylor & Francis.
[85] Paun G . 2003 Membrane computing. In Fundamentals of computation theory (eds A Lingas, BJ Nilsson), pp. 284–295. Lecture Notes in Computer Science, vol. 2751. Berlin, Germany: Springer.
[86] Paun G Rozenberg G Salomaa A . 2009 The Oxford handbook of membrane computing. Oxford, UK: Oxford University Press.
[87] Milner R . 1999 Communicating and mobile systems: the {\(\pi\)}-calculus. Cambridge, UK: Cambridge University Press. · Zbl 0942.68002
[88] Phillips A Cardelli L . 2007 Efficient, correct simulation of biological processes in the stochastic pi-calculus. In Computational methods in systems biology (eds M Calder, S Gilmore) pp. 184–199. Berlin, Germany: Springer. · Zbl 05282354
[89] Phillips A Cardelli L Castagna G . 2006 A graphical representation for biological processes in the stochastic pi-calculus. In Transactions on computational systems biology VII (ed. C Priami), pp. 123–152. Berlin, Germany: Springer. · Zbl 05282621
[90] DOI: 10.1016/j.tcs.2004.03.061 · Zbl 1069.68569
[91] DOI: 10.1039/b910101m
[92] DOI: 10.1016/j.biosystems.2009.04.008
[93] DOI: 10.1162/106454600568311
[94] DOI: 10.1016/0001-8708(75)90115-2 · Zbl 0314.12101
[95] DOI: 10.1016/0010-0277(95)00674-3
[96] Nehaniv CL . 1993 The algebra of time. In Proc. National Conf. of the Japan Society for Industrial and Applied Mathematics, pp. 127–128. Tokyo, Japan: Japan Society for Industrial and Applied Mathematics.
[97] Aczel P . 1988 Non-well-founded sets. CSLI Lecture Notes 14. Chicago, IL: University of Chicago Press.
[98] DOI: 10.1007/BF01843493 · Zbl 0248.18015
[99] DOI: 10.1016/S0304-3975(00)00056-6 · Zbl 0951.68038
[100] Nicolis G Prigogine I . 1977 Self-organization in non-equilibrium systems. New York, NY: John Wiley. · Zbl 0363.93005
[101] DOI: 10.1073/pnas.88.16.7328
[102] Akam M . 2014 The evolution of the segmentation gene network in arthropods. Centre for Ecology and Evolution (CEE) Autumn Symposium on the Evolution of Gene Regulation, 3 November 2014. (Modelling work of Erik Clark.)
[103] DOI: 10.1093/bioinformatics/btn266
[104] von Neumann J . 1956 Probabilistic logics and the synthesis of reliable organisms from unreliable components. In Automata studies (eds CE Shannon, J McCarthy), pp. 43–98. Annals of Mathematical Studies, vol 34. Princeton, NJ: Princeton University Press.
[105] von Neumann J 1966 Theory of self-reproducing automata. Champaign, IL: University of Illinois Press. Edited and completed by Arthur W. Burks.
[106] DOI: 10.1016/0303-2647(74)90031-8
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.