Search

Boolean network is a modeling tool that describes a dynamic system with binary variables and their logical transition formulas. Recent studies in precision medicine use a Boolean network to discover critical genetic alterations that may lead to cancer or target genes for effective therapies to individuals. In this paper, we study a logical inference problem in a Boolean network to find all such critical genetic alterations in a minimal (parsimonious) way. We propose a bilevel integer programming model to find a single minimal genetic alteration. Using the bilevel integer programming model, we develop a branch and bound algorithm that effectively finds all of the minimal alterations. Through a computational study with eleven Boolean networks from the literature, we show that the proposed algorithm finds solutions much faster than the state-of-the-art algorithms in large data sets.

Gene regulatory networks represent the interactions among genes regulating the activation of specific cell functionalities. They have been successfully modelled using Boolean networks, where a set of Boolean variables model the activation state of each gene, and Boolean functions model positive and negative influences among genes. Moreover, when the effect of such influences is additive, threshold Boolean networks, in which Boolean functions are replaced by simpler threshold functions, turned out to be particularly effective. In this paper we propose a systematic translation of threshold Boolean networks into Ehrenfeucht and Rozenberg's reaction systems. Our translation produces a non redundant set of reactions, each using a minimal set of objects. This translation allows us to simulate the behaviour of a general threshold Boolean network by simply executing the (closed) reaction system we obtain, and to investigate causality relations among genes by applying tools available for reaction systems. We implemented our translation in an open-source tool and applied it in two case studies: the gene regulation network of segment polarity in Drosophila melanogaster and the one controlling the differentiation of Th cells in the immune system. In both case studies, we investigate causalities among genes in the reaction system obtained from the translation by applying a tool for the computation of formula based predictors. In the context of the second case study, we show that also Boolean networks with non-additive influences and modelling genes with multiple expression levels can be dealt with by our approach.

In this paper, a chaotic image encryption algorithm based on the matrix semi-tensor product (STP) with a compound secret key is designed. First, a new scrambling method is designed. The pixels of the initial plaintext image are randomly divided into four blocks. The pixels in each block are then subjected to different numbers of rounds of Arnold transformation, and the four blocks are combined to generate a scrambled image. Then, a compound secret key is designed. A set of pseudosecret keys is given and filtered through a synchronously updating Boolean network to generate the real secret key. This secret key is used as the initial value of the mixed linear-nonlinear coupled map lattice (MLNCML) system to generate a chaotic sequence. Finally, the STP operation is applied to the chaotic sequences and the scrambled image to generate an encrypted image. Compared with other encryption algorithms, the algorithm proposed in this paper is more secure and effective, and it is also suitable for color image encryption.

In this paper, we study the induced probabilistic Boolean dynamics for dynamical quantum networks subject to sequential quantum measurements. In this part of the paper, we focus on closed networks of quits whose states evolutions are described by a continuous Lindblad master equation. When measurements are performed sequentially along such continuous dynamics, the quantum network states undergo random jumps and the corresponding measurement outcomes can be described by a probabilistic Boolean network. First of all, we show that the state transition of the induced Boolean networks can be explicitly represented through realification of the master equation. Next, when the open quantum dynamics is relaxing in the sense that it possesses a unique equilibrium as a global attractor, structural properties including absorbing states, reducibility, and periodicity for the induced Boolean network are direct consequences of the relaxing property. Finally, we show that for quantum consensus networks as a type of non-relaxing open quantum network dynamics, the communication classes of the measurement-induced Boolean networks are encoded in the quantum Laplacian of the underlying interaction graph.

This paper studies chaotic image encryption technology and an application of matrix semi-tensor product theory, and a Boolean network encryption algorithm for a synchronous update process is proposed. A 2D-LASM chaotic system is used to generate a random key stream. First, a Boolean network is coded, and a Boolean matrix is generated. If necessary, the Boolean network matrix is diffused in one round so that the Boolean matrix can be saved in the form of an image. Then, three random position scramblings are used to scramble the plaintext image. Finally, using a matrix semi-tensor product technique to generate an encrypted image in a second round of diffusion, a new Boolean network can be generated by encoding the encrypted image. In secure communications, users can choose to implement an image encryption transmission or a Boolean network encryption transmission according to their own needs. Compared with other algorithms, this algorithm exhibits good security characteristics.

