Combinatorial Properties of Some Cellular Automata Related to the Mosaic Cycle Concept

A cellular automaton that is related to the "mosaic cycle concept" is considered. We explain why such automata sustain very often, but not always, n-periodic trajectories (n being the number of states of the automaton). Our work is a first step in the direction of a theory of these type of automata which might be useful in modeling mosaic successions.     

A cellular automaton model of morphogenesis in Arabidopsis thaliana

Development of organisms is a very complex process in that a lot of gene networks of different cell types are to be integrated. Development of cellular automata that model the morphodynamics of different cell types is the first step in understanding and analyzing the regulatory mechanisms that underlie the developmental gene networks. We have developed a model of a cellular automaton that simulates the embryonic development of the shoot meristem in Arabidopsis thaliana. The model adequately describes the basic stages in the development of this organ in wild type and mutants.

     

A cellular automaton model of morphogenesis in <Emphasis Type="Italic">Arabidopsis thaliana</Emphasis>

Development of organisms is a very complex process in that a lot of gene networks of different cell types are to be integrated. Development of cellular automata that model the morphodynamics of different cell types is the first step in understanding and analyzing the regulatory mechanisms that underlie the developmental gene networks. We have developed a model of a cellular automaton that simulates the embryonic development of the shoot meristem in Arabidopsis thaliana. The model adequately describes the basic stages in the development of this organ in wild type and mutants.     

Evolved cellular automata for protein secondary structure prediction imitate the determinants for folding observed in nature

We demonstrate the first application of cellular automata to the secondary structure predictions of proteins. Cellular automata use localized interactions to simulate global phenomena, which resembles the protein folding problem where individual residues interact locally to define the global protein conformation. The protein's amino acid sequence was input into the cellular automaton and rules for updating states were evolved using a genetic algorithm. An optimized accuracy (Q3) for the RS126 and CB513 dataset of 58.21% and 56.51%, respectively, could be obtained. Thus, the current work demonstrates the applicability of a rather simple algorithm on a problem as complex as protein secondary structure prediction.     

Cellular Automata Modeling of Stem‐Cell‐Driven Development of Tissue in the Nervous System

Mathematical and computational modeling enables biologists to integrate data from observations and experiments into a theoretical framework. In this review, we describe how developmental processes associated with stem‐cell‐driven growth of tissue in both the embryonic and adult nervous system can be modeled using cellular automata (CA). A cellular automaton is defined by its discrete nature in time, space, and state. The discrete space is represented by a uniform grid or lattice containing agents that interact with other agents within their local neighborhood. This possibility of local interactions of agents makes the cellular automata approach particularly well suited for studying through modeling how complex patterns at the tissue level emerge from fundamental developmental processes (such as proliferation, migration, differentiation, and death) at the single‐cell level. As part of this review, we provide a primer for how to define biologically inspired rules governing these processes so that they can be implemented into a CA model. We then demonstrate the power of the CA approach by presenting simulations (in the form of figures and movies) based on building models of three developmental systems: the formation of the enteric nervous system through invasion by neural crest cells; the growth of normal and tumorous neurospheres induced by proliferation of adult neural stem/progenitor cells; and the neural fate specification through lateral inhibition of embryonic stem cells in the neurogenic region of Drosophila.     

Pre-clinical drug prioritization via prognosis-guided genetic interaction networks

The high rates of failure in oncology drug clinical trials highlight the problems of using pre-clinical data to predict the clinical effects of drugs. Patient population heterogeneity and unpredictable physiology complicate pre-clinical cancer modeling efforts. We hypothesize that gene networks associated with cancer outcome in heterogeneous patient populations could serve as a reference for identifying drug effects. Here we propose a novel in vivo genetic interaction which we call 'synergistic outcome determination' (SOD), a concept similar to 'Synthetic Lethality'. SOD is defined as the synergy of a gene pair with respect to cancer patients' outcome, whose correlation with outcome is due to cooperative, rather than independent, contributions of genes. The method combines microarray gene expression data with cancer prognostic information to identify synergistic gene-gene interactions that are then used to construct interaction networks based on gene modules (a group of genes which share similar function). In this way, we identified a cluster of important epigenetically regulated gene modules. By projecting drug sensitivity-associated genes on to the cancer-specific inter-module network, we defined a perturbation index for each drug based upon its characteristic perturbation pattern on the inter-module network. Finally, by calculating this index for compounds in the NCI Standard Agent Database, we significantly discriminated successful drugs from a broad set of test compounds, and further revealed the mechanisms of drug combinations. Thus, prognosis-guided synergistic gene-gene interaction networks could serve as an efficient in silico tool for pre-clinical drug prioritization and rational design of combinatorial therapies.     

