title: Algebraic properties of automata associated to Petri nets and applications to computation in biological systems.
abstract: Biochemical and genetic regulatory networks are often modeled by Petri nets. We study the algebraic structure of the computations carried out by Petri nets from the viewpoint of algebraic automata theory. Petri nets comprise a formalized graphical modeling language, often used to describe computation occurring within biochemical and genetic regulatory networks, but the semantics may be interpreted in different ways in the realm of automata. Therefore, there are several different ways to turn a Petri net into a state-transition automaton. Here, we systematically investigate different conversion methods and describe cases where they may yield radically different algebraic structures. We focus on the existence of group components of the corresponding transformation semigroups, as these reflect symmetries of the computation occurring within the biological system under study. Results are illustrated by applications to the Petri net modelling of intermediary metabolism. Petri nets with inhibition are shown to be computationally rich, regardless of the particular interpretation method. Along these lines we provide a mathematical argument suggesting a reason for the apparent all-pervasiveness of inhibitory connections in living systems.
authors.affiliation: The Royal Society, Wolfson Foundation BioComputation Laboratory & Algorithms Research Group, Centre for Computer Science and Informatics Research, University of Hertfordshire, Hatfield, Hertfordshire, United Kingdom. A.Egri-Nagy@herts.ac.uk
authors.forename: Attila
authors.initials: A
authors.lastname: Egri-Nagy
authors.forename: Chrystopher L
authors.initials: CL
authors.lastname: Nehaniv
mesh_terms: D000465:Algorithms; D002952:Citric Acid Cycle; D019295:Computational Biology / Q000379:methods*; D003198:Computer Simulation; D053263:Gene Regulatory Networks; D053858:Metabolic Networks and Pathways; D008954:Models, Biological