In this paper, we investigate the ensemble controllability and reachability for a family of Boolean control networks (BCNs). First, BCNs are converted to discrete-time linear dynamics by the semi-tensor product. Then the ensemble controllability of BCNs is studied via a free control sequence and input Boolean network, respectively. Some necessary and sufficient conditions are obtained to judge the ensemble controllability. The existence of the input Boolean network for the ensemble controllability is also discussed. When there are unknown inputs in BCNs, necessary and sufficient conditions for the controllability are presented as well. Finally, examples are analyzed to show the effectiveness of the proposed results.

Boolean networks are a well-established formalism for modelling biological systems. An important aspect of analysing a Boolean network is to identify all its attractors. This becomes challenging for large Boolean networks due to the infamous state-space explosion problem. In this paper, we propose a new strongly connected component (SCC) based decomposition method for attractor detection in large synchronous Boolean networks and prove its correctness. Experimental results show that our proposed method is significantly better in terms of performance when compared to existing methods in the literature.

Boolean network tomography can limit optical nodes on which electronic monitors need to be placed in all-optical mesh networks. However, required monitoring cost for operation and deployment increases as the number of optical nodes equipped with the electronic monitors decreases. The required monitoring cost depends heavily on the length of configured all-optical monitoring trails. Two heuristic approaches have been proposed to compute monitoring trails for localizing multiple-link failures. However, these existing approaches cannot control the length of computed monitoring trails in the given monitor placement. This paper proposes a novel approach to minimize the required monitoring cost in the given monitor placement. The proposed approach exploits a greedy method where the routes for the monitoring trails are extended in a hop-by-hop manner to localize all link failures in arbitrary failure scenarios. The greedy method can control the length of monitoring trails flexibly due to the hop-by-hop extension of monitoring trails. The simulation results confirm that the proposed approach can minimize the total monitoring cost adaptively by adjusting the length of monitoring trails on the basis of the trade-off relationship between the monitoring operation cost and deployment cost.

This paper researches the synchronization of asynchronous probabilistic Boolean network and synchronization theorems are provided. Inner synchronization and outer synchronization are considered, respectively. It should be pointed that synchronization theorems and corollaries with probability one and probabilities unequal to one are both taken into consideration. What’s more, the asynchronous multivalued Boolean network is also studied as an extension. Finally, some examples for asynchronous probabilistic Boolean network synchronizations are provided in the numerical simulation.

Boolean network models provide an efficient way for studying gene regulatory networks. The main dynamics of a Boolean network is determined by its attractors. Attractor calculation plays a key role for analyzing Boolean gene regulatory networks. An approach of attractor calculation was proposed in this study, which combined the predecessor approach and the logic unsatisfiability approach to accelerate attractor calculation. The proposed algorithm is effective to calculate all attractors for large-scale Boolean gene regulatory networks even the networks with a relatively large average degree.

Non-Linear Feedback Shift Registers (NFSRs) are a generalization of Liner Feedback Shift Registers (LFSRs). The study of NFSR sequence helps to analyze the cryptographical security of NFSR-based stream cipher. Due to lack of efficient algebraic tools, the period of NFSR still remains an open crucial theoretical problem. In this paper, we view the NFSR as a Boolean network (BN), so that the study about the period of NFSR can be viewed as the study about period of BN. Furthermore, based on the mathematical tool of semi-tensor product (STP), a Boolean network can be mapped into an algebraic form. For these, we put forward a method for reconstructing the period of NFSR with single input. Especially, we propose a procedure to choose the controlled states and steer the controlled states from initial state to desirable one. At last, the general derivation is exemplified by numerical simulations for a kind of NFSR.

In this paper, the equivalence issue between state feedback controller and free sequence controller in Boolean control network (BCN) is investigated. Based on the algebraic representation of Boolean networks, we prove that a Boolean control network can be stabilized to a cycle or a fixed point via free sequence controller if and only if there is a state feedback controller which can derive the Boolean control network to the cycle or the fixed point. Then, two algorithms are provided to find the state feedback controller. After that, we prove that a BCN can be globally controllable by free sequence controller, while the BCN is not necessarily globally controllable by state feedback controller. At last, an example is given to illustrate the results.

This paper studies the cluster synchronization of Boolean network with open-loop control. Both synchronous Boolean network and asynchronous Boolean network are considered. Firstly, the basic cluster synchronization concept in synchronous Boolean network is provided and necessary and sufficient conditions are derived. Secondly, with different update scheme, necessary and sufficient conditions for cluster synchronization to reference trajectories are provided and open-loop cycle controllers are designed. Finally, some numerical examples are provided and results show the efficiency of cluster synchronization methods in Boolean network.

