Narrow Results

In standard Cellular Automata (CA) and Boolean Networks (BN), the new state of a cell depends on the neighborhood configuration only at the preceding time step. The effect of implementing memory in cells on CA, CA on networks and BN with different degrees of random rewiring is studied in this paper paying attention to the particular case of four inputs. As a rule, memory in cells induces a moderation in the rate of changing cells and in the damage spreading, albeit in the latter case memory turns out ineffective in the control of the damage as the wiring network moves away of the ordered structure that features proper CA.

We present a method which allows for a reduction of a size of a simulated system. The method can be applied to any system where one can define a finite set of possible states of the system and an elementary process which transforms one state of the system to another. The method is based on the system symmetry; we get classes of states, which can be used instead of states. A detailed procedure is presented for undirected/directed and/or unweighted/weighted graphs. Several applications of the method are shown for different types of systems. In particular, new results are presented for the random Boolean networks.

We study the effects of the reciprocal links on the dynamics of direct Boolean networks with scale-free topology (SFRBNs). By means of the method of the Derrida Plot, we have investigated the SFRBNs characterized by different values of average degree and different values of reciprocity in order to test the behavioral regimes of the system. The following step was to perform numerical simulation with the quenched Kauffman model to study the dynamical properties of critical SFRBNs with ${〈k〉}_c=2$. The distribution of the number of different attractors, the period of the cyclic attractors, the transient duration and the fraction of the frozen nodes, have been studied as a function of the reciprocity and network size. The results presented reveal that reciprocity seems to have no direct effect on the changing of the behavioral regime of SFRBNs with given value of $〈k〉$. On the contrary, we observed that reciprocal links have a profound effect on the dynamic of critical SFRBNs.

Random Boolean networks, originally introduced as simplified models for the genetic regulatory networks, are abstract models widely applied for the study of the dynamical behaviors of self-organizing complex systems. In these networks, connectivity and the bias of the Boolean functions are the most important factors that can determine the behavioral regime of the systems. On the other hand, it has been found that topology and some structural elements of the networks such as the reciprocity, self-loops and source nodes, can have relevant effects on the dynamical properties of critical Boolean networks. In this paper, we study the impact of source and sink nodes on the dynamics of homogeneous and heterogeneous Boolean networks. Our research shows that an increase of the source nodes causes an exponentially growing of the different behaviors that the system can exhibit regardless of the network topology, while the amount of order seems to undergo modifications depending on the topology of the system. Indeed, with the increase of the source nodes the orderliness of the heterogeneous networks also increases, whereas it diminishes in the homogeneous ones. On the other hand, although the sink nodes seem not to have effects on the dynamic of the homogeneous networks, for the heterogeneous ones we have found that an increase of the sinks gives rise to an increasing of the order, although the different potential behaviors of the system remains approximately the same.

In this work, the Boolean Networks of different geometric shape and lattice organization were studied. It was revealed that not only a spatial shape but also the type of lattice are very important for definition of the structure-dynamics relation. The regular structures do not give a critical regime in the investigated cases. Hierarchy together with the irregular structure reveals characteristic features of criticality.

In standard Boolean Networks (BN) the new state of a cell depends upon the neighborhood configuration only at the preceding time step. The effect of implementing memory of different types in cells of BN with different degrees of random rewiring is studied in this article.

Traditional Boolean networks consist of nodes within a single network, each updating synchronously, although asynchronous versions have also been presented. In this paper the dynamics of two, mutually coupled traditional networks are investigated. In particular, the effects of varying the degree and type of intra-network connectivity are explored. The effects from different inter-network evolution rates are then considered, i.e. asynchronousity at the network level is examined. Finally, state memory is included within the nodes of coupled networks and shown to alter the dynamics of the networks under certain circumstances.

The solution to a deceptively simple combinatorial problem on bit strings results in the emergence of a fractal related to the Sierpinski Gasket. The result is generalized to higher dimensions and applied to the study of global dynamics in Boolean network models of complex biological systems.

This paper explores the compressibility of complex systems by considering the simplification of Boolean networks. A method, which is similar to that reported by Bastolla and Parisi,^4,5 is considered that is based on the removal of frozen nodes, or stable variables, and network "leaves," i.e. those nodes with outdegree = 0. The method uses a random sampling approach to identify the minimum set of frozen nodes. This set contains the nodes that are frozen in all attractor schemes. Although the method can over-estimate the size of the minimum set of frozen nodes, it is found that the chances of finding this minimum set are considerably greater than finding the full attractor set using the same sampling rate. Given that the number of attractors not found for a particular Boolean network increases with the network size, for any given sampling rate, such a method provides an opportunity to either fully enumerate the attractor set for a particular network, or improve the accuracy of the random sampling approach. Indeed, the paper also shows that when it comes to the counting of attractors in an ensemble of Boolean networks, enhancing the random sample method with the simplification method presented results in a significant improvement in accuracy.

