Chemical organisation theory is a framework developed to simplify the analysis of long-term behaviour of chemical systems. In this work, we build on these ideas to develop novel techniques for formal quantitative analysis of chemical reaction networks, using discrete stochastic models represented as continuous-time Markov chains. We propose methods to identify organisations, and to study quantitative properties regarding movements between these organisations. We then construct and formalise a coarse-grained Markov chain model of hierarchic organisations for a given reaction network, which can be used to approximate the behaviour of the original reaction network. As an application of the coarse-grained model, we predict the behaviour of the reaction network systems over time via the master equation. Experiments show that our predictions can mimic the main pattern of the concrete behaviour in the long run, but the precision varies for different models and reaction rule rates. Finally, we propose an algorithm to selectively refine the coarse-grained models and show experiments demonstrating that the precision of the prediction has been improved.

Unconventional computing devices operating on nonlinear chemical media offer an interesting alternative to standard, semiconductor-based computers. In this work we study in-silico a chemical medium composed of communicating droplets that functions as a database classifier. The droplet network can be "programmed" by an externally provided illumination pattern. The complex relationship between the illumination pattern and the droplet behavior makes manual programming hard. We introduce an evolutionary algorithm that automatically finds the optimal illumination pattern for a given classification problem. Notably, our approach does not require us to prespecify the signals that represent the output classes of the classification problem, which is achieved by using a fitness function that measures the mutual information between chemical oscillation patterns and desired output classes. We illustrate the feasibility of our approach in computer simulations by evolving droplet classifiers for three machine learning datasets. We demonstrate that the same medium composed of 25 droplets located on a square lattice can be successfully used for different classification tasks by applying different illumination patterns as its externally supplied program.

We are pleased to present this special issue of Artificial Life, which is dedicated to articles arising from a workshop held on September 6, 2012, as part of the Unconventional Computation and Natural Computation (UCNC) conference in Orléans, France. UCNC is now a well-established meeting in the portfolio of conferences dedicated to nonstandard computation, dating back to 1998. The 2012 conference was hosted by the Fundamental Computer Science Laboratory of the University of Orléans, and the Second Workshop on Biological and Chemical Information Technologies (BioChemIT) was organized by the COBRA project.COBRA was a three-year initiative (2010–2013), supported by the European Commission to encourage and nurture research and training in the field of biological and chemical information technology. Fundamentally, the field seeks to harness the capabilities of natural and chemical systems. Rather than simply deriving inspiration from living systems, biological and chemical IT researchers seek to directly use or construct these systems for the purposes of engineering and computation. Over the past few years, technological advances in chemistry, molecular biology, functional materials, and engineering have brought biological and chemical information processing within our control. The ability to build, design, and grow ICT systems that can exploit these processes will lead to revolutionary advances in the future [1].The five articles in this issue represent a broad swathe of work, mainly covering alternative computational substrates (such as droplet architectures, chemical media, and microbes) and novel theory (complexity measurement).The first two articles concern chemistry-based computing. The one by Jones et al. considers how an architecture composed of interacting autonomous droplets might (in future) be applied to applications in robotics. They give their design for a single droplet (capable of rudimentary sensing of its environment, processing, and actuation), which is based on the well-known Braitenberg vehicle, before presenting preliminary experimental results on the processing and actuation phases, using multiple droplets.Although the first two articles both use the Belousov-Zhabotinsky (BZ) reaction [4] as a basic underlying mechanism, the second one (by King et al.) takes a slightly different approach from the first, in that it considers the geometry of the vessel containing the reaction, and how this might be designed in order to obtain large networks of chemical oscillators. Coupled oscillators are fundamental to the study of complex systems, and their properties have been harnessed for the purposes of nonstandard computation in a variety of domains and substrates (e.g., [2]). This article presents detailed experimental investigations into the effect of channel geometry on BZ excitability, thus laying the ground for threshold-based chemical computing implemented by the combination of reactions and specific 3D reaction vessel structure.The third article, by Ozasa et al., concerns the use of single-celled organisms; specifically, microbes from the genus Euglena, which are capable of self-directed movement. Previously, single colonies have been used to implement simply neurocomputing algorithms [3], but a useful extension, demonstrated here, would be to connect multiple colonies, for the purposes of distributed processing. Euglena cells are naturally averse to blue light, and this property is used to externally direct the swimming behavior of colonies of cells. In this way, the isolated colonies may be optically coupled, which allows studies of both cooperative and competitive control of behavior and colony distribution.The fourth article, by Beneš et al., also concerns microbial computing, but in the context of synthetic biology. The engineering of genetic circuits within bacteria (and other simple organisms) is now well established, but there are inherent difficulties with the approach, due to the unpredictable nature of the biological substrate. The notion of evolving circuits in situ is therefore appealing, and here the authors present a scheme for using plasmids (short circular strands of DNA) to drive a population towards good solutions. Importantly, they present a dual selection mechanism, and simulation results suggest that this adds robustness to the process.The final article in this issue, by Lui et al., considers issues of complexity, and introduces a new definition based on Kolmogorov complexity and Shannon entropy. The article shows some applications of this new measure, one using the familiar cellular automata classification scheme of Wolfram, and the other using the self-organization of porphyrin molecules. The utility of the method is illustrated by convincing demonstrations that the results of measuring existing well-understood structures (using the new metric) are consistent with previous theory.We thank the European Commission for supporting COBRA (grant number 270371), the UCNC organizers for hosting our workshop, the Editor-in-Chief, Mark Bedau, for the opportunity to publish the special issue, and the anonymous reviewers for their timely, clear, and helpful assessments.