We introduce and discuss duality operators on the set of binary extended Boolean functions, i.e., on the set of binary operations on the real interval [ 0 , 1 ] whose restrictions to Boolean inputs yield Boolean functions. These dualities have been divided into seven classes, and the majority of their properties depend on the class they belong to. We study composition of dualities, properties of dual classes, duality of properties of extended Boolean functions and invariantness of extended Boolean functions with respect to particular dualities. Our approach allows to transfer the results known for some studied class of extended Boolean functions into the results for the corresponding dual classes. As typical examples, one can recall the standard duality of the classes of all t-norms and t-conorms and the duality of implication functions and conjunctive (disjunctive) aggregation functions.

State feedback control design to make the response Boolean network synchronize with the drive Boolean network is far from being solved in the literature. Motivated by this, this paper studies the feedback control design for the complete synchronization of two coupled Boolean networks with time delays. A necessary condition for the existence of a state feedback controller is derived first. Then the feedback control design procedure for the complete synchronization of two coupled Boolean networks is provided based on the necessary condition. Finally, an example is given to illustrate the proposed design procedure.

A probabilistic Boolean network (PBN) is a discrete network composed of a family of Boolean networks together with a set of probabilities governing the selection of a Boolean network at each time step. We introduce in this paper a novel observability problem for PBNs. Specifically, we assume that the values of the initial state of the PBN are not known with certainty, but can be described by probability distributions. We ask ourselves under which conditions it is possible to uniquely determine the probability distribution of initial states when giving only knowledge of the evolution of the probability distributions of network outputs. We propose a complete answer to this problem using a linear algebra approach. Several examples, both artificial and real-world, are given and illustrate the viability of the proposed theoretical results.

Inferring Boolean networks is crucial for modeling and analyzing gene regulatory networks from a systematic perspective. However, the state-of-the-art algorithms cannot accurately infer the topology and dynamics of Boolean networks due to the lack of an efficient approach to representing the unknown Boolean functions and the over-fit problem caused by the noise in time-series data. To address these problems, we propose a novel inference algorithm using a genetic algorithm with novel polynomial representation and encoding scheme (GAPORE) to reconstruct large-scale Boolean networks accurately. First of all, a novel symbolic polynomial representation method is introduced to efficiently represent the unknown Boolean functions of the candidate Boolean network as the symbolic polynomial dynamical equations. Then, a novel encoding scheme is developed to flexibly encode the symbolic polynomial dynamical equations by varying the effective lengths of the chromosomes. To reduce the over-fit problem, the l 2 -norm regularization is designed into the fitness evaluation in view of the network sparsity. In addition, the local search strategy is embedded into the hybrid genetic algorithm framework to strengthen the search capability. Extensive experiments demonstrate that GAPORE can infer the large-scale Boolean networks more accurately than state-of-the-art algorithms from the noisy time-series data.

Determining the minimum number of sensor nodes to observe the internal state of the whole system is important in analysis of complex networks. However, existing studies suggest that a large number of sensor nodes are needed to know the whole internal state. In this paper, we focus on identification of a small set of sensor nodes to discriminate statically and periodically steady states using the Boolean network model where steady states are often considered to correspond to cell types. In other words, we seek a minimum set of nodes to discriminate singleton and periodic attractors. We prove that one node is not necessarily enough but two nodes are always enough to discriminate two periodic attractors by using the Chinese remainder theorem. Based on this, we present an algorithm to determine the minimum number of nodes to discriminate all given attractors. We also present a much more efficient algorithm to discriminate singleton attractors. The results of computational experiments suggest that attractors in realistic Boolean networks can be discriminated by observing the states of only a small number of nodes.

This paper is devoted to studying function perturbations on the transition matrix and topological structure of a singular Boolean network (SBN) via the semi-tensor product of matrices. First, the algebraic form of an SBN is given, and we discuss how the transition matrix of the SBN changes under function perturbations. Then the local uniqueness of solutions to the SBN is studied, under which the impacts of function perturbations on the topological structure are investigated. Finally, examples are given to show the effectiveness of the obtained results.

A finite dynamical system is a system consisting of some finite number of objects that take upon a value from some domain as a state, in which after initialization the states of the objects are updated based upon the states of the other objects and themselves according to a certain update schedule. This paper studies a subclass of finite dynamical systems the synchronous Boolean finite dynamical system (synchronous BFDS, for short), where the states are Boolean and the state update takes place in discrete time and at the same on all objects. The paper is concerned with three problems, Convergence, Path Intersection, and Cycle Length, of the synchronous BFDS in which the state update functions (or the local state transition functions) are chosen from a predetermined finite basis of Boolean functions B . The paper results characterize their computational complexity.

