In this article we investigate the computational complexity of predicting two dimensional freezing majority cellular automata with states { − 1 , + 1 } , where the local interactions are based on an L-shaped neighborhood structure. In these automata, once a cell reaches state + 1 , it remains fixed in that state forever, while cells in state − 1 update to the most represented state among their neighborhoods. We consider L-shaped neighborhoods, which mean that the vicinity of a given cell c consists in a subset of cells in the north and east of c . We focus on the prediction problem, a decision problem that involves determining the state of a given cell after a given number of time-steps. We prove that when restricted to the simplest L-shaped neighborhood, consisting of the central cell and its nearest north and east neighbors, the prediction problem belongs to NC , meaning it can be solved efficiently in parallel. We generalize this result for any L-shaped neighborhood of size two. On the other hand, for other L-shaped neighborhoods, the problem becomes P -Complete, indicating that the problem might be inherently sequential.

In this work, we provide a procedure that allows us to transform certain kinds of deterministic Boolean networks on minterm or maxterm functions into symmetric ones, so inferring that such symmetrizable networks can present only periodic points of periods 1 or 2. In particular, we deal with generalized parallel (or synchronous) dynamical systems (GPDS) over undirected graphs, i.e., discrete parallel dynamical systems over undirected graphs where some of the self-loops may not appear. We also study the class of anti-symmetric GPDS (which are non-symmetrizable), proving that their periodic orbits have period 4. In addition, we introduce a class of non-symmetrizable systems which admit periodic orbits with arbitrary large periods.

Inspired by the resent trend of binary neural net-works, where weights and activation thresholds are represented using 1 and −1 such that they can be stored in 1-bit instead of full precision, we explore this approach for gene regulatory network modeling. An evolutionary computation approach to learn binary threshold networks is presented. In particular, we consider differential evolution and particle swarm optimization. We test our method by inferring binary threshold networks of a regulatory network of Quorum sensing systems in bacterium Paraburkholderia phytofirmans PsJN. We present results for weights having only 1 and −1 values, and consider different activation thresholds. Full binary threshold networks were found with minimum error (2 bits), whereas when the binary restriction is relaxed for the activation thresholds, networks with 0 bit error were found.

Consensus has become an active research topic in the field of social science, blockchain, and decision-making, to name a few. The study of how a group of people, entities, or agents generally reach an agreement is of interest. This paper studies how a consensus is reached using the threshold Boolean network model, where nodes represent agents taking on two possible values: 1 or 0. A threshold Boolean network is a directed graph with weights. It has typically been used as a model of gene regulatory networks. Each node has a Heaviside function depending linearly on its inputs and an updating scheme (in what order the nodes update their values). By using threshold Boolean networks, there are two possibilities of reaching a consensus. When all the possible configurations in the network converge to the fixed point attractor, all the nodes have only 1s or only 0s. We adopt a reverse engineering approach to study the characteristics of the networks that can model consensus. We search for such networks using evolutionary computation containing only one of the two mentioned attractors (consensus property). The search consists of finding the weights of the edges and the threshold value of each node. We characterize the resulting networks by the total number of edges, the number of positive edges, the number of negative edges, the average indegree, and the steps needed to reach consensus.

One of the first popular applications of Boolean networks for gene regulatory networks corresponds to the Mendoza & Alvarez-Buylla network of flower development. In this paper, we consider this model and a reduced version to reconstruct synthetic threshold Boolean networks that have the same asymptotic behavior as these base models. For this, we employ an evolution strategy to search for neighboring solutions. We were able to find solutions with fewer edges as well as networks with more balanced distributions of basins of attractions. Overall, our results show the effectiveness of using evolutionary computation in this application to explore alternative solutions with desired properties.

The lac operen in E. coli is one of the earliest examples of an inducible system of genes being under both positive and negative control that is capable of showing bistability. In this paper, we present a methodology to infer synthetic threshold Boolean regulatory networks of a reduced model of the lac operon using evolutionary computation. The formulation consists in a vector representation of the solutions (networks) and a fitness function specially designed to correctly simulate the bistability through the models' fixed points. We compared the effectiveness and efficiency (runtime) of the proposed approach using three evolutionary computation techniques: differential evolution, genetic algorithms, and particle swarm optimization. The results showed that the three algorithms are capable of finding solutions, being differential evolution the most effective, whereas genetic algorithms was the least effective and efficient in terms of runtime. Particle swarm optimization obtained a good trade-off between effectiveness versus efficiency. One of the inferred solutions was analyzed showing some interesting biological insights, as well as correctly being able to model bistability without any spurious attractors. Overall, the proposed formulation was effective to infer bistable lac operon models under the threshold Boolean network paradigm.