In this paper, we present general methods that can be used to explore the information processing potential of a medium composed of oscillating (self-exciting) droplets. Networks of Belousov-Zhabotinsky (BZ) droplets seem especially interesting as chemical reaction-diffusion computers because their time evolution is qualitatively similar to neural network activity. Moreover, such networks can be self-generated in microfluidic reactors. However, it is hard to track and to understand the function performed by a medium composed of droplets due to its complex dynamics. Corresponding to recurrent neural networks, the flow of excitations in a network of droplets is not limited to a single direction and spreads throughout the whole medium. In this work, we analyze the operation performed by droplet systems by monitoring the information flow. This is achieved by measuring mutual information and time delayed mutual information of the discretized time evolution of individual droplets. To link the model with reality, we use experimental results to estimate the parameters of droplet interactions. We exemplarily investigate an evolutionary generated droplet structure that operates as a NOR gate. The presented methods can be applied to networks composed of at least hundreds of droplets.

We outline a blueprint for the development of new computer science approaches for the management and analysis of big data problems for biodiversity science. Such problems are characterized by a combination of different data sources each of which owns at least one of the typical characteristics of big data (volume, variety, velocity, or veracity). For these problems, we envision a solution that covers different aspects of integrating data sources and algorithms for their analysis on one of the following three layers: At the data layer, there are various data archives of heterogeneous, unstructured, and uncertain data. At the functional layer, the data are analyzed for each archive individually. At the meta-layer, multiple functional archives are combined for complex analysis.

MOTIVATION: The functioning of many biological processes depends on the appearance of only a small number of a single molecular species. Additionally, the observation of molecular crowding leads to the insight that even a high number of copies of species do not guarantee their interaction. How single particles contribute to stabilizing biological systems is not well understood yet. Hence, we aim at determining the influence of single molecules on the long-term behaviour of biological systems, i.e. whether they can reach a steady state. RESULTS: We provide theoretical considerations and a tool to analyse Systems Biology Markup Language models for the possibility to stabilize because of the described effects. The theory is an extension of chemical organization theory, which we called discrete chemical organization theory. Furthermore we scanned the BioModels Database for the occurrence of discrete chemical organizations. To exemplify our method, we describe an application to the Template model of the mitotic spindle assembly checkpoint mechanism. AVAILABILITY AND IMPLEMENTATION: http://www.biosys.uni-jena.de/Services.html. SUPPLEMENTARY INFORMATION: Supplementary data are available at Bioinformatics online.