Motivated by the elicitation or the learning of certain types of models for classifying objects in ordered categories based on several criteria, we categorize the positive Boolean functions up to 6 variables. We list all inequivalent positive Boolean functions and we determine the smallest degree k of the k -additive capacity that can be used for separating their true points from their false points. 1-additive Boolean functions are the well-studied threshold functions. Each function is described by its set of minimal true points. The latter correspond to the minimal winning coalitions of simple games. They also correspond to the minimal sufficient coalitions in the multiple criteria classification models we are interested in, namely, the MR-Sort and the noncompensatory sorting model.

Based on semi-tensor product of matrices, global robust stability and stabilization of Boolean network (BN) with disturbances are investigated. Firstly, the definition of global robust stability for BN with disturbances is presented. By using the algebraic state space representation of disturbed BN, some necessary and sufficient criteria are obtained to ensure the global robust stability with respect to (w.r.t.) a fixed point or w.r.t. a limit cycle. In contrast, if a given disturbed BN is not globally robust stable w.r.t. a fixed point or w.r.t. a limit cycle, system can achieve stability by a matrix transformation technique. However, it is a difficult task to find such a suitable matrix transformation. In this paper, a pinning state feedback control design is proposed to find a suitable transformation. The obtained results are well illustrated by numerical example.

Evolvability and robustness are crucial for the origin and maintenance of complex organisms, but may not be simultaneously achievable as robust traits are also hard to change. Andreas Wagner has proposed a solution to this paradox by arguing that the many-to-few aspect of genotype-phenotype maps creates neutral networks of genotypes coding for the same phenotype. Phenotypes with large networks are genetically robust, but they may also have more neighboring phenotypes and thus higher evolvability. In this paper, we explore the generality of this idea by sampling large numbers of random genotype-phenotype maps for Boolean genotypes and phenotypes. We show that there is indeed a preponderance of positive correlations between the evolvability and robustness of phenotypes within a genotype-phenotype map, but also that there are negative correlations between average evolvability and robustness across maps. We interpret this as predicting a positive correlation across the phenotypic states of a character, but a negative correlation across characters. We also argue that evolvability and robustness tend to be negatively correlated when phenotypes are measured on ordinal or higher scale types. We conclude that Wagner's conjecture of a positive relation between robustness and evolvability is based on strict and somewhat unrealistic biological assumptions.

Boolean network has been widely used in modeling biological systems and one of the key problems is its stability in response to small perturbations. Based on the hypothesis that the states of all nodes are homogenously updated, great progress has been made in previous works. In real biological networks, however, the updates of genes typically show much heterogeneity. To address such conditions, we introduce transmission sensitivity into Boolean network model. By the method of semi-annealed approximation, we illustrate that in a homogenous network, the critical condition of stability has no connection with its transmission sensitivity. As for heterogeneous networks, it reveals that correlations between network topology and transmission sensitivity can have profound effects on the its stability. This result shows a new mechanism that affects the stability of Boolean network, which could be used to control the dynamics in real biological systems.

Although several methods for estimating the resistance of a random Boolean function against (fast) algebraic attacks were proposed, these methods are usually infeasible in practice for relatively large number of input variables n (for instance n 30) due to increased computational complexity. An efficient estimation of the resistance of Boolean functions, with relatively large number of inputs n, against (fast) algebraic attacks appears to be a rather difficult task. In this paper, the concept of partial linear relations decomposition is introduced, which decomposes any given nonlinear Boolean function into many linear (affine) subfunctions by using the disjoint sets of input variables. Based on this result, a general probabilistic decomposition algorithm for nonlinear Boolean functions is presented which gives a new framework for estimating the resistance of Boolean function against (fast) algebraic attacks. It is shown that our new probabilistic method gives very tight estimates (lower and upper bound) and it only requires about O(n22n) operations for a random Boolean function with n variables, thus having much less time complexity than previously known algorithms.

Canalyzing Boolean functions have shown their popularity in various biological networks and established themselves to be biologically meaningful at the system level, marking their importance in the analysis of stability and robustness of such complex systems. Based on a matrix representation of Boolean networks due to the recently developed tool called semi-tensor product, we categorize canalyzing functions in terms of their capabilities of affecting the number of attractors in the Boolean network, which is one key index for the stability and robustness of Boolean networks. We show that there exist only three categories of attractor-effective canalyzing functions for any network size larger than 1, while the number of all the interested canalyzing functions is proportional to the square of the network size. We also give the explicit expression of the mean number of attractors with any length for Boolean networks with a single canalyzing function. Compared with Boolean networks without any canalyzing functions, we are able to show quantitatively how canalyzing functions can affect the mean number and length of attractors in Boolean networks for the first time.

