Control of Large-Scale Boolean Networks via Network Aggregation

Output Stabilizing Control of Complex Biological Networks Based on Boolean Algebra Analysis

Output stabilizing control of biological systems is of utmost importance in systems biology since key phenotypes of biological networks are often encoded by a small subset of their phenotypic marker nodes. This study addresses the challenge of output stabilizing control for complex biological systems modeled by Boolean networks (BNs). The objective is to identify a set of constant control inputs capable of driving the BN toward a desirable long-term behavior with respect to specified output nodes. Leveraging the algebraic properties of Boolean logic, we develop a novel control algorithm that reformulates the output stabilizing control problem into a simple graph theoretic problem involving auxiliary BNs, the scale of which significantly decreases compared to the original BN. The proposed method ensures superiority over previous results in terms of both the number of control inputs and computational loads, since it searches for the solution within the reduced BNs while retaining essential structures needed for output stabilization. The efficacy of the proposed control scheme is demonstrated through extensive numerical experiments with complex random BNs and real biological networks. To support the reproducible research initiative, detailed results of numerical experiments are provided in the supplementary material, and all the implementation codes are made accessible at https://github.com/choonlog/OutputStabilization.

Attractor-Transition Control of Complex Biological Networks: A Constant Control Approach

This article presents attractor-transition control of complex biological networks represented by Boolean networks (BNs) wherein the BN is steered from a prescribed initial attractor toward a desired one. The proposed approach leverages the similarity between attractors and Boolean algebraic properties embedded in the underlying state transition equations. To enhance the clarity of expression regarding stabilization toward the desired attractor, a simple coordinate transformation is performed on the considered BN. Based on the characteristics of transformed state equations, self-stabilizing state variables requiring no control efforts are derived in the first. Next, by applying the feedback vertex set (FVS) control scheme, control inputs stabilizing the remaining state variables are determined. The proposed control scheme exhibits versatility by accommodating both fixed-point and cyclic attractors. We validate the effectiveness of the proposed strategy through extensive numerical experiments conducted on random BNs as well as complex biological systems. In adherence to the reproducible research initiative, detailed results of numerical experiments and all the implementation codes are provided on the authors' website: https://github.com/choonlog/AttractorTransition.

Feedback Stabilization of Boolean Control Networks With Missing Data

Data loss is often random and unavoidable in realistic networks due to transmission failure or node faults. When it comes to Boolean control networks (BCNs), the model actually becomes a delayed system with unbounded time delays. It is difficult to find a suitable way to model it and transform it into a familiar form, so there have been no available results so far. In this article, the stabilization of BCNs is studied with Bernoulli-distributed missing data. First, an augmented probabilistic BCN (PBCN) is constructed to estimate the appearance of data loss items in the model form. Based on this model, some necessary and sufficient conditions are proposed based on the construction of reachable matrices and one-step state transition probability matrices. Moreover, algorithms are proposed to complete the state feedback stabilizability analysis. In addition, a constructive method is developed to design all feasible state feedback controllers. Finally, illustrative examples are given to show the effectiveness of the proposed results.

On the Compressive Power of Boolean Threshold Autoencoders

An autoencoder is a layered neural network whose structure can be viewed as consisting of an encoder, which compresses an input vector to a lower dimensional vector, and a decoder, which transforms the low-dimensional vector back to the original input vector (or one that is very similar). In this article, we explore the compressive power of autoencoders that are Boolean threshold networks by studying the numbers of nodes and layers that are required to ensure that each vector in a given set of distinct input binary vectors is transformed back to its original. We show that for any set of n distinct vectors there exists a seven-layer autoencoder with the optimal compression ratio, (i.e., the size of the middle layer is logarithmic in n ), but that there is a set of n vectors for which there is no three-layer autoencoder with a middle layer of logarithmic size. In addition, we present a kind of tradeoff: if the compression ratio is allowed to be considerably larger than the optimal, then there is a five-layer autoencoder. We also study the numbers of nodes and layers required only for encoding, and the results suggest that the decoding part is the bottleneck of autoencoding. For example, there always is a three-layer Boolean threshold encoder that compresses n vectors into a dimension that is twice the logarithm of n .

Temporary and permanent control of partially specified Boolean networks

Boolean networks (BNs) are a well-accepted modelling formalism in computational systems biology. Nevertheless, modellers often cannot identify only a single BN that matches the biological reality. The typical reasons for this is insufficient knowledge or a lack of experimental data. Formally, this uncertainty can be expressed using partially specified Boolean networks (PSBNs), which encode the wide range of network candidates into a single structure. In this paper, we target the control of PSBNs. The goal of BN control is to find perturbations which guarantee stabilisation of the system in the desired state. Specifically, we consider variable perturbations (gene knock-out and over-expression) with three types of application time-window: one-step, temporary, and permanent. While the control of fully specified BNs is a thoroughly explored topic, control of PSBNs introduces additional challenges that we address in this paper. In particular, the unspecified components of the model cause a significant amount of additional state space explosion. To address this issue, we propose a fully symbolic methodology that can represent the numerous system variants in a compact form. In fully specified models, the efficiency of a perturbation is characterised by the count of perturbed variables (the perturbation size). However, in the case of a PSBN, a perturbation might work only for a subset of concrete BN models. To that end, we introduce and quantify perturbation robustness. This metric characterises how efficient the given perturbation is with respect to the model uncertainty. Finally, we evaluate the novel control methods using non-trivial real-world PSBN models. We inspect the method's scalability and efficiency with respect to the size of the state space and the number of unspecified components. We also compare the robustness metrics for all three perturbation types. Our experiments support the hypothesis that one-step perturbations are significantly less robust than temporary and permanent ones.

On the Distribution of Successor States in Boolean Threshold Networks

We study the distribution of successor states in Boolean networks (BNs). The state vector y is called a successor of x if y = F(x) holds, where x, y ∈ {0,1}ⁿ are state vectors and F is an ordered set of Boolean functions describing the state transitions. This problem is motivated by analyzing how information propagates via hidden layers in Boolean threshold networks (discrete model of neural networks) and is kept or lost during time evolution in BNs. In this article, we measure the distribution via entropy and study how entropy changes via the transition from x to y , assuming that x is given uniformly at random. We focus on BNs consisting of exclusive OR (XOR) functions, canalyzing functions, and threshold functions. As a main result, we show that there exists a BN consisting of d -ary XOR functions, which preserves the entropy if d is odd and , whereas there does not exist such a BN if d is even. We also show that there exists a specific BN consisting of d -ary threshold functions, which preserves the entropy if [Formula: see text]. Furthermore, we theoretically analyze the upper and lower bounds of the entropy for BNs consisting of canalyzing functions and perform computational experiments using BN models of real biological networks.

Infinite-Horizon Optimal Control of Switched Boolean Control Networks With Average Cost: An Efficient Graph-Theoretical Approach

This study investigates the infinite-horizon optimal control (IHOC) problem for switched Boolean control networks with an average cost criterion. A primary challenge of this problem is the prohibitively high computational cost when dealing with large-scale networks. We attempt to develop a more efficient approach from a novel graph-theoretical perspective. First, a weighted directed graph structure called the optimal state transition graph (OSTG) is established, whose edges encode the optimal action for each admissible state transition between states reachable from a given initial state subject to various constraints. Then, we reduce the IHOC problem into a minimum-mean cycle (MMC) problem in the OSTG. Finally, we develop an algorithm that can quickly find a particular MMC by resorting to Karp's algorithm in the graph theory and construct an optimal switching control law based on state feedback. The time complexity analysis shows that our algorithm, albeit still running in exponential time, can outperform all the existing methods in terms of time efficiency. A 16-state-3-input signaling network in leukemia is used as a benchmark to test its effectiveness. Results show that the proposed graph-theoretical approach is much more computationally efficient and can reduce the running time dramatically: it runs hundreds or even thousands of times faster than the existing methods. The Python implementation of the algorithm is available at https://github.com/ShuhuaGao/sbcn_mmc.

Identification of periodic attractors in Boolean networks using a priori information

Boolean networks (BNs) have been developed to describe various biological processes, which requires analysis of attractors, the long-term stable states. While many methods have been proposed to detection and enumeration of attractors, there are no methods which have been demonstrated to be theoretically better than the naive method and be practically used for large biological BNs. Here, we present a novel method to calculate attractors based on a priori information, which works much and verifiably faster than the naive method. We apply the method to two BNs which differ in size, modeling formalism, and biological scope. Despite these differences, the method presented here provides a powerful tool for the analysis of both networks. First, our analysis of a BN studying the effect of the microenvironment during angiogenesis shows that the previously defined microenvironments inducing the specialized phalanx behavior in endothelial cells (ECs) additionally induce stalk behavior. We obtain this result from an extended network version which was previously not analyzed. Second, we were able to heuristically detect attractors in a cell cycle control network formalized as a bipartite Boolean model (bBM) with 3158 nodes. These attractors are directly interpretable in terms of genotype-to-phenotype relationships, allowing network validation equivalent to an in silico mutagenesis screen. Our approach contributes to the development of scalable analysis methods required for whole-cell modeling efforts.

Systems biology requires not only scalable formalization methods, but also means to analyze complex networks. Although Boolean networks (BNs) are a convenient way to formalize biological processes, their analysis suffers from the combinatorial complexity with increasing number of nodes n. Hence, the long standing O(2ⁿ) barrier for detection of periodic attractors in BNs has obstructed the development of large, biological BNs. We break this barrier by introducing a novel algorithm using a priori information. We show that the proposed algorithm enables systematic analysis of BNs formulated as bipartite models in the form of in silico mutagenesis screens.

Finite-Horizon Optimal Control of Boolean Control Networks: A Unified Graph-Theoretical Approach

This article investigates the finite-horizon optimal control (FHOC) problem of Boolean control networks (BCNs) from a graph theory perspective. We first formulate two general problems to unify various special cases studied in the literature: 1) the horizon length is a priori fixed and 2) the horizon length is unspecified but finite for given destination states. Notably, both problems can incorporate time-variant costs, which are rarely considered in existing work, and a variety of constraints. The existence of an optimal control sequence is analyzed under mild assumptions. Motivated by BCNs' finite state space and control space, we approach the two general problems intuitively and efficiently under a graph-theoretical framework. A weighted state transition graph and its time-expanded variants are developed, and the equivalence between the FHOC problem and the shortest-path (SP) problem in specific graphs is established rigorously. Two algorithms are developed to find the SP and construct the optimal control sequence for the two problems with reduced computational complexity, though technically, a classical SP algorithm in graph theory is sufficient for all problems. Compared with existing algebraic methods, our graph-theoretical approach can achieve state-of-the-art time efficiency while targeting the most general problems. Furthermore, our approach is the first one capable of solving Problem 2) with time-variant costs. Finally, a genetic network in the bacterium E. coli and a signaling network involved in human leukemia are used to validate the effectiveness of our approach. The results of two common tasks for both networks show that our approach can dramatically reduce the running time. Python implementation of our algorithms is available at GitHub https://github.com/ShuhuaGao/FHOC.

On Optimal Time-Varying Feedback Controllability for Probabilistic Boolean Control Networks

This brief studies controllability for probabilistic Boolean control network (PBCN) with time-varying feedback control laws. The concept of feedback controllability with an arbitrary probability for PBCNs is formulated first, and a control problem to maximize the probability of time-varying feedback controllability is investigated afterward. By introducing semitensor product (STP) technique, an equivalent multistage decision problem is deduced, and then a novel optimization algorithm is proposed to obtain the maximum probability of controllability and the corresponding optimal feedback law simultaneously. The advantages of the time-varying optimal controller obtained by the proposed algorithm, compared to the time-invariant one, are illustrated by numerical simulations.

Tractable Learning and Inference for Large-Scale Probabilistic Boolean Networks

Probabilistic Boolean networks (PBNs) have previously been proposed so as to gain insights into complex dynamical systems. However, identification of large networks and their underlying discrete Markov chain which describes their temporal evolution still remains a challenge. In this paper, we introduce an equivalent representation for PBNs, the stochastic conjunctive normal form network (SCNFN), which enables a scalable learning algorithm and helps predict long-run dynamic behavior of large-scale systems. State-of-the-art methods turn out to be 400 times slower for middle-sized networks (i.e., containing 100 nodes) and incapable of terminating for large networks (i.e., containing 1000 nodes) compared to the SCNFN-based learning, when attempting to achieve comparable accuracy. In addition, in contrast to the currently used methods which introduce strict restrictions on the structure of the learned PBNs, the hypothesis space of our training paradigm is the set of all possible PBNs. Moreover, SCNFNs enable efficient sampling so as to statistically infer multistep transition probabilities which can provide information on the activity levels of individual nodes in the long run. Extensive experimental results showcase the scalability of the proposed approach both in terms of sample and runtime complexity. In addition, we provide examples to study large and complex cell signaling networks to show the potential of our model. Finally, we suggest several directions for future research on model variations, theoretical analysis, and potential applications of SCNFNs.

Fast-Time Stability of Temporal Boolean Networks

In real systems, most of the biological functionalities come from the fact that the connections are not active all the time. Based on the fact, temporal Boolean networks (TBNs) are proposed in this paper, and the fast-time stability is analyzed via semi-tensor product (STP) of matrices and incidence matrices. First, the algebraic form of a TBN is obtained based on the STP method, and one necessary and sufficient condition for global fast-time stability is presented. Moreover, incidence matrices are used to obtain several sufficient conditions, which reduce the computational complexity from O(n2ⁿ) (exponential type) to O(n⁴) (polynomial type) compared with the STP method. In addition, the global fast-time stabilization of TBNs is considered, and pinning controllers are designed based on the neighbors of controlled nodes rather than all the nodes. Finally, the local fast-time stability of TBNs is considered based on the incidence matrices as well. Several examples are provided to illustrate the effectiveness of the obtained results.

Controlling large Boolean networks with single-step perturbations

Motivation

The control of Boolean networks has traditionally focussed on strategies where the perturbations are applied to the nodes of the network for an extended period of time. In this work, we study if and how a Boolean network can be controlled by perturbing a minimal set of nodes for a single-step and letting the system evolve afterwards according to its original dynamics. More precisely, given a Boolean network (BN), we compute a minimal subset Cmin of the nodes such that BN can be driven from any initial state in an attractor to another ‘desired’ attractor by perturbing some or all of the nodes of Cmin for a single-step. Such kind of control is attractive for biological systems because they are less time consuming than the traditional strategies for control while also being financially more viable. However, due to the phenomenon of state-space explosion, computing such a minimal subset is computationally inefficient and an approach that deals with the entire network in one-go, does not scale well for large networks.

Results

We develop a ‘divide-and-conquer’ approach by decomposing the network into smaller partitions, computing the minimal control on the projection of the attractors to these partitions and then composing the results to obtain Cmin for the whole network. We implement our method and test it on various real-life biological networks to demonstrate its applicability and efficiency.

Supplementary information

Supplementary data are available at Bioinformatics online.

On the number of driver nodes for controlling a Boolean network when the targets are restricted to attractors

It is known that many driver nodes are required to control complex biological networks. Previous studies imply that O(N) driver nodes are required in both linear complex network and Boolean network models with N nodes if an arbitrary state is specified as the target. In order to cope with this intrinsic difficulty, we consider a special case of the control problem in which the targets are restricted to attractors. For this special case, we mathematically prove under the uniform distribution of states in basins that the expected number of driver nodes is only O(log₂N+log₂M) for controlling Boolean networks, where M is the number of attractors. Since it is expected that M is not very large in many practical networks, the new model requires a much smaller number of driver nodes. This result is based on discovery of novel relationships between control problems on Boolean networks and the coupon collector's problem, a well-known concept in combinatorics. We also provide lower bounds of the number of driver nodes as well as simulation results using artificial and realistic network data, which support our theoretical findings.

Model Approximation for Switched Genetic Regulatory Networks

The model approximation problem is studied in this paper for switched genetic regulatory networks (GRNs) with time-varying delays. We focus on constructing a reduced-order model to approximate the high-order GRNs considered under the switching signal subject to certain constraints, such that the approximation error system between the original and reduced-order systems is exponentially stable with a disturbance attenuation performance. The stability conditions and the disturbance attenuation performance are established by utilizing two integral inequality bounding techniques and the average dwell-time method for the approximation error system. Then, the solvability conditions for the reduced-order models for the GRNs are also established using the projection method. Furthermore, the model approximation problem can be transferred into a sequential minimization problem that is subject to linear matrix inequality constraints by using the cone complementarity algorithm. Finally, several examples are provided to illustrate the effectiveness and the advantages of the proposed methods.