A 3-D model of tumor progression based on complex automata driven by particle dynamics

The dynamics of a growing tumor involving mechanical remodeling of healthy tissue and vasculature is neglected in most of the existing tumor models. This is due to the lack of efficient computational framework allowing for simulation of mechanical interactions. Meanwhile, just these interactions trigger critical changes in tumor growth dynamics and are responsible for its volumetric and directional progression. We describe here a novel 3-D model of tumor growth, which combines particle dynamics with cellular automata concept. The particles represent both tissue cells and fragments of the vascular network. They interact with their closest neighbors via semi-harmonic central forces simulating mechanical resistance of the cell walls. The particle dynamics is governed by both the Newtonian laws of motion and the cellular automata rules. These rules can represent cell life-cycle and other biological interactions involving smaller spatio-temporal scales. We show that our complex automata, particle based model can reproduce realistic 3-D dynamics of the entire system consisting of the tumor, normal tissue cells, blood vessels and blood flow. It can explain phenomena such as the inward cell motion in avascular tumor, stabilization of tumor growth by the external pressure, tumor vascularization due to the process of angiogenesis, trapping of healthy cells by invading tumor, and influence of external (boundary) conditions on the direction of tumor progression. We conclude that the particle model can serve as a general framework for designing advanced multiscale models of tumor dynamics and it is very competitive to the modeling approaches presented before.     

Autonomy: an information theoretic perspective

We present a tentative proposal for a quantitative measure of autonomy. This is something that, surprisingly, is rarely found in the literature, even though autonomy is considered to be a basic concept in many disciplines, including artificial life. We work in an information theoretic setting for which the distinction between system and environment is the starting point. As a first measure for autonomy, we propose the conditional mutual information between consecutive states of the system conditioned on the history of the environment. This works well when the system cannot influence the environment at all and the environment does not interact synergetically with the system. When, in contrast, the system has full control over its environment, we should instead neglect the environment history and simply take the mutual information between consecutive system states as a measure of autonomy. In the case of mutual interaction between system and environment there remains an ambiguity regarding whether system or environment has caused observed correlations. If the interaction structure of the system is known, we define a "causal" autonomy measure which allows this ambiguity to be resolved. Synergetic interactions still pose a problem since in this case causation cannot be attributed to the system or the environment alone. Moreover, our analysis reveals some subtle facets of the concept of autonomy, in particular with respect to the seemingly innocent system-environment distinction we took for granted, and raises the issue of the attribution of control, i.e. the responsibility for observed effects. To further explore these issues, we evaluate our autonomy measure for simple automata, an agent moving in space, gliders in the game of life, and the tessellation automaton for autopoiesis of Varela et al. [Varela, F.J., Maturana, H.R., Uribe, R., 1974. Autopoiesis: the organization of living systems, its characterization and a model. BioSystems 5, 187-196].     

A computational model of a class of gene networks with positive and negative controls

This article proposes a computational framework for modelling the logical behavior of a class of gene networks. We characterize the basic behavior of genes in terms of a state-and-transition structure, and model the individual genes as language-generating automata. We consider positive and negative controls as the interaction mechanisms among the genes, and treat such controls as constraints (also expressed in automata) imposed on the behavior of the gene network. By computing the intersection of the languages generated by the gene models and the constraints, we obtain the complete set of pathways in a gene network. Implications and possible improvement of this work are discussed.     

Differential dependence on DNA ligase of type II restriction enzymes: a practical way toward ligase-free DNA automaton

DNA computing study is a new paradigm in computer science and biological computing fields. As one of DNA computing approaches, DNA automaton is composed of the hardware, input DNA molecule and state transition molecules. By now restriction enzymes are key hardware for DNA computing automaton. It has been found that DNA computing efficiency may be independent on DNA ligases when type IIS restriction enzymes like FokI are used as hardware. In this study, we compared FokI with four other distinct enzymes HgaI, BsmFI, BbsI, and BseMII, and found their differential independence on T4 DNA ligase when performing automaton reactions. Since DNA automaton is a potential powerful tool to tackle gene relationship in genomic network scale, the feasible ligase-free DNA automaton may set an initial base to develop functional DNA automata for various DNA technology development and implications in genetics study in the near future.     

