Model construction of Boolean network via observed data

Optimal Reconstruction of Probabilistic Boolean Networks

In gene regulatory networks (GRNs), it is important to model gene regulation based on a priori information and experimental data. As a useful mathematical model, probabilistic Boolean networks (PBNs) have been widely applied in GRNs. This article addresses the optimal reconstruction problem of PBNs based on several priori Boolean functions and sampled data. When all candidate Boolean functions are known in advance, the optimal reconstruction problem is reformulated into an optimization problem. This problem can be well solved by a recurrent neural network approach which decreases the computational cost. When parts of candidate Boolean functions are known in advance, necessary and sufficient conditions are provided for the reconstruction of PBNs. In this case, two types of reconstruction problems are further proposed: one is aimed at minimizing the number of reconstructed Boolean functions, and the other one is aimed at maximizing the selection probability of the main dynamics under noises. At last, examples in GRNs are elaborated to demonstrate the effectiveness of the main results.

Identification of Boolean control networks with time delay

This paper investigates the identification of time-delay Boolean networks (TBNs) and time-delay Boolean control networks (TBCNs) via Cheng product. According to all admissible (input-)output sequences, definition on identifiability of the (TBCN) TBN is given. Two algorithms are designed to select suitable delay parameters of the TBN and TBCN, respectively. Based on these, the original systems are divided into several subsystems. Then by virtue of observability, the criteria for identifiability of the TBN and TBCN are obtained. Moreover, the corresponding constructing processes are presented to establish the internal structures of the TBN and TBCN. Finally, two illustrative examples are given to show the feasibility of the proposed methods.

Boolean network sketches: a unifying framework for logical model inference

MOTIVATION

The problem of model inference is of fundamental importance to systems biology. Logical models (e.g. Boolean networks; BNs) represent a computationally attractive approach capable of handling large biological networks. The models are typically inferred from experimental data. However, even with a substantial amount of experimental data supported by some prior knowledge, existing inference methods often focus on a small sample of admissible candidate models only.

RESULTS

We propose Boolean network sketches as a new formal instrument for the inference of Boolean networks. A sketch integrates (typically partial) knowledge about the network's topology and the update logic (obtained through, e.g. a biological knowledge base or a literature search), as well as further assumptions about the properties of the network's transitions (e.g. the form of its attractor landscape), and additional restrictions on the model dynamics given by the measured experimental data. Our new BNs inference algorithm starts with an 'initial' sketch, which is extended by adding restrictions representing experimental data to a 'data-informed' sketch and subsequently computes all BNs consistent with the data-informed sketch. Our algorithm is based on a symbolic representation and coloured model-checking. Our approach is unique in its ability to cover a broad spectrum of knowledge and efficiently produce a compact representation of all inferred BNs. We evaluate the method on a non-trivial collection of real-world and simulated data.

AVAILABILITY AND IMPLEMENTATION

All software and data are freely available as a reproducible artefact at https://doi.org/10.5281/zenodo.7688740.

From data to QSP models: a pipeline for using Boolean networks for hypothesis inference and dynamic model building

Quantitative Systems Pharmacology (QSP) models capture the physiological underpinnings driving the response to a drug and express those in a semi-mechanistic way, often involving ordinary differential equations (ODEs). The process of developing a QSP model generally starts with the definition of a set of reasonable hypotheses that would support a mechanistic interpretation of the expected response which are used to form a network of interacting elements. This is a hypothesis-driven and knowledge-driven approach, relying on prior information about the structure of the network. However, with recent advances in our ability to generate large datasets rapidly, often in a hypothesis-neutral manner, the opportunity emerges to explore data-driven approaches to establish the network topologies and models in a robust, repeatable manner. In this paper, we explore the possibility of developing complex network representations of physiological responses to pharmaceuticals using a logic-based analysis of available data and then convert the logic relations to dynamic ODE-based models. We discuss an integrated pipeline for converting data to QSP models. This pipeline includes using k-means clustering to binarize continuous data, inferring likely network relationships using a Best-Fit Extension method to create a Boolean network, and finally converting the Boolean network to a continuous ODE model. We utilized an existing QSP model for the dual-affinity re-targeting antibody flotetuzumab to demonstrate the robustness of the process. Key output variables from the QSP model were used to generate a continuous data set for use in the pipeline. This dataset was used to reconstruct a possible model. This reconstruction had no false-positive relationships, and the output of each of the species was similar to that of the original QSP model. This demonstrates the ability to accurately infer relationships in a hypothesis-neutral manner without prior knowledge of a system using this pipeline.