SUMMARY: Analysing genome-scale in silico models with stoichiometry-based methods is computationally demanding. The current algorithms to compute chemical organizations in chemical reaction networks are limited to small-scale networks, prohibiting a thorough analysis of large models. Here, we introduce a parallelized version of the constructive algorithm to determine chemical organizations. The algorithm is implemented in the Standard C programming language and parallelized using the message passing interface (MPI) protocol. The resulting code can be executed on computer clusters making use of an arbitrary number of processors. The algorithm is parallelized in an embarrassing parallel manner, providing good scalability. AVAILABILITY: An implementation of the algorithm including source code can be obtained from http://www.minet.uni-jena.de/csb/prj/ot/tools

BACKGROUND: We suggest a new type of modeling approach for the coarse grained, particle-based spatial simulation of combinatorially complex chemical reaction systems. In our approach molecules possess a location in the reactor as well as an orientation and geometry, while the reactions are carried out according to a list of implicitly specified reaction rules. Because the reaction rules can contain patterns for molecules, a combinatorially complex or even infinitely sized reaction network can be defined. For our implementation (based on LAMMPS), we have chosen an already existing formalism (BioNetGen) for the implicit specification of the reaction network. This compatibility allows to import existing models easily, i.e., only additional geometry data files have to be provided. RESULTS: Our simulations show that the obtained dynamics can be fundamentally different from those simulations that use classical reaction-diffusion approaches like Partial Differential Equations or Gillespie-type spatial stochastic simulation. We show, for example, that the combination of combinatorial complexity and geometric effects leads to the emergence of complex self-assemblies and transportation phenomena happening faster than diffusion (using a model of molecular walkers on microtubules). When the mentioned classical simulation approaches are applied, these aspects of modeled systems cannot be observed without very special treatment. Further more, we show that the geometric information can even change the organizational structure of the reaction system. That is, a set of chemical species that can in principle form a stationary state in a Differential Equation formalism, is potentially unstable when geometry is considered, and vice versa. CONCLUSIONS: We conclude that our approach provides a new general framework filling a gap in between approaches with no or rigid spatial representation like Partial Differential Equations and specialized coarse-grained spatial simulation systems like those for DNA or virus capsid self-assembly.

Large chemical reaction networks often exhibit distinctive features that can be interpreted as higher-level structures. Prime examples are metabolic pathways in a biochemical context. We review mathematical approaches that exploit the stoichiometric structure, which can be seen as a particular directed hypergraph, to derive an algebraic picture of chemical organizations. We then give an alternative interpretation in terms of set-valued set functions that encapsulate the production rules of the individual reactions. From the mathematical point of view, these functions define generalized topological spaces on the set of chemical species. We show that organization-theoretic concepts also appear in a natural way in the topological language. This abstract representation in turn suggests the exploration of the chemical meaning of well-established topological concepts. As an example, we consider connectedness in some detail.

January 01 2009 Artificial Chemistry In Special Collection: CogNet Hideaki Suzuki, Hideaki Suzuki * Contact author.** National Institute of Information and Communications Technology (NICT), Kobe Advanced ICT Research Center (KARC), 588-2, Iwaoka, Iwaokaka-cho, Nishi-ku, Kobe, 651-2492 Japan. E-mail: [email protected] Search for other works by this author on: This Site Google Scholar Peter Dittrich Peter Dittrich † Friedrich Schiller University Jena, Institute of Computer Science, and Jena Centre for Bioinformatics, D-07743 Jena, Germany. E-mail: [email protected] Search for other works by this author on: This Site Google Scholar Author and Article Information Hideaki Suzuki * Contact author.** National Institute of Information and Communications Technology (NICT), Kobe Advanced ICT Research Center (KARC), 588-2, Iwaoka, Iwaokaka-cho, Nishi-ku, Kobe, 651-2492 Japan. E-mail: [email protected] Peter Dittrich † Friedrich Schiller University Jena, Institute of Computer Science, and Jena Centre for Bioinformatics, D-07743 Jena, Germany. E-mail: [email protected] Online ISSN: 1530-9185 Print ISSN: 1064-5462 © 2008 Massachusetts Institute of Technology2008 Artificial Life (2009) 15 (1): 1–3. https://doi.org/10.1162/artl.2009.15.1.15100 Cite Icon Cite Permissions Share Icon Share Facebook Twitter LinkedIn MailTo Views Icon Views Article contents Figures & tables Video Audio Supplementary Data Peer Review Search Site Citation Hideaki Suzuki, Peter Dittrich; Artificial Chemistry. Artif Life 2009; 15 (1): 1–3. doi: https://doi.org/10.1162/artl.2009.15.1.15100 Download citation file: Ris (Zotero) Reference Manager EasyBib Bookends Mendeley Papers EndNote RefWorks BibTex toolbar search Search Dropdown Menu toolbar search search input Search input auto suggest filter your search All ContentAll JournalsArtificial Life Search Advanced Search This content is only available as a PDF. © 2008 Massachusetts Institute of Technology2008 Article PDF first page preview Close Modal You do not currently have access to this content.