A Boolean network is a discrete-time finite state dynamical system, whose variables take values from the binary set {0,1}, and the value update rules are Boolean functions. A conjunctive Boolean network is a special type of Boolean network, whose value update rule for each variable is comprised only of “AND” operations. Recently there have been extensive investigations on conjunctive Boolean networks. Questions about asymptotic behaviors, stabilities of periodic orbits, and reachability and observability have all been addressed to some extent. We focus in this paper on controllability of a conjunctive Boolean network. Specifically, assuming that there is a selected subset of variables whose values are determined by external control inputs, we pose and answer the question of whether (and how) one can steer the system from any initial state to any final state. We establish a necessary and sufficient condition, via a graphical approach, for a conjunctive Boolean network to be controllable. An explicit control law is also presented along the analysis.

This paper studies the set stabilization of switched Boolean control networks, in which a feedback control design algorithm is presented by a constructive method. Necessary and sufficient conditions of the set stabilization of switched Boolean control networks under arbitrary switching signals are presented for the cases of the control input relying on switching signals or not, respectively. Furthermore, the corresponding switching-signal-independent and switching-signal-dependent controllers are provided for these two cases, respectively. It is shown that the condition of the switching-signal-dependent controller is less conservative than the one of the switching-signal-independent controller. Finally, examples are given to illustrate the effectiveness of the proposed results.

Nonlinear filter generators are commonly used as keystream generators in stream ciphers. A nonlinear filter generator utilizes a nonlinear filtering function to combine the outputs of a linear feedback shift register (LFSR) to improve the linear complexity of keystream sequences. However, the LFSR-based stream ciphers are still potentially vulnerable to algebraic attacks that recover the key from some keystream bits. Although the known algebraic attacks only require polynomial time complexity of computations, all have their own constraints. This paper uses the linearization of nonlinear filter generators to cryptanalyze LFSR-based stream ciphers. Such a method works for any nonlinear filter generators. Viewing a nonlinear filter generator as a Boolean network that evolves as an automaton through Boolean functions, we first give its linearization representation. Compared to the linearization representation in Limniotis et al. (2008), this representation requires lower spatial complexity of computations in most cases. Based on the representation, the key recoverability is analyzed via the observability of Boolean networks. An algorithm for key recovery is given as well. Compared to the exhaustive search to recover the key, using this linearization representation requires lower time complexity of computations, though it leads to exponential time complexity.

Progress in cell type reprogramming has revived the interest in Waddington's concept of the epigenetic landscape. Recently researchers developed the quasi-potential theory to represent the Waddington's landscape. The Quasi-potential U(x), derived from interactions in the gene regulatory network (GRN) of a cell, quantifies the relative stability of network states, which determine the effort required for state transitions in a multi-stable dynamical system. However, quasi-potential landscapes, originally developed for continuous systems, are not suitable for discrete-valued networks which are important tools to study complex systems. In this paper, we provide a framework to quantify the landscape for discrete Boolean networks (BNs). We apply our framework to study pancreas cell differentiation where an ensemble of BN models is considered based on the structure of a minimal GRN for pancreas development. We impose biologically motivated structural constraints (corresponding to specific type of Boolean functions) and dynamical constraints (corresponding to stable attractor states) to limit the space of BN models for pancreas development. In addition, we enforce a novel functional constraint corresponding to the relative ordering of attractor states in BN models to restrict the space of BN models to the biological relevant class. We find that BNs with canalyzing/sign-compatible Boolean functions best capture the dynamics of pancreas cell differentiation. This framework can also determine the genes' influence on cell state transitions, and thus can facilitate the rational design of cell reprogramming protocols., Comment: 24 pages, 6 figures, 1 table

Arvind and Vasudev 2 have introduced the notion of an approximate isomorphism between two Boolean functions f and g. They furthermore designed two algorithms that construct an approximate isomorphism when given oracle access to f and g. The first of these algorithms is specialized to Boolean functions which are computable by constant-depth circuits. The second one applies to any pair of Boolean functions. It runs in exponential time and achieves optimality up to a factor of order n . In this paper, we present an improved analysis and come up with a variant of the second algorithm that runs in polynomial time and achieves optimality up to a factor of (approximately) 2. A new algorithm for the construction of approximate ismorphisms between Boolean functions.Improvement on an existing algorithm in several respects.Efficiency: it works in polynomial time.Performance: better performance guarantees as before.