Models from experiments: combinatorial drug perturbations of cancer cells

We present a novel method for deriving network models from molecular profiles of perturbed cellular systems. The network models aim to predict quantitative outcomes of combinatorial perturbations, such as drug pair treatments or multiple genetic alterations. Mathematically, we represent the system by a set of nodes, representing molecular concentrations or cellular processes, a perturbation vector and an interaction matrix. After perturbation, the system evolves in time according to differential equations with built‐in nonlinearity, similar to Hopfield networks, capable of representing epistasis and saturation effects. For a particular set of experiments, we derive the interaction matrix by minimizing a composite error function, aiming at accuracy of prediction and simplicity of network structure. To evaluate the predictive potential of the method, we performed 21 drug pair treatment experiments in a human breast cancer cell line (MCF7) with observation of phospho‐proteins and cell cycle markers. The best derived network model rediscovered known interactions and contained interesting predictions. Possible applications include the discovery of regulatory interactions, the design of targeted combination therapies and the engineering of molecular biological networks.     

CompuCell, a multi-model framework for simulation of morphogenesis

MOTIVATION: CompuCell is a multi-model software framework for simulation of the development of multicellular organisms known as morphogenesis. It models the interaction of the gene regulatory network with generic cellular mechanisms, such as cell adhesion, division, haptotaxis and chemotaxis. A combination of a state automaton with stochastic local rules and a set of differential equations, including subcellular ordinary differential equations and extracellular reaction-diffusion partial differential equations, model gene regulation. This automaton in turn controls the differentiation of the cells, and cell-cell and cell-extracellular matrix interactions that give rise to cell rearrangements and pattern formation, e.g. mesenchymal condensation. The cellular Potts model, a stochastic model that accurately reproduces cell movement and rearrangement, models cell dynamics. All these models couple in a controllable way, resulting in a powerful and flexible computational environment for morphogenesis, which allows for simultaneous incorporation of growth and spatial patterning. RESULTS: We use CompuCell to simulate the formation of the skeletal architecture in the avian limb bud. AVAILABILITY: Binaries and source code for Microsoft Windows, Linux and Solaris are available for download from http://sourceforge.net/projects/compucell/     

Global Quantitative Modeling of Chromatin Factor Interactions

Chromatin is the driver of gene regulation, yet understanding the molecular interactions underlying chromatin factor combinatorial patterns (or the “chromatin codes”) remains a fundamental challenge in chromatin biology. Here we developed a global modeling framework that leverages chromatin profiling data to produce a systems-level view of the macromolecular complex of chromatin. Our model ultilizes maximum entropy modeling with regularization-based structure learning to statistically dissect dependencies between chromatin factors and produce an accurate probability distribution of chromatin code. Our unsupervised quantitative model, trained on genome-wide chromatin profiles of 73 histone marks and chromatin proteins from modENCODE, enabled making various data-driven inferences about chromatin profiles and interactions. We provided a highly accurate predictor of chromatin factor pairwise interactions validated by known experimental evidence, and for the first time enabled higher-order interaction prediction. Our predictions can thus help guide future experimental studies. The model can also serve as an inference engine for predicting unknown chromatin profiles — we demonstrated that with this approach we can leverage data from well-characterized cell types to help understand less-studied cell type or conditions.     

Modeling landscape structure constraints on species dispersal with a cellular automaton: Are there convergences with empirical data?

Landscapes are typically complex systems which do not necessarily allow performing large scale field experiments. A lot of studies hence analyzed correlations between landscape structure and species distribution. However, empirical data integrate a non-reducible part of contingency, which implies a major issue: the generalization of results. In such complex contexts, modeling can be useful since it allows isolating factors and it can play the role of reference for comparisons. In this perspective, we modeled plant species dispersal within a hedgerow network with a simple cellular automaton. In parallel we studied empirically plant species distribution in hedgerows to see whether both, results from the model and results from empirical data were convergent. Results showed that the cellular automaton was characterized by non-linear responses, corresponding to different levels of landscape constraints. Furthermore, convergences were found between the theoretical model and empirical data, in terms of differential responses of plant species to landscape structure, according to dispersal type and habitat specialization. Finally examining past landscape structure, the theoretical model and empirical data converged, demonstrating that past landscape patterns are particularly relevant in terms of statistical explanation of plant species distribution. We conclude that cellular automata were relevant formalizations of dispersal processes at the landscape level.     