Unsupervised logic-based mechanism inference for network-driven biological processes

Modern analytical techniques enable researchers to collect data about cellular states, before and after perturbations. These states can be characterized using analytical techniques, but the inference of regulatory interactions that explain and predict changes in these states remains a challenge. Here we present a generalizable, unsupervised approach to generate parameter-free, logic-based models of cellular processes, described by multiple discrete states. Our algorithm employs a Hamming-distance based approach to formulate, test, and identify optimized logic rules that link two states. Our approach comprises two steps. First, a model with no prior knowledge except for the mapping between initial and attractor states is built. We then employ biological constraints to improve model fidelity. Our algorithm automatically recovers the relevant dynamics for the explored models and recapitulates key aspects of the biochemical species concentration dynamics in the original model. We present the advantages and limitations of our work and discuss how our approach could be used to infer logic-based mechanisms of signaling, gene-regulatory, or other input-output processes describable by the Boolean formalism.

Boolean model of anchorage dependence and contact inhibition points to coordinated inhibition but semi-independent induction of proliferation and migration

Epithelial cells respond to their physical neighborhood with mechano-sensitive behaviors required for development and tissue maintenance. These include anchorage dependence, matrix stiffness-dependent proliferation, contact inhibition of proliferation and migration, and collective migration that balances cell crawling with the maintenance of cell junctions. While required for development and tissue repair, these coordinated responses to the microenvironment also contribute to cancer metastasis. Predictive models of the signaling networks that coordinate these behaviors are critical in controlling cell behavior to halt disease. Here we propose a Boolean regulatory network model that synthesizes mechanosensitive signaling that links anchorage to a matrix of varying stiffness and cell density sensing to contact inhibition, proliferation, migration, and apoptosis. Our model can reproduce anchorage dependence and anoikis, detachment-induced cytokinesis errors, the effect of matrix stiffness on proliferation, and contact inhibition of proliferation and migration by two mechanisms that converge on the YAP transcription factor. In addition, we offer testable predictions related to cell cycle-dependent anoikis sensitivity, the molecular requirements for abolishing contact inhibition, and substrate stiffness dependent expression of the catalytic subunit of PI3K. Moreover, our model predicts heterogeneity in migratory vs. non-migratory phenotypes in sub-confluent monolayers, and co-inhibition but semi-independent induction of proliferation vs. migration as a function of cell density and mitogenic stimulation. Our model serves as a stepping-stone towards modeling mechanosensitive routes to the epithelial to mesenchymal transition, capturing the effects of the mesenchymal state on anoikis resistance, and understanding the balance between migration versus proliferation at each stage of the epithelial to mesenchymal transition.

Identification of the Structure of a Probabilistic Boolean Network From Samples Including Frequencies of Outcomes

We study the problem of identifying the structure of a probabilistic Boolean network (PBN), a probabilistic model of biological networks, from a given set of samples. This problem can be regarded as an identification of a set of Boolean functions from samples. Existing studies on the identification of the structure of a PBN only use information on the occurrences of samples. In this paper, we also make use of the frequencies of occurrences of subtuples, information that is obtainable from the samples. We show that under this model, it is possible to identify a PBN from among a class of PBNs, for much broader classes of PBNs. In particular, we prove that, under a reasonable assumption, the structure of a PBN can be identified from among the class of PBNs that have at most three functions assigned to each node, but that identification may be impossible if four or more functions are assigned to each node. We also analyze the sample complexity for exactly identifying the structure of a PBN, and present an efficient algorithm for the identification of a PBN consisting of threshold functions from samples.

Observability of Boolean Control Networks Using Parallel Extension and Set Reachability

This brief reviews various definitions of observability for Boolean control networks (BCNs) and proposes a new one: output-feedback observability. This new definition applies to all BCNs whose initial states can be identified from the history of output measurements. A technique called parallel extension is then proposed to facilitate observability analysis. Furthermore, a technique called state transition graph reconstruction is proposed for analyzing the set reachability of BCNs, based on which new criteria for observability, single-input sequence observability, and arbitrary-input observability, are obtained. Using the proposed techniques, this brief proves that the problem of output-feedback observability can be recast as that of stabilizing a logic dynamical system with output feedback. Then, a necessary and sufficient condition for static output feedback observability is proposed. The relationships between the different definitions of observability are discussed, and the main results are illustrated with examples.