Core input-state cycles are proposed to investigate the synchronization of two deterministic Boolean networks coupled in the master-slave configuration. Firstly, by using the algebraic form of the master-slave system, a new Boolean control network (BCN) is constructed and an algorithm is given to find core input-state cycles of the newly constructed BCN. Secondly, based on these cycles, a necessary and sufficient condition is derived for the existence of a synchronizing state feedback controller. Accordingly, an algorithm is provided for verifying the existence of feasible state feedback controllers. Thirdly, a constructive method is developed to design a synchronizing state feedback controller when the existence condition obtained above is satisfied. Our results are significantly superior to the existing relevant results. Finally, an example is employed to show the effectiveness of our results.

A random Boolean network (RBN) is a generic model of interactions between entities with binary states that has applications in different fields. As real-world systems often operate on the border between order and chaos, algorithms simulating RBN's transition to a critical state are of particular interest. Adaptive RBNs (ARBNs) can evolve towards such a state by rewiring of nodes according to their states on the attractor. Numerical simulation of ARBNs larger than several dozens of nodes is computationally hard due to an enormous growth of attractor lengths and transient periods. In this paper, we propose a GPGPU algorithm for parallel simulation of ARBNs with modified activity-dependent rewiring rule which can be used with any sequential algorithm for attractor's search. In the experimental part of the study, we investigate the performance of parallel implementation and the influence of parameters of the algorithm on the speed of convergence to a steady state.

Boolean networks can describe dynamics of genetic and cellular networks in a simple and abstract framework. This paper presents a constant control scheme for stabilization of large-scale Boolean networks. A number of state nodes are selected as constant control inputs so that the Boolean network can reach desirable attractors or cycles. Strongly connected components of the Boolean network are considered to reduce the computational cost. A simulation study on the problem of determining combinatorial targeted drugs for desired cellular phenotype is provided.

International audience; Discrete modelling frameworks of Biological networks can be divided in two distinct categories: Boolean and multivalued. Although multivalued networks are more expressive for qualifying the regulatory behaviours modelled by more than two values, the ability to automatically convert them to Boolean network with an equivalent behaviour breaks down the fundamental borders between the two approaches. Theoretically investigating the conversion process provides relevant insights into bridging the gap between them. Basically, the conversion aims at finding a Boolean network bisimulating a multivalued one. In this article, we investigate the bisimilar conversion where the Boolean integer coding is a parameter that can be freely modified. Based on this analysis, we define a computational method automatically inferring a bisimilar Boolean network from a given multivalued one.

In this paper, the set stabilization problem of switched Boolean networks is reinvestigated. An event-triggered mechanism is formulated in the process of designing time-varying set stabilization state feedback controller. First, compared with the existing results, an improved algorithm which can effectively reduce computational complexity of calculating the maximum control invariant set is given. Second, using Warshall algorithm, an explicit criterion is derived to check whether a switched Boolean network satisfies set stabilization. Third, a systematic procedure is devised to design event-triggered set stabilization state feedback controller of switched Boolean networks. Then, a method is proposed to obtain all possible event-triggered state feedback controllers for set stabilization of switched Boolean networks. Finally, two examples are shown to demonstrate the effectiveness of presented results.

This study addresses the set stability of Boolean networks (BNs) and set stabilization of Boolean control networks (BCNs). Set stability determines whether a BN converges to a given subset, whereas set stabilizability addresses the issue of whether a BCN can be stabilized to a given subset. Many problems can be viewed as special cases of set stability and set stabilization, including synchronization, partial stability, and partial stabilization problems. The concepts of invariant subset and control invariant subset are introduced. Then, algorithms for the largest invariant subset and the largest control invariant subset contained in a given subset are proposed. Based on the invariant subsets obtained, the necessary and sufficient conditions for set stability and set stabilizability are established, and formulae are provided to calculate the shortest transient periods for respective initial states. A design procedure is proposed for finding all the time-optimal set stabilizers. Finally, an example is used to show the application of the proposed results to the synchronization problem of BNs.

In this manuscript we propose and implement a dimension reduction algorithm of AND-NOT networks for the purpose of steady state computation. Our method of network reduction consists in using “steady state approximations” that do not change the number of steady states. The algorithm is designed to work at the wiring diagram level without the need to evaluate or simplify Boolean functions. Also, our implementation of the algorithm takes advantage of the sparsity typical of discrete models of biological systems.The main features of our reduction algorithm are that it works at the wiring diagram level and it preserves the number of steady states. Furthermore, the steady states of the original network can be recovered from the steady states of the reduced network; thus, all steady states are found. Also, heuristic analysis and simulations show that it runs in polynomial time. We used our results to study AND-NOT network models of gene networks and showed that our algorithm greatly simplifies steady state analysis. Furthermore, our algorithm can handle sparse AND-NOT networks with up to 1,000,000 nodes.