Boolean networks are popular models to represent gene regulatory networks due to their simplicity and capacity to give an initial idea of the qualitative dynamics of a gene regulatory network represented by the temporal evolution of the protein states. In this paper, we analyze the neutral space of Boolean network models of salt stress response in Arabidopsis through the construction of neutral networks. To infer Boolean networks to build the neutral network, we use an evolution strategy that uses a wildtype network to generate initial candidate solutions. We compare the neutral space results when we consider two different wildtypes. Our results show the effectiveness and usefulness of the evolutionary computation approach for this problem, as well as findings related to how the neutral space is shaped depending of the initial wildtype employed as well as particular characteristics of the evolution strategy used in this work.

Salinity is one of the main problems in agriculture, negatively influencing the survival, biomass production, and yield of food crops. Exposure to high salinity is connected with ionic stress due to accumulation of sodium ions, osmotic stress, and reactive oxygen species production. To develop crop plants with enhanced tolerance of saline stress, a basic understanding of physiological, biochemical and gene regulatory networks (GRN) is essential. In this paper, an approach to study the saline stress response and tolerance of plants through the GRN involved in this process is proposed. In particular, we reconstruct the GRN of Ara-bidopsis thaliana saline stress response using genetic algorithms and a Boolean network model. The proposed computational intelligence approach was able to successfully infer 1000 threshold Boolean networks that contained the desired Boolean trajectory. The inferred networks were used to build a consensus network, which was useful to identify the regulations or interactions among the genes that were more plausible.

In (Veliz-Cuba and Stigler, 2011) the authors proposed a Boolean model for the lac operon in Escherichia coli that is capable of predicting the operon being ON, OFF and bistable when the update schedule is the parallel one. We complement this work by using theoretical and algorithmic tools that allow us to know which are the configurations that converge to a fixed point or limit cycle (set namely attractor basin) for each deterministic update schedule. We show that, when bistability appears, about 70% of the dynamics have only the steady states ON and OFF. This latest having an attractor basin of an average size about 8 times bigger than that of ON. In the other 30%, the proportion is balanced between ON/OFF basins but the basins of limit cycles sum up, in average, about 5 times more than that of ON and OFF respectively. The techniques presented in this work are general and can be used to analyze other Boolean models.

An evolution strategy is proposed to construct neutral graphs. The proposed method is applied to the construction of the neutral graph of Boolean regulatory networks that share the same state sequences of the cell cycle of the fission yeast. The regulatory networks in the neutral graph are analyzed, identifying characteristics of the networks which belong to the connected component of the fission yeast cell cycle network and the regulatory networks that are not in the connected component. Results show not only topological differences, but also differences in the state space between networks in the connected component and the rest of the networks in the neutral graph. It was found that regulatory networks in the fission yeast cell cycle network connected component can be mutated (change in their interaction matrices) no more than three times, if more mutations occur, then the networks leave the connected component. Comparisons with a standard genetic algorithm shows the effectiveness of the proposed evolution strategy.

Given the input-output data of the mammalian cell cycle network under a parallel updating scheme, an attempt to construct a threshold Boolean network with the same dynamics is presented. To accomplish this, mutual information is used to find the network structure, then a swarm intelligence optimization technique called the bees algorithm is used to find the weights and thresholds for the network. It is shown that out of the ten regulatory elements (nodes) of the network, only nine can be modeled as a single threshold function, thus, the resulting network is almost a threshold Boolean network with the exception of the CycA protein which remains with its logical rules instead. The robustness of the network is explored with respect to update perturbations, in particular, what happens to the limit cycle attractors when changing from parallel to a sequential updating scheme. Results shows that the network is not robust since different limit cycles of different lengths appear.