Combining food web and species distribution models for improved community projections

The ability to model biodiversity patterns is of prime importance in this era of severe environmental crisis. Species assemblage along environmental gradients is subject to the interplay of biotic interactions in complement to abiotic filtering and stochastic forces. Accounting for complex biotic interactions for a wide array of species remains so far challenging. Here, we propose using food web models that can infer the potential interaction links between species as a constraint in species distribution models. Using a plant–herbivore (butterfly) interaction dataset, we demonstrate that this combined approach is able to improve species distribution and community forecasts. The trophic interaction network between butterfly larvae and host plant was phylogenetically structured and driven by host plant nitrogen content allowing forecasting the food web model to unknown interactions links. This combined approach is very useful in rendering models of more generalist species that have multiple potential interaction links, where gap in the literature may occur. Our combined approach points toward a promising direction for modeling the spatial variation in entire species interaction networks.     

Optimal amnesic probabilistic automata or how to learn and classify proteins in linear time and space.

Statistical modeling of sequences is a central paradigm of machine learning that finds multiple uses in computational molecular biology and many other domains. The probabilistic automata typically built in these contexts are subtended by uniform, fixed-memory Markov models. In practice, such automata tend to be unnecessarily bulky and computationally imposing both during their synthesis and use. Recently, D. Ron, Y. Singer, and N. Tishby built much more compact, tree-shaped variants of probabilistic automata under the assumption of an underlying Markov process of variable memory length. These variants, called Probabilistic Suffix Trees (PSTs) were subsequently adapted by G. Bejerano and G. Yona and applied successfully to learning and prediction of protein families. The process of learning the automaton from a given training set S of sequences requires theta(Ln2) worst-case time, where n is the total length of the sequences in S and L is the length of a longest substring of S to be considered for a candidate state in the automaton. Once the automaton is built, predicting the likelihood of a query sequence of m characters may cost time theta(m2) in the worst case. The main contribution of this paper is to introduce automata equivalent to PSTs but having the following properties: Learning the automaton, for any L, takes O (n) time. Prediction of a string of m symbols by the automaton takes O (m) time. Along the way, the paper presents an evolving learning scheme and addresses notions of empirical probability and related efficient computation, which is a by-product possibly of more general interest.     

Four-dimensional visualisation and analysis of protein-protein interaction networks

Protein-protein interaction networks are typically built with interactions collated from many experiments. These networks are thus composite and show all interactions that are currently known to occur in a cell. However, these representations are static and ignore the constant changes in protein-protein interactions. Here we present software for the generation and analysis of dynamic, four-dimensional (4-D) protein interaction networks. In this, time-course-derived abundance data are mapped onto three-dimensional networks to generate network movies. These networks can be navigated, manipulated and queried in real time. Two types of dynamic networks can be generated: a 4-D network that maps expression data onto protein nodes and one that employs 'real-time rendering' by which protein nodes and their interactions appear and disappear in association with temporal changes in expression data. We illustrate the utility of this software by the analysis of singlish interface date hub interactions during the yeast cell cycle. In this, we show that proteins MLC1 and YPT52 show strict temporal control of when their interaction partners are expressed. Since these proteins have one and two interaction interfaces, respectively, it suggests that temporal control of gene expression may be used to limit competition at the interaction interfaces of some hub proteins. The software and movies of the 4-D networks are available at http://www.systemsbiology.org.au/downloads_geomi.html.     

Probabilistic automata as a model for epigenesis of cellular networks

Probabilistic automata are compared with deterministic ones in simulations of growing networks made of dividing interconnected cells. On examples of chains, wheels and tree-like structures made of large numbers of cells it is shown that the number of necessary states in the initial generating cell automaton is reduced drastically when the automaton is probabilistic rather than deterministic. Since the price being paid is a decrease in the accuracy of the generated network, conditions under which reasonable compromises can be achieved are studied. They depend on the degree of redundancy of the final network (defined from the complexity of a deterministic automaton capable of generating it with maximum accuracy), on the "entropy" of the generating probabilistic automaton, and on the effects of different inputs on its transition probabilities (as measured by its "'capacity" in the sense of Shannon's information theory). The results are used to discuss and make more precise the notion of biological specificity. It is suggested that the weak metaphor of a genetic program, classically used to account for the role of DNA in specific genetic determinations, is replaced by that of inputs to biochemical probabilistic automata.