MOTIVATION: The increasing number and complexity of biomodels makes automatic procedures for checking the models' properties and quality necessary. Approaches like elementary mode analysis, flux balance analysis, deficiency analysis and chemical organization theory (OT) require only the stoichiometric structure of the reaction network for derivation of valuable information. In formalisms like Systems Biology Markup Language (SBML), however, information about the stoichiometric coefficients required for an analysis of chemical organizations can be hidden in kinetic laws. RESULTS: First, we introduce an algorithm that uncovers stoichiometric information that might be hidden in the kinetic laws of a reaction network. This allows us to apply OT to SBML models using modifiers. Second, using the new algorithm, we performed a large-scale analysis of the 185 models contained in the manually curated BioModels Database. We found that for 41 models (22%) the set of organizations changes when modifiers are considered correctly. We discuss one of these models in detail (BIOMD149, a combined model of the ERK- and Wnt-signaling pathways), whose set of organizations drastically changes when modifiers are considered. Third, we found inconsistencies in 5 models (3%) and identified their characteristics. Compared with flux-based methods, OT is able to identify those species and reactions more accurately [in 26 cases (14%)] that can be present in a long-term simulation of the model. We conclude that our approach is a valuable tool that helps to improve the consistency of biomodels and their repositories. AVAILABILITY: All data and a JAVA applet to check SBML-models is available from http://www.minet.uni-jena.de/csb/prj/ot/tools. SUPPLEMENTARY INFORMATION: Supplementary data are available at Bioinformatics online.

DEF-like and GLO-like class B floral homeotic genes encode closely related MADS-domain transcription factors that act as developmental switches involved in specifying the identity of petals and stamens during flower development. Class B gene function requires transcriptional upregulation by an autoregulatory loop that depends on obligate heterodimerization of DEF-like and GLO-like proteins. Because switch-like behavior of gene expression can be displayed by single genes already, the functional relevance of this complex circuitry has remained enigmatic. On the basis of a stochastic in silico model of class B gene and protein interactions, we suggest that obligate heterodimerization of class B floral homeotic proteins is not simply the result of neutral drift but enhanced the robustness of cell-fate organ identity decisions in the presence of stochastic noise. This finding strongly corroborates the view that the appearance of this regulatory mechanism during angiosperm phylogeny led to a canalization of flower development and evolution.

MOTIVATION: Novel techniques are required to analyze computational models of intracellular processes as they increase steadily in size and complexity. The theory of chemical organizations has recently been introduced as such a technique that links the topology of biochemical reaction network models to their dynamical repertoire. The network is decomposed into algebraically closed and self-maintaining subnetworks called organizations. They form a hierarchy representing all feasible system states including all steady states. RESULTS: We present three algorithms to compute the hierarchy of organizations for network models provided in SBML format. Two of them compute the complete organization hierarchy, while the third one uses heuristics to obtain a subset of all organizations for large models. While the constructive approach computes the hierarchy starting from the smallest organization in a bottom-up fashion, the flux-based approach employs self-maintaining flux distributions to determine organizations. A runtime comparison on 16 different network models of natural systems showed that none of the two exhaustive algorithms is superior in all cases. Studying a 'genome-scale' network model with 762 species and 1193 reactions, we demonstrate how the organization hierarchy helps to uncover the model structure and allows to evaluate the model's quality, for example by detecting components and subsystems of the model whose maintenance is not explained by the model. AVAILABILITY: All data and a Java implementation that plugs into the Systems Biology Workbench is available from http://www.minet.uni-jena.de/csb/prj/ot/tools.