A swarm intelligence technique called the bees algorithm is formulated to build synthetic networks of the budding yeast cell-cycle. The resulting networks contain the original fixed points of the budding yeast cell-cycle network plus additional fixed points to reduce the basin size of the fixed point associated to the G1 phase of the cell-cycle, with the purpose of promoting cell proliferation for biotechnological applications. One thousand synthetic networks were found using the bees algorithm, 84.5% had basins size for the G1 fixed point less or equal to 10, whereas the original model has a basin size for that fixed point of 1764. One of the synthetic networks was analyzed by a biologist concluding that the resulting model was quite consistent from a biological point of view, supporting the proposed method as a tool for biologist to construct synthetic networks with desired characteristics.

This paper investigates the avalanche problem AP for the Kadanoff sandpile model (KSPM). We prove that (a slight restriction of) AP is in NC1 in dimension one, leaving the general case open. Moreover, we prove that AP is P-complete in dimension two.

A simulated annealing framework is presented for learning gene regulatory networks with predefined attractors, under the threshold Boolean network model updated sequentially. The proposed method is used to study the robustness of the networks, defined as the number of different updating sequences they can have without loosing the attractor. The results suggests a power law between the frequency of the networks and the number of the updating sequences, also, a decrease of the networks' robustness as the cycle length grows. In general, the proposed simulated annealing framework is effective for reverse engineering problems.

We study the relationships between the positive and negative circuits of the connection graph and the fixed points of discrete neural networks (DNNs). As main results, we give necessary conditions and sufficient conditions for the existence of fixed points in a DNN. Moreover, we exhibit an upper bound for the number of fixed points in terms of the structure and number of positive circuits in the connection graph. This allows the determination of the maximum capacity for storing vectors in DNNs as fixed points, depending on the architecture of the network.

In this paper we study the dynamical behavior of a class of neural networks where the local transition rules are max or min functions. We prove that sequential updates define dynamics which reach the equilibrium in O(n2) steps, where n is the size of the network. For synchronous updates the equilibrium is reached in O(n) steps. It is shown that the number of fixed points of the sequential update is at most n. Moreover, given a set of p < or = n vectors, we show how to build a network of size n such that all these vectors are fixed points.

We present dynamical results concerning neural networks with high order arguments. More precisely, we study the family of block-sequential iteration of neural networks with polynomial arguments. In this context, we prove that, under a symmetric hypothesis, the sequential iteration is the only one of this family to converge to fixed points. The other iteration modes present a highly complex dynamical behavior: non-bounded cycles and simulation of arbitrary non-symmetric linear neural network. We also study a high order memory iteration scheme which accepts an energy functional and bounded cycles in the size of the memory steps.

Previous article Full AccessErrata: Lyapunov Functionals for Automata Networks Defined by Cyclically Monotone FunctionsE. Goles and S. MartínezE. Goles and S. Martínezhttps://doi.org/10.1137/0406051PDFBibTexSections ToolsAdd to favoritesExport CitationTrack CitationsEmail SectionsAbout"Errata: Lyapunov Functionals for Automata Networks Defined by Cyclically Monotone Functions." SIAM Journal on Discrete Mathematics, 6(4), p. 677[1] S. Poljak and , D. Turzik, On an application of convexity to discrete systems, Discrete Appl. Math., 13 (1986), 27–32 10.1016/0166-218X(86)90066-1 87k:58133 0588.93048 CrossrefISIGoogle Scholar Previous article FiguresRelatedReferencesCited byDetails Volume 6, Issue 4| 1993SIAM Journal on Discrete Mathematics History Submitted:04 August 1993Accepted:06 August 1993Published online:08 August 2006 InformationCopyright © 1993 Society for Industrial and Applied MathematicsPDF Download Article & Publication DataArticle DOI:10.1137/0406051Article page range:pp. 677-677ISSN (print):0895-4801ISSN (online):1095-7146Publisher:Society for Industrial and Applied Mathematics

For automata networks with dynamics given by $x( t + 1 ) = f( Ax( t ) - b )$, where A is symmetric and f is cyclically monotone, it is proved that there exists a Lyapunov functional $( H( x( t ) ) )_{t\geqq 1} $ that increases with t along the orbit. This allows one to study the finite limit cycles (which are of length one or two), the transient behavior in the finite case, and also to write down explicit integral functionals. The existence of $( H( x( t ) ) )$ is important for a physical approach to the study of these automata networks. The condition that f be cyclically monotone in $\mathbb{R}$ is equivalent to f increasing and is usually used in applications to computer sciences.