Boolean variables are such that they take values on Z 2 ≅ { 0 , 1 } . NK-Kauffman networks are dynamical deterministic systems of N Boolean functions that depend only on K ≤ N Boolean variables. They were proposed by Kauffman as a first step to understand cellular behavior (Kauffman, 1969) with great success. Among the problems that still have not been well understood in Kauffman networks, is the mechanism that regulates the phase transition of the system from an ordered phase where small changes of the initial state decay, to a chaotic one, where they grow exponentially. I show, that this mechanism is regulated through the irreducible decomposition of Boolean functions proposed in Zertuche (2009). This is in contrast to previous knowledge that attributed it to canalization . I also review other statistical properties of Kauffman networks that Boolean irreducibility explains.

Nonlinear feedback shift registers (NFSRs) have been used as the main building blocks in many stream ciphers and convolutional decoders. The linearization of NFSRs is to find their state transition matrices. This paper uses a Boolean network approach to facilitate the linearization of NFSRs. A new state transition matrix is found for an NFSR, which can be simply computed from the truth table of its feedback function. Compared to the existing results, the new state transition matrix is easier to compute and is more explicit. Some properties of the matrix are provided, which are helpful to theoretically analyze NFSRs.

We present dichotomy theorems regarding the computational complexity of counting fixed points in boolean (discrete) dynamical systems, i.e., finite discrete dynamical systems over the domain {0,1}. For a class F of boolean functions and a class G of graphs, an (F,G)-system is a boolean dynamical system with local transitions functions lying in F and graphs in G. We show that, if local transition functions are given by lookup tables, then the following complexity classification holds: Let F be a class of boolean functions closed under superposition and let G be a graph class closed under taking minors. If F contains all min-functions, all max-functions, or all self-dual and monotone functions, and G contains all planar graphs, then it is #P-complete to compute the number of fixed points in an (F,G)-system; otherwise it is computable in polynomial time. We also prove a dichotomy theorem for the case that local transition functions are given by formulas (over logical bases). This theorem has a significantly more complicated structure than the theorem for lookup tables. A corresponding theorem for boolean circuits coincides with the theorem for formulas., Comment: 16 pages, extended abstract presented at 10th Italian Conference on Theoretical Computer Science (ICTCS'2007)

The stock prices of companies with businesses that are closely related within a specific sector of economy might exhibit movement patterns and correlations in their dynamics. The idea in this work is to use the concept of autocatalytic network to model such correlations and patterns in the trends exhibited by the expected returns. The trends are expressed in terms of positive or negative returns within each fixed time interval. The time series derived from these trends is then used to represent the movement patterns by a probabilistic boolean network with transitions modeled as an autocatalytic network. The proposed method might be of value in short term forecasting and identification of dependencies. The method is illustrated with a case study based on four stocks of companies in the field of natural resource and technology.

Cancer has become known as a complex and systematic disease on macroscopic, mesoscopic and microscopic scales. Systems biology employs state-of-the-art computational theories and high-throughput experimental data to model and simulate complex biological procedures such as cancer, which involves genetic and epigenetic, in addition to intracellular and extracellular complex interaction networks. In this paper, different systems biology modeling techniques such as systems of differential equations, stochastic methods, Boolean networks, Petri nets, cellular automata methods and agent-based systems are concisely discussed. We have compared the mentioned formalisms and tried to address the span of applicability they can bear on emerging cancer modeling and simulation approaches. Different scales of cancer modeling, namely, microscopic, mesoscopic and macroscopic scales are explained followed by an illustration of angiogenesis in microscopic scale of the cancer modeling. Then, the modeling of cancer cell proliferation and survival are examined on a microscopic scale and the modeling of multiscale tumor growth is explained along with its advantages.

This paper investigates cycles of periodically time-variant Boolean networks (PTVBNs). Some properties of cycles of PTVBNs and the relationship between PTVBNs and time-invariant Boolean networks (TIBNs) are revealed. It is shown that each cycle of a PTVBN corresponds to a common cycle of some TIBNs. And, all the cycles of a PTVBN can be constructed by those of the corresponding TIBNs. Moreover, some results on lengths of cycles of PTVBNs are derived. Finally, some examples are given to illustrate the obtained theoretical results.

This paper introduces an algorithm to learn the strategy updating rule for a two- person Boolean game using the records of the history strategies and game results. The two-person game in this paper is introduced as a zero-sum game along with a Boolean strategy set, and the strategies are governed by fixed Boolean functions whose arguments are the history strategies and game results with additive binary noise, which can be modeled as a stochastic Boolean dynamic system. However, for this easy-to-play game, there is no effective convenient methods to win more often. To achieve this goal, a learning algorithm based on Boolean regression and maximum-likelihood estimation is put forward to learn the strategy updating rule and the noise property using the records of the history strategies and game results. In addition, extensive simulations via actual examples have illustrated the effectiveness of the proposed learning algorithm.

This work presents a network model for representation of the evolution of certain patterns of economic behavior. More specifically, after representing the agents as points in a space in which each dimension associated to a relevant economic variable, their relative “motions” that can be either stationary or discordant, are coded into a boolean network. Patterns with stationary averages indicate the maintenance of status quo, whereas discordant patterns represent aggregation of new agent into the cluster or departure from the former policies. The changing patterns can be embedded into a network representation, particularly using the concept of autocatalytic boolean networks. As a case study, the economic tendencies of the BRIC countries + Argentina were studied. Although Argentina is not included in the cluster formed by BRIC countries, it tends to follow the BRIC members because of strong commercial ties.

Display Omitted Devised a novel structural measure called hierarchical closeness (HC) to rank disease risk of genes in a directed biological network.Hierarchical closeness outperforms the other well-known structural centrality measures, particularly for cancer, hereditary, immune, and neurodegenerative disease-related genes in a human signaling network.The set of HC-center genes are different from the hub genes with the largest interactions.Genes with relatively high hierarchical closeness are significantly likely to encode proteins in the extracellular matrix and receptor proteins in a human signaling network.All the findings were reproduced in a random Boolean network model. BackgroundMany structural centrality measures were proposed to predict putative disease genes on biological networks. Closeness is one of the best-known structural centrality measures, and its effectiveness for disease gene prediction on undirected biological networks has been frequently reported. However, it is not clear whether closeness is effective for disease gene prediction on directed biological networks such as signaling networks. ResultsIn this paper, we first show that closeness does not significantly outperform other well-known centrality measures such as Degree, Betweenness, and PageRank for disease gene prediction on a human signaling network. In addition, we observed that prediction accuracy by the closeness measure was worse than that by a reachability measure, but closeness could efficiently predict disease genes among a set of genes with the same reachability value. Based on this observation, we devised a novel structural measure, hierarchical closeness, by combining reachability and closeness such that all genes are first ranked by the degree of reachability and then the tied genes are further ranked by closeness. We discovered that hierarchical closeness outperforms other structural centrality measures in disease gene prediction. We also found that the set of highly ranked genes in terms of hierarchical closeness is clearly different from that of hub genes with high connectivity. More interestingly, these findings were consistently reproduced in a random Boolean network model. Finally, we found that genes with relatively high hierarchical closeness are significantly likely to encode proteins in the extracellular matrix and receptor proteins in a human signaling network, supporting the fact that half of all modern medicinal drugs target receptor-encoding genes. ConclusionTaken together, hierarchical closeness proposed in this study is a novel structural measure to efficiently predict putative disease genes in a directed signaling network.

The attractor graph of a Boolean network F has the attractors of F as vertices. There is a directed edge between attractors A i and A j if there is a state x ? A i and an index k such that x when perturbed in the kth coordinate yields a state x ' in the basin of attractor A j . Kauffman (2007) proposed to use the strongly connected components of the attractor graph (called ergodic sets) to model possible targets for cell differentiation. However, computational follow-up work by him and others has revealed that most Boolean networks have a single strongly connected component in an overwhelming number of cases, and two strongly connected components in rare cases.As a proof of concept, we explicitly construct classes of hierarchical, nonuniform Boolean networks where the attractor graph may have an arbitrary number of ergodic sets. The construction uses threshold functions and networks that are combinations of connected cliques. Earlier work does not address the structure of ergodic sets. Building on the previous construction we show how to generate Boolean networks where ergodic sets possess binary hyper-cubes Q 2 m as sub-graphs.Although the focus of this paper is to demonstrate that there are Boolean networks with a large number of ergodic sets and that ergodic sets can be arbitrarily large; we remark that networks we construct have community structure and the results may therefore be relevant to application areas ranging from biology to social science. The results also provide a starting point for additional studies into the attractor structure of Boolean networks, their basins of attractions, and conditions for stability under state noise.