Chemical information processing posseses a variety of valuable properties, such as, robustness, concurrency, fault- tolerance, and evolvability. However, it is difficult to predict and program a chemical system, because the computation emerges as a global phenomenon from microscopic reactions. Here, we will present design principles for chemical programs. We focus on programs that should compute a qualitative and not quantitative result. The design principles are based on chemical organization theory, which defines a chemical organization as a closed and self- maintaining set of molecular species. The fundamental assumption of so called organization-oriented programming is that computation should be understood as a movement between chemical organizations. In this case we expect that the resulting system is more robust, and fine-tuning of the kinetic laws will be less important.

Handling highly dynamic scenarios as they arise in emergency situations requires lots of semantic information about the situation and an extremely flexible, selforganizing IT infrastructure that provides services that can be used to manage the situation. We show that a distributed meta level architecture is particularly suited for the implementation of such a self-organizing grid of services. This architecture (SOGOS) distinguishes between an object level and a meta level. The middleware processes of the grid are running on the object level. The meta level defines an explicitly and declaratively represented dynamic meta model that provides the semantics for the object level processes. Additionally, this level runs processes that plan, supervise and control mobile agents on the object level. The levels are linked together by reflection processes that ensure that relevant changes on the object level are reflected in the meta model and vice versa. The corresponding reflection principles provide the basis for the implementation of the selforganizing mechanisms that govern the overall system.

A large training set of fitness cases can critically slow down genetic programming, if no appropriate subset selection method is applied. Such a method allows an individual to be evaluated on a smaller subset of fitness cases. In this paper we suggest a new subset selection method that takes the problem structure into account, while being problem independent at the same time. In order to achieve this, information about the problem structure is acquired during evolutionary search by creating a topology (relationship) on the set of fitness cases. The topology is induced by individuals of the evolving population. This is done by increasing the strength of the relation between two fitness cases, if an individual of the population is able to solve both of them. Our new topology-based subset selection method chooses a subset, such that fitness cases in this subset are as distantly related as is possible with respect to the induced topology. We compare topology-based selection of fitness cases with dynamic subset selection and stochastic subset sampling on four different problems. On average, runs with topology-based selection show faster progress than the others.

This article reviews the growing body of scientific work in artificial chemistry. First, common motivations and fundamental concepts are introduced. Second, current research activities are discussed along three application dimensions: modeling, information processing, and optimization. Finally, common phenomena among the different systems are summarized. It is argued here that artificial chemistries are "the right stuff" for the study of prebiotic and biochemical evolution, and they provide a productive framework for questions regarding the origin and evolution of organizations in general. Furthermore, artificial chemistries have a broad application range of practical problems, as shown in this review.

We analyze different levels of meta-evolution using a graph based GP system. The system allows one to represent individuals of the search space and genetic variation operators in a coherent way as graph programs differing only in the operator set. Seven variants of meta-evolution are tested on three real world classification problems. The most complex variant consists of three meta-levels where graph programs on meta-level 1 recombine individuals of the search space (base level), graph programs on meta-level 2 recombine programs on meta-level 1, and programs on meta-level 3 recombine programs on meta-level 2 and themselves. The empirical results shows that the use of meta levels is advantageous.

We examine the qualitative dynamics of a catalytic self-organizing system of binary strings that is inspired by the chemical information processing metaphor. A string is interpreted in two different ways: either (a) as raw data or (b) as a machine that is able to process another string as data in order to produce a third one. This article focuses on the phenomena of evolution whose appearance is notable because no explicit mutation, recombination, or artificial selection operators are introduced. We call the system self-evolving because every variation is performed by the objects themselves in their machine form.