Industrial networks offer a prime example of the tension between system stability and change. Change is necessary as a response to environmental variation, whereas stability provides the underpinning for long-term investment and the exploitation of efficiencies. Whilst one of the key themes in industrial network research has been the dynamics of change, relatively little work, empirical or theoretical, has been devoted to the dynamics of stability. This paper presents a new approach to this problem by using Boolean networks, which were originally devised by Stuart Kauffman as an abstract model of genetic networks. The elements in the model are connected by rules of Boolean logic, and a novel aspect of this research is that the elements represent the industrial network exchanges rather than stock entities (the organizations). The model structure consists of interactions between the exchanges, and the results represent the pattern of exchange episodes. A total of 42 networks were modeled and the dynamics analyzed in detail, and five of these cases are presented in this paper. The models produced realistic behavior and provided some insights into the reasons for stability in industrial networks.

We study the minimum number of driver nodes control of which leads a Boolean network (BN) from an initial state to a target state in a specified number of time steps. We show that the problem is NP-hard and present an integer linear programming-based method that solves the problem exactly. We mathematically analyze the average size of the minimum set of driver nodes for random Boolean networks with bounded in-degree and with a small number of time steps. The results of computational experiments using randomly generated BNs show good agreements with theoretical analyses. A further examination in realistic BNs demonstrates the efficiency and generality of our theoretical analyses.

We present an exact algorithm, based on techniques from the field of Model Checking, for finding control policies for Boolean Networks (BN) with control nodes. Given a BN, a set of starting states, I, a set of goal states, F, and a target time, t, our algorithm automatically finds a sequence of control signals that deterministically drives the BN from I to F at, or before time t, or else guarantees that no such policy exists. Despite recent hardness-results for finding control policies for BNs, we show that, in practice, our algorithm runs in seconds to minutes on over 13,400 BNs of varying sizes and topologies, including a BN model of embryogenesis in Drosophila melanogaster with 15,360 Boolean variables. We then extend our method to automatically identify a set of Boolean transfer functions that reproduce the qualitative behavior of gene regulatory networks. Specifically, we automatically learn a BN model of D. melanogaster embryogenesis in 5.3 seconds, from a space containing 6.9 × 10¹⁰ possible models.

We present algorithms for finding control strategies in Boolean Networks (BN). Our approach uses symbolic techniques from the field of model checking. We show that despite recent hardness-results for finding control policies, a model checking-based approach is often capable of scaling to extremely large and complex models. We demonstrate the effectiveness of our approach by applying it to a BN model of embryogenesis in D. melanogaster with 15,360 Boolean variables.

Boolean networks are models of genetic regulatory networks. S. Kauffman based many of his claims about spontaneous self-organization in complex systems on simulations of randomly constructed Boolean networks. Some of these claims are precise mathematical statements. We analyze these statements using combinatorial methods and show that there is partial agreement with some of Kauffman's conclusions, but in other cases there is disagreement. Our key finding is an algebraic parameter that determines the likelihood of order behaviour in a random Boolean network. There is a threshold such that when the parameter is less than the threshold, ordered behavior is prevalent, and when it is greater than the threshold, chaotic behavior is highly likely. When the parameter equals the threshold, some forms of ordered behavior persist, but others do not.

Motivation: A grand challenge in the modeling of biological systems is the identification of key variables which can act as targets for intervention. Good intervention targets are the "key players" in a system and have significant influence over other variables; in other words, in the context of diseases such as cancer, targeting these variables with treatments and interventions will provide the greatest effects because of their direct and indirect control over other parts of the system. Boolean networks are among the simplest of models, yet they have been shown to adequately model many of the complex dynamics of biological systems. Often ignored in the Boolean network model, however, are the so called basins of attraction. As the attractor states alone have been shown to correspond to cellular phenotypes, it is logical to ask which variables are most responsible for triggering a path through a basin to a particular attractor.

Results: This work claims that logic minimization (i.e. classical circuit design) of the collections of states in Boolean network basins of attraction reveals key players in the network. Furthermore, we claim that the key players identified by this method are often excellent targets for intervention given a network modeling a biological system, and more importantly, that the key players identified are not apparent from the attractor states alone, from existing Boolean network measures, or from other network measurements. We demonstrate these claims with a well-studied yeast cell cycle network and with a WNT5A network for melanoma, computationally predicted from gene expression data.

Theories of the origin of life have gone through several stages, with accompanying experimental work. The start of the modern era in this field lies with Stanley Miller's stunning early work showing abiotic synthesis of several amino acids, followed by an era of prebiotic chemistry, including sugars, nucleotides and other abiotically synthesized biomolecules.

With the discovery of the structure of double stranded DNA and RNA, focus shifted, largely in the work of Leslie Orgel, to the search for conditions in which a single stranded RNA molecule might line up free nucleotides according to Watson Crick base paring, and in the absence of an enzyme, ligate these free nucleotides into proper 3', 5' phosphodiester bonds, make a template complementary strand, the two strands would melt apart and cycle. These experiments, after some 40 years, have never worked.

On the theoretical level, Eigen and Schusters' Hypercycle model was build upon template replicating RNA strands which formed a hypercycle in which replicating strand pair I, helped replicating strand pair I + 1 replicate around a cycle of such mutualistic strand pairs. This era was followed by the RNA world hypothesis. The discovery of ribozymes led to a sustained effort in which two RNA world views predominated. In the first, a population of RNA ribozyme sequences would mutually catalyze one another's formation, creating what I will call a collectively autocatalyltic set. In the second, a single ribozyme would act as a polymerase able to copy any RNA sequence, including itself - the first self replicating molecule it was hoped. At present, David Bartel has made a candidate ribozyme that can template copy 14 nucleotides.

We may be entering a third era. In 1971 I published a first paper in which polymers, such as proteins, could form a collectively autocatalytic set. This set arises as a phase transition analagous the phase transition in Erdos Renyi random graphs, but "one level up", in a world of chemical reaction graphs and a hypergraph structure in which some molecules in the reaction graph can catalyze some reactions in that very reaction graph. I will discuss how, at a sufficient diversity of polymers, the formation of such a collectively autocatalytic set arises with probability near one.

On the experimental front, G. von Kiedrowski made a single autocatalytic DNA sequence, then the first collectively autocatalytic set of two DNA sequences. In 1995 Reza Ghadiri at Scripps, made the first self reporducing 31 amino acid sequences, and shortly thereafter a collectively autocatalytic set of peptides. Recently, his former post doc, Gonen Ashkanazi has made a collectively autocatalytic set of 9 peptides. In addition, Ashkanazi has engineered these peptides to realize all Boolean functions of 2 inputs, so autocatalytic sets with complex dynamics can now be studied.

Still more recently Mike Steel and Wim Hordijk have improved on my own initial model, showing that the density of catalysis can be much smaller and still yield a phase transition to collectively autocatalytic sets.

At present we are at the stage of generating random "never before born" peptides. I made the first libraries in the late 80s and 90s. Luigi Luisi and independently, Tetsuya Yomo have made such libraries. In 1996 Thomas LaBean in my lab showed that such random peptides fold to molten globules or better. This work has been repeated by both Luisi and Yomo. It is known from phage display that the probability a small peptide binds an epitope is about one in a million. The probability of catalysis of a specific reaction is still unknown. I personally hope collectively autocatalytic sets will be generated soon.

The analysis of industrial clusters has been carried on until now almost prevalently through the traditional statistical approaches used in empirical research. The growing and promising studies of inter-firm relationships stimulated the application of network methodologies, mostly confined to social network analysis. However, though this methodology gives a lot of interesting results, it suffers of the limitation of being static. In order to overcome this failure, this paper applies the methodology of Boolean networks, which allows a dynamic analysis. More specifically, the focus is on the knowledge exchanges flowing through the network of collaborations for innovation, which is indicated by current literature as a fundamental factor of competitiveness of industrial clusters. In particular, it has been studied the inter-firm transfer of managerial knowledge into the aerospace industrial cluster of the Lazio Region (Italy). Both the application of the Boolean network methodology and the content of the managerial knowledge network are traits of originality respect to the literature on industrial clusters and inter-firm relationships. Moreover, for it uses empirical data and introduces some innovative methodological devices this work can be an example replicable in other studies. The main findings are that the number of attractors are very sensitive to the threshold of activation of firms to transfer knowledge, and that even small changes determine the presence of key-players in the attractors (final stable states).