Identification of Boolean Network Models From Time Series Data Incorporating Prior Knowledge

Motivation: Mathematical models take an important place in science and engineering. A model can help scientists to explain dynamic behavior of a system and to understand the functionality of system components. Since length of a time series and number of replicates is limited by the cost of experiments, Boolean networks as a structurally simple and parameter-free logical model for gene regulatory networks have attracted interests of many scientists. In order to fit into the biological contexts and to lower the data requirements, biological prior knowledge is taken into consideration during the inference procedure. In the literature, the existing identification approaches can only deal with a subset of possible types of prior knowledge. Results: We propose a new approach to identify Boolean networks from time series data incorporating prior knowledge, such as partial network structure, canalizing property, positive and negative unateness. Using vector form of Boolean variables and applying a generalized matrix multiplication called the semi-tensor product (STP), each Boolean function can be equivalently converted into a matrix expression. Based on this, the identification problem is reformulated as an integer linear programming problem to reveal the system matrix of Boolean model in a computationally efficient way, whose dynamics are consistent with the important dynamics captured in the data. By using prior knowledge the number of candidate functions can be reduced during the inference. Hence, identification incorporating prior knowledge is especially suitable for the case of small size time series data and data without sufficient stimuli. The proposed approach is illustrated with the help of a biological model of the network of oxidative stress response. Conclusions: The combination of efficient reformulation of the identification problem with the possibility to incorporate various types of prior knowledge enables the application of computational model inference to systems with limited amount of time series data. The general applicability of this methodological approach makes it suitable for a variety of biological systems and of general interest for biological and medical research.

Identifying a Probabilistic Boolean Threshold Network From Samples

This paper studies the problem of exactly identifying the structure of a probabilistic Boolean network (PBN) from a given set of samples, where PBNs are probabilistic extensions of Boolean networks. Cheng et al. studied the problem while focusing on PBNs consisting of pairs of AND/OR functions. This paper considers PBNs consisting of Boolean threshold functions while focusing on those threshold functions that have unit coefficients. The treatment of Boolean threshold functions, and triplets and -tuplets of such functions, necessitates a deepening of the theoretical analyses. It is shown that wide classes of PBNs with such threshold functions can be exactly identified from samples under reasonable constraints, which include: 1) PBNs in which any number of threshold functions can be assigned provided that all have the same number of input variables and 2) PBNs consisting of pairs of threshold functions with different numbers of input variables. It is also shown that the problem of deciding the equivalence of two Boolean threshold functions is solvable in pseudopolynomial time but remains co-NP complete.

Observability of Automata Networks: Fixed and Switching Cases

Automata networks are a class of fully discrete dynamical systems, which have received considerable interest in various different areas. This brief addresses the observability of automata networks and switched automata networks in a unified framework, and proposes simple necessary and sufficient conditions for observability. The results are achieved by employing methods from symbolic computation, and are suited for implementation using computer algebra systems. Several examples are presented to demonstrate the application of the results.

ATLANTIS - Attractor Landscape Analysis Toolbox for Cell Fate Discovery and Reprogramming

Boolean modelling of biological networks is a well-established technique for abstracting dynamical biomolecular regulation in cells. Specifically, decoding linkages between salient regulatory network states and corresponding cell fate outcomes can help uncover pathological foundations of diseases such as cancer. Attractor landscape analysis is one such methodology which converts complex network behavior into a landscape of network states wherein each state is represented by propensity of its occurrence. Towards undertaking attractor landscape analysis of Boolean networks, we propose an Attractor Landscape Analysis Toolbox (ATLANTIS) for cell fate discovery, from biomolecular networks, and reprogramming upon network perturbation. ATLANTIS can be employed to perform both deterministic and probabilistic analyses. It has been validated by successfully reconstructing attractor landscapes from several published case studies followed by reprogramming of cell fates upon therapeutic treatment of network. Additionally, the biomolecular network of HCT-116 colorectal cancer cell line has been screened for therapeutic evaluation of drug-targets. Our results show agreement between therapeutic efficacies reported by ATLANTIS and the published literature. These case studies sufficiently highlight the in silico cell fate prediction and therapeutic screening potential of the toolbox. Lastly, ATLANTIS can also help guide single or combinatorial therapy responses towards reprogramming biomolecular networks to recover cell fates.

Characterization of Linearly Separable Boolean Functions: A Graph-Theoretic Perspective

In this paper, we present a novel approach for studying Boolean function in a graph-theoretic perspective. In particular, we first transform a Boolean function f of n variables into an induced subgraph H_f of the n -dimensional hypercube, and then, we show the properties of linearly separable Boolean functions on the basis of the analysis of the structure of H_f . We define a new class of graphs, called hyperstar, and prove that the induced subgraph H_f of any linearly separable Boolean function f is a hyperstar. The proposal of hyperstar helps us uncover a number of fundamental properties of linearly separable Boolean functions in this paper.

Identification of Boolean Networks Using Premined Network Topology Information

This brief aims to reduce the data requirement for the identification of Boolean networks (BNs) by using the premined network topology information. First, a matching table is created and used for sifting the true from the false dependences among the nodes in the BNs. Then, a dynamic extension to matching table is developed to enable the dynamic locating of matching pairs to start as soon as possible. Next, based on the pseudocommutative property of the semitensor product, a position-transform mining is carried out to further improve data utilization. Combining the above, the topology of the BNs can be premined for the subsequent identification. Examples are given to illustrate the efficiency of reducing the data requirement. Some excellent features, such as the online and parallel processing ability, are also demonstrated.

Control of Large-Scale Boolean Networks via Network Aggregation

A major challenge to solve problems in control of Boolean networks is that the computational cost increases exponentially when the number of nodes in the network increases. We consider the problem of controllability and stabilizability of Boolean control networks, address the increasing cost problem by partitioning the network graph into several subnetworks, and analyze the subnetworks separately. Easily verifiable necessary conditions for controllability and stabilizability are proposed for a general aggregation structure. For acyclic aggregation, we develop a sufficient condition for stabilizability. It dramatically reduces the computational complexity if the number of nodes in each block of the acyclic aggregation is small enough compared with the number of nodes in the entire Boolean network.

Data identification for improving gene network inference using computational algebra

Identification of models of gene regulatory networks is sensitive to the amount of data used as input. Considering the substantial costs in conducting experiments, it is of value to have an estimate of the amount of data required to infer the network structure. To minimize wasted resources, it is also beneficial to know which data are necessary to identify the network. Knowledge of the data and knowledge of the terms in polynomial models are often required a priori in model identification. In applications, it is unlikely that the structure of a polynomial model will be known, which may force data sets to be unnecessarily large in order to identify a model. Furthermore, none of the known results provides any strategy for constructing data sets to uniquely identify a model. We provide a specialization of an existing criterion for deciding when a set of data points identifies a minimal polynomial model when its monomial terms have been specified. Then, we relax the requirement of the knowledge of the monomials and present results for model identification given only the data. Finally, we present a method for constructing data sets that identify minimal polynomial models.

Construction of a Boolean model of gene and protein regulatory network with memory

A Boolean model of gene and protein regulatory network with memory (GPBN) has recently attracted interest as a generalization of original random Boolean networks (BNs) for genetic and cellular networks. It is better suited to describe experimental data from the time-course microarray. Addressing construction problems in GPBNs may lead to a better understanding of the intrinsic dynamics in biological systems. Using the technique of the semi-tensor product (STP) of matrices, the dynamics of a GPBN can be expressed in an algebraic form and the attractors can be calculated. This paper investigates the issue of construction of GPBNs from prescribed attractors. Based on a rigorous theoretical analysis, some algebraic formulae and a computationally feasible algorithm are obtained to construct the least in-degree model with prescribed attractors. Illustrative examples are presented to show the validity of the theoretical results and the proposed algorithm.

Synchronization design of Boolean networks via the semi-tensor product method

We provide a general approach for the design of a response Boolean network (BN) to achieve complete synchronization with a given drive BN. The approach is based on the algebraic representation of BNs in terms of the semi-tensor product of matrices. Instead of designing the logical dynamic equations of a response BN directly, we first construct its algebraic representation and then convert the algebraic representation back to the logical form. The results are applied to a three-neuron network in order to illustrate the effectiveness of the proposed approach.

Complete synchronization of Boolean networks

We examine complete synchronization of two deterministic Boolean networks (BNs) coupled unidirectionally in the drive-response configuration. A necessary and sufficient criterion is presented in terms of algebraic representations of BNs. As a consequence, we show that complete synchronization can occur only between two conditionally identical BNs when the transition matrix of the drive network is nonsingular. Two examples are worked out to illustrate the obtained results.