An effective network reduction approach to find the dynamical repertoire of discrete dynamic networks

Evaluating changes in attractor sets under small network perturbations to infer reliable microbial interaction networks from abundance patterns

MOTIVATION

Inferring microbial interaction networks from microbiome data is a core task of computational ecology. An avenue of research to create reliable inference methods is based on a stylized view of microbiome data, starting from the assumption that the presences and absences of microbiomes, rather than the quantitative abundances, are informative about the underlying interaction network. With this starting point, inference algorithms can be based on the notion of attractors (asymptotic states) in Boolean networks. Boolean network framework offers a computationally efficient method to tackle this problem. However, often existing algorithms operating under a Boolean network assumption, fail to provide networks that can reproduce the complete set of initial attractors (abundance patterns). Therefore, there is a need for network inference algorithms capable of reproducing the initial stable states of the system.

RESULTS

We study the change of attractors in Boolean threshold dynamics on signed undirected graphs under small changes in network architecture and show, how to leverage these relationships to enhance network inference algorithms. As an illustration of this algorithmic approach, we analyse microbial abundance patterns from stool samples of humans with inflammatory bowel disease (IBD), with colorectal cancer and from healthy individuals to study differences between the interaction networks of the three conditions. The method reveals strong diversity in IBD interaction networks. The networks are first partially deduced by an earlier inference method called ESABO, then we apply the new algorithm developed here, EDAME, to this result to generate a network that comes nearest to satisfying the original attractors.

AVAILABILITY AND IMPLEMENTATION

Implementation code is freely available at https://github.com/Jojo6297/edame.git.

Canalizing kernel for cell fate determination

The tendency for cell fate to be robust to most perturbations, yet sensitive to certain perturbations raises intriguing questions about the existence of a key path within the underlying molecular network that critically determines distinct cell fates. Reprogramming and trans-differentiation clearly show examples of cell fate change by regulating only a few or even a single molecular switch. However, it is still unknown how to identify such a switch, called a master regulator, and how cell fate is determined by its regulation. Here, we present CAESAR, a computational framework that can systematically identify master regulators and unravel the resulting canalizing kernel, a key substructure of interconnected feedbacks that is critical for cell fate determination. We demonstrate that CAESAR can successfully predict reprogramming factors for de-differentiation into mouse embryonic stem cells and trans-differentiation of hematopoietic stem cells, while unveiling the underlying essential mechanism through the canalizing kernel. CAESAR provides a system-level understanding of how complex molecular networks determine cell fates.

A network-based modeling framework reveals the core signal transduction network underlying high carbon dioxide-induced stomatal closure in guard cells

Stomata are pores on plant aerial surfaces, each bordered by a pair of guard cells. They control gas exchange vital for plant survival. Understanding how guard cells respond to environmental signals such as atmospheric carbon dioxide (CO2) levels is not only insightful to fundamental biology but also relevant to real-world issues of crop productivity under global climate change. In the past decade, multiple important signaling elements for stomatal closure induced by elevated CO2 have been identified. Yet, there is no comprehensive understanding of high CO2-induced stomatal closure. In this work, we assemble a cellular signaling network underlying high CO2-induced stomatal closure by integrating evidence from a comprehensive literature analysis. We further construct a Boolean dynamic model of the network, which allows in silico simulation of the stomatal closure response to high CO2 in wild-type Arabidopsis thaliana plants and in cases of pharmacological or genetic manipulation of network nodes. Our model has a 91% accuracy in capturing known experimental observations. We perform network-based logical analysis and reveal a feedback core of the network, which dictates cellular decisions in closure response to high CO2. Based on these analyses, we predict and experimentally confirm that applying nitric oxide (NO) induces stomatal closure in ambient CO2 and causes hypersensitivity to elevated CO2. Moreover, we predict a negative regulatory relationship between NO and the protein phosphatase ABI2 and find experimentally that NO inhibits ABI2 phosphatase activity. The experimental validation of these model predictions demonstrates the effectiveness of network-based modeling and highlights the decision-making role of the feedback core of the network in signal transduction. We further explore the model's potential in predicting targets of signaling elements not yet connected to the CO2 network. Our combination of network science, in silico model simulation, and experimental assays demonstrates an effective interdisciplinary approach to understanding system-level biology.

Biologically meaningful regulatory logic enhances the convergence rate in Boolean networks and bushiness of their state transition graph

Boolean models of gene regulatory networks (GRNs) have gained widespread traction as they can easily recapitulate cellular phenotypes via their attractor states. Their overall dynamics are embodied in a state transition graph (STG). Indeed, two Boolean networks (BNs) with the same network structure and attractors can have drastically different STGs depending on the type of Boolean functions (BFs) employed. Our objective here is to systematically delineate the effects of different classes of BFs on the structural features of the STG of reconstructed Boolean GRNs while keeping network structure and biological attractors fixed, and explore the characteristics of BFs that drive those features. Using $10$ reconstructed Boolean GRNs, we generate ensembles that differ in BFs and compute from their STGs the dynamics' rate of contraction or 'bushiness' and rate of 'convergence', quantified with measures inspired from cellular automata (CA) that are based on the garden-of-Eden (GoE) states. We find that biologically meaningful BFs lead to higher STG 'bushiness' and 'convergence' than random ones. Obtaining such 'global' measures gets computationally expensive with larger network sizes, stressing the need for feasible proxies. So we adapt Wuensche's $Z$-parameter in CA to BFs in BNs and provide four natural variants, which, along with the average sensitivity of BFs computed at the network level, comprise our descriptors of local dynamics and we find some of them to be good proxies for bushiness. Finally, we provide an excellent proxy for the 'convergence' based on computing transient lengths originating at random states rather than GoE states.

Breaking reflection symmetry: evolving long dynamical cycles in Boolean systems

In interacting dynamical systems, specific local interaction rules for system components give rise to diverse and complex global dynamics. Long dynamical cycles are a key feature of many natural interacting systems, especially in biology. Examples of dynamical cycles range from circadian rhythms regulating sleep to cell cycles regulating reproductive behavior. Despite the crucial role of cycles in nature, the properties of network structure that give rise to cycles still need to be better understood. Here, we use a Boolean interaction network model to study the relationships between network structure and cyclic dynamics. We identify particular structural motifs that support cycles, and other motifs that suppress them. More generally, we show that the presence of dynamical reflection symmetry in the interaction network enhances cyclic behavior. In simulating an artificial evolutionary process, we find that motifs that break reflection symmetry are discarded. We further show that dynamical reflection symmetries are over-represented in Boolean models of natural biological systems. Altogether, our results demonstrate a link between symmetry and functionality for interacting dynamical systems, and they provide evidence for symmetry's causal role in evolving dynamical functionality.

Models of Cell Processes are Far from the Edge of Chaos

Complex living systems are thought to exist at the "edge of chaos" separating the ordered dynamics of robust function from the disordered dynamics of rapid environmental adaptation. Here, a deeper inspection of 72 experimentally supported discrete dynamical models of cell processes reveals previously unobserved order on long time scales, suggesting greater rigidity in these systems than was previously conjectured. We find that propagation of internal perturbations is transient in most cases, and that even when large perturbation cascades persist, their phenotypic effects are often minimal. Moreover, we find evidence that stochasticity and desynchronization can lead to increased recovery from regulatory perturbation cascades. Our analysis relies on new measures that quantify the tendency of perturbations to spread through a discrete dynamical system. Computing these measures was not feasible using current methodology; thus, we developed a multipurpose CUDA-based simulation tool, which we have made available as the open-source Python library cubewalkers. Based on novel measures and simulations, our results suggest that-contrary to current theory-cell processes are ordered and far from the edge of chaos.

Phenotype Control techniques for Boolean gene regulatory networks

Modeling cell signal transduction pathways via Boolean networks (BNs) has become an established method for analyzing intracellular communications over the last few decades. What's more, BNs provide a course-grained approach, not only to understanding molecular communications, but also for targeting pathway components that alter the long-term outcomes of the system. This has come to be known as phenotype control theory. In this review we study the interplay of various approaches for controlling gene regulatory networks such as: algebraic methods, control kernel, feedback vertex set, and stable motifs. The study will also include comparative discussion between the methods, using an established cancer model of T-Cell Large Granular Lymphocyte Leukemia. Further, we explore possible options for making the control search more efficient using reduction and modularity. Finally, we will include challenges presented such as the complexity and the availability of software for implementing each of these control techniques.

Hybrid computational modeling highlights reverse warburg effect in breast cancer-associated fibroblasts

Cancer-associated fibroblasts (CAFs) are amongst the key players of the tumor microenvironment (TME) and are involved in cancer initiation, progression, and resistance to therapy. They exhibit aggressive phenotypes affecting extracellular matrix remodeling, angiogenesis, immune system modulation, tumor growth, and proliferation. CAFs phenotypic changes appear to be associated with metabolic alterations, notably a reverse Warburg effect that may drive fibroblasts transformation. However, its precise molecular mechanisms and regulatory drivers are still under investigation. Deciphering the reverse Warburg effect in breast CAFs may contribute to a better understanding of the interplay between TME and tumor cells, leading to new treatment strategies. In this regard, dynamic modeling approaches able to span multiple biological layers are essential to capture the emergent properties of various biological entities when complex and intertwined pathways are involved. This work presents the first hybrid large-scale computational model for breast CAFs covering major cellular signaling, gene regulation, and metabolic processes. It was generated by combining a cell- and disease-specific asynchronous Boolean model with a generic core metabolic network leveraging both data-driven and manual curation approaches. This model reproduces the experimentally observed reverse Warburg effect in breast CAFs and further identifies Hypoxia-Inducible Factor 1 (HIF-1) as its key molecular driver. Targeting HIF-1 as part of a TME-centered therapeutic strategy may prove beneficial in the treatment of breast cancer by addressing the reverse Warburg effect. Such findings in CAFs, in light of our previously published results in rheumatoid arthritis synovial fibroblasts, point to a common HIF-1-driven metabolic reprogramming of fibroblasts in breast cancer and rheumatoid arthritis.

A large-scale Boolean model of the rheumatoid arthritis fibroblast-like synoviocytes predicts drug synergies in the arthritic joint

Rheumatoid arthritis (RA) is a complex autoimmune disease with an unknown aetiology. However, rheumatoid arthritis fibroblast-like synoviocytes (RA-FLS) play a significant role in initiating and perpetuating destructive joint inflammation by expressing immuno-modulating cytokines, adhesion molecules, and matrix remodelling enzymes. In addition, RA-FLS are primary drivers of inflammation, displaying high proliferative rates and an apoptosis-resistant phenotype. Thus, RA-FLS-directed therapies could become a complementary approach to immune-directed therapies by predicting the optimal conditions that would favour RA-FLS apoptosis, limit inflammation, slow the proliferation rate and minimise bone erosion and cartilage destruction. In this paper, we present a large-scale Boolean model for RA-FLS that consists of five submodels focusing on apoptosis, cell proliferation, matrix degradation, bone erosion and inflammation. The five-phenotype-specific submodels can be simulated independently or as a global model. In silico simulations and perturbations reproduced the expected biological behaviour of the system under defined initial conditions and input values. The model was then used to mimic the effect of mono or combined therapeutic treatments and predict novel targets and drug candidates through drug repurposing analysis.

Reducing Boolean networks with backward equivalence

BACKGROUND

Boolean Networks (BNs) are a popular dynamical model in biology where the state of each component is represented by a variable taking binary values that express, for instance, activation/deactivation or high/low concentrations. Unfortunately, these models suffer from the state space explosion, i.e., there are exponentially many states in the number of BN variables, which hampers their analysis.

RESULTS

We present Boolean Backward Equivalence (BBE), a novel reduction technique for BNs which collapses system variables that, if initialized with same value, maintain matching values in all states. A large-scale validation on 86 models from two online model repositories reveals that BBE is effective, since it is able to reduce more than 90% of the models. Furthermore, on such models we also show that BBE brings notable analysis speed-ups, both in terms of state space generation and steady-state analysis. In several cases, BBE allowed the analysis of models that were originally intractable due to the complexity. On two selected case studies, we show how one can tune the reduction power of BBE using model-specific information to preserve all dynamics of interest, and selectively exclude behavior that does not have biological relevance.

CONCLUSIONS

BBE complements existing reduction methods, preserving properties that other reduction methods fail to reproduce, and vice versa. BBE drops all and only the dynamics, including attractors, originating from states where BBE-equivalent variables have been initialized with different activation values The remaining part of the dynamics is preserved exactly, including the length of the preserved attractors, and their reachability from given initial conditions, without adding any spurious behaviours. Given that BBE is a model-to-model reduction technique, it can be combined with further reduction methods for BNs.

Statistical control of structural networks with limited interventions to minimize cellular phenotypic diversity represented by point attractors

The underlying genetic networks of cells give rise to diverse behaviors known as phenotypes. Control of this cellular phenotypic diversity (CPD) may reveal key targets that govern differentiation during development or drug resistance in cancer. This work establishes an approach to control CPD that encompasses practical constraints, including model limitations, the number of simultaneous control targets, which targets are viable for control, and the granularity of control. Cellular networks are often limited to the structure of interactions, due to the practical difficulty of modeling interaction dynamics. However, these dynamics are essential to CPD. In response, our statistical control approach infers the CPD directly from the structure of a network, by considering an ensemble average function over all possible Boolean dynamics for each node in the network. These ensemble average functions are combined with an acyclic form of the network to infer the number of point attractors. Our approach is applied to several known biological models and shown to outperform existing approaches. Statistical control of CPD offers a new avenue to contend with systemic processes such as differentiation and cancer, despite practical limitations in the field.

Phenotype control techniques for Boolean gene regulatory networks

Modeling cell signal transduction pathways via Boolean networks (BNs) has become an established method for analyzing intracellular communications over the last few decades. What’s more, BNs provide a course-grained approach, not only to understanding molecular communications, but also for targeting pathway components that alter the long-term outcomes of the system. This has come to be known as phenotype control theory . In this review we study the interplay of various approaches for controlling gene regulatory networks such as: algebraic methods, control kernel, feedback vertex set, and stable motifs. The study will also include comparative discussion between the methods, using an established cancer model of T-Cell Large Granular Lymphocyte (T-LGL) Leukemia. Further, we explore possible options for making the control search more efficient using reduction and modularity. Finally, we will include challenges presented such as the complexity and the availability of software for implementing each of these control techniques.

Dauer fate in a Caenorhabditis elegans Boolean network model

Cellular fates are determined by genes interacting across large, complex biological networks. A critical question is how to identify causal relationships spanning distinct signaling pathways and underlying organismal phenotypes. Here, we address this question by constructing a Boolean model of a well-studied developmental network and analyzing information flows through the system. Depending on environmental signals Caenorhabditis elegans develop normally to sexual maturity or enter a reproductively delayed, developmentally quiescent 'dauer' state, progressing to maturity when the environment changes. The developmental network that starts with environmental signal and ends in the dauer/no dauer fate involves genes across 4 signaling pathways including cyclic GMP, Insulin/IGF-1, TGF-β and steroid hormone synthesis. We identified three stable motifs leading to normal development, each composed of genes interacting across the Insulin/IGF-1, TGF-β and steroid hormone synthesis pathways. Three genes known to influence dauer fate, daf-2, daf-7 and hsf-1, acted as driver nodes in the system. Using causal logic analysis, we identified a five gene cyclic subgraph integrating the information flow from environmental signal to dauer fate. Perturbation analysis showed that a multifactorial insulin profile determined the stable motifs the system entered and interacted with daf-12 as the switchpoint driving the dauer/no dauer fate. Our results show that complex organismal systems can be distilled into abstract representations that permit full characterization of the causal relationships driving developmental fates. Analyzing organismal systems from this perspective of logic and function has important implications for studies examining the evolution and conservation of signaling pathways.

Predicting cascading extinctions and efficient restoration strategies in plant-pollinator networks via generalized positive feedback loops

The extinction of a species in a plant-pollinator mutualistic community can cause cascading effects and lead to major biodiversity loss. The ecologically important task of predicting the severity of the cascading effects is made challenging by the complex network of interactions among the species. In this work, we analyze an ensemble of models of communities of plant and pollinator species. These models describe the mutualistic inter-species interactions by Boolean threshold functions. We show that identifying generalized positive feedback loops can help pinpoint the species whose extinction leads to catastrophic and substantial damage to the whole community. We compare these results with the damage percentage caused by the loss of species identified as important by previously studied structural measures and show that positive feedback loops and the information gained from them can identify certain crucial species that the other measures fail to find. We also suggest mitigation measures for two specific purposes: (1) prevent the damage to the community by protecting a subset of the species, and (2) restore the community after the damage by restoring a subset of species. Our analyses indicate that the generalized positive feedback loops predict the most efficient strategies to achieve these purposes. The correct identification of species in each category has important implications for conservation efforts and developing community management strategies.

Metabolic reprogramming in Rheumatoid Arthritis Synovial Fibroblasts: A hybrid modeling approach

Rheumatoid Arthritis (RA) is an autoimmune disease characterized by a highly invasive pannus formation consisting mainly of Synovial Fibroblasts (RASFs). This pannus leads to cartilage, bone, and soft tissue destruction in the affected joint. RASFs' activation is associated with metabolic alterations resulting from dysregulation of extracellular signals' transduction and gene regulation. Deciphering the intricate mechanisms at the origin of this metabolic reprogramming may provide significant insight into RASFs' involvement in RA's pathogenesis and offer new therapeutic strategies. Qualitative and quantitative dynamic modeling can address some of these features, but hybrid models represent a real asset in their ability to span multiple layers of biological machinery. This work presents the first hybrid RASF model: the combination of a cell-specific qualitative regulatory network with a global metabolic network. The automated framework for hybrid modeling exploits the regulatory network's trap-spaces as additional constraints on the metabolic network. Subsequent flux balance analysis allows assessment of RASFs' regulatory outcomes' impact on their metabolic flux distribution. The hybrid RASF model reproduces the experimentally observed metabolic reprogramming induced by signaling and gene regulation in RASFs. Simulations also enable further hypotheses on the potential reverse Warburg effect in RA. RASFs may undergo metabolic reprogramming to turn into "metabolic factories", producing high levels of energy-rich fuels and nutrients for neighboring demanding cells through the crucial role of HIF1.

Relative importance of composition structures and biologically meaningful logics in bipartite Boolean models of gene regulation

Boolean networks have been widely used to model gene networks. However, such models are coarse-grained to an extent that they abstract away molecular specificities of gene regulation. Alternatively, bipartite Boolean network models of gene regulation explicitly distinguish genes from transcription factors (TFs). In such bipartite models, multiple TFs may simultaneously contribute to gene regulation by forming heteromeric complexes, thus giving rise to composition structures. Since bipartite Boolean models are relatively recent, an empirical investigation of their biological plausibility is lacking. Here, we estimate the prevalence of composition structures arising through heteromeric complexes. Moreover, we present an additional mechanism where composition structures may arise as a result of multiple TFs binding to cis-regulatory regions and provide empirical support for this mechanism. Next, we compare the restriction in BFs imposed by composition structures and by biologically meaningful properties. We find that though composition structures can severely restrict the number of Boolean functions (BFs) driving a gene, the two types of minimally complex BFs, namely nested canalyzing functions (NCFs) and read-once functions (RoFs), are comparatively more restrictive. Finally, we find that composition structures are highly enriched in real networks, but this enrichment most likely comes from NCFs and RoFs.

Landscape of epithelial-mesenchymal plasticity as an emergent property of coordinated teams in regulatory networks

Elucidating the design principles of regulatory networks driving cellular decision-making has fundamental implications in mapping and eventually controlling cell-fate decisions. Despite being complex, these regulatory networks often only give rise to a few phenotypes. Previously, we identified two 'teams' of nodes in a small cell lung cancer regulatory network that constrained the phenotypic repertoire and aligned strongly with the dominant phenotypes obtained from network simulations (Chauhan et al., 2021). However, it remained elusive whether these 'teams' exist in other networks, and how do they shape the phenotypic landscape. Here, we demonstrate that five different networks of varying sizes governing epithelial-mesenchymal plasticity comprised of two 'teams' of players - one comprised of canonical drivers of epithelial phenotype and the other containing the mesenchymal inducers. These 'teams' are specific to the topology of these regulatory networks and orchestrate a bimodal phenotypic landscape with the epithelial and mesenchymal phenotypes being more frequent and dynamically robust to perturbations, relative to the intermediary/hybrid epithelial/mesenchymal ones. Our analysis reveals that network topology alone can contain information about corresponding phenotypic distributions, thus obviating the need to simulate them. We propose 'teams' of nodes as a network design principle that can drive cell-fate canalization in diverse decision-making processes.

Probabilistic edge weights fine-tune Boolean network dynamics

Biological systems are noisy by nature. This aspect is reflected in our experimental measurements and should be reflected in the models we build to better understand these systems. Noise can be especially consequential when trying to interpret specific regulatory interactions, i.e. regulatory network edges. In this paper, we propose a method to explicitly encode edge-noise in Boolean dynamical systems by probabilistic edge-weight (PEW) operators. PEW operators have two important features: first, they introduce a form of edge-weight into Boolean models through the noise, second, the noise is dependent on the dynamical state of the system, which enables more biologically meaningful modeling choices. Moreover, we offer a simple-to-use implementation in the already well-established BooleanNet framework. In two application cases, we show how the introduction of just a few PEW operators in Boolean models can fine-tune the emergent dynamics and increase the accuracy of qualitative predictions. This includes fine-tuning interactions which cause non-biological behaviors when switching between asynchronous and synchronous update schemes in dynamical simulations. Moreover, PEW operators also open the way to encode more exotic cellular dynamics, such as cellular learning, and to implementing edge-weights for regulatory networks inferred from omics data.

Leveraging network structure in nonlinear control

Over the last twenty years, dynamic modeling of biomolecular networks has exploded in popularity. Many of the classical tools for understanding dynamical systems are unwieldy in the highly nonlinear, poorly constrained, high-dimensional systems that often arise from these modeling efforts. Understanding complex biological systems is greatly facilitated by purpose-built methods that leverage common features of such models, such as local monotonicity, interaction graph sparsity, and sigmoidal kinetics. Here, we review methods for controlling the systems of ordinary differential equations used to model biomolecular networks. We focus on methods that make use of the structure of the network of interactions to help inform, which variables to target for control, and highlight the computational and experimental advantages of such approaches. We also discuss the importance of nonperturbative methods in biomedical and experimental molecular biology applications, where finely tuned interventions can be difficult to implement. It is well known that feedback loops, and positive feedback loops in particular, play a major determining role in the dynamics of biomolecular networks. In many of the methods we cover here, control over system trajectories is realized by overriding the behavior of key feedback loops.

A probabilistic Boolean model on hair follicle cell fate regulation by TGF-β

Hair follicles (HFs) are mini skin organs that undergo cyclic growth. Various signals regulate HF cell fate decisions jointly. Recent experimental results suggest that transforming growth factor beta (TGF-β) exhibits a dual role in HF cell fate regulation that can be either anti- or pro-apoptosis. To understand the underlying mechanisms of HF cell fate control, we develop a novel probabilistic Boolean network (pBN) model on the HF epithelial cell gene regulation dynamics. First, the model is derived from literature, then refined using single-cell RNA sequencing data. Using the model, we both explore the mechanisms underlying HF cell fate decisions and make predictions that could potentially guide future experiments: 1) we propose that a threshold-like switch in the TGF-β strength may necessitate the dual roles of TGF-β in either activating apoptosis or cell proliferation, in cooperation with bone morphogenetic protein (BMP) and tumor necrosis factor (TNF) and at different stages of a follicle growth cycle; 2) our model shows concordance with the high-activator-low-inhibitor theory of anagen initiation; 3) we predict that TNF may be more effective in catagen initiation than TGF-β, and they may cooperate in a two-step fashion; 4) finally, predictions of gene knockout and overexpression reveal the roles in HF cell fate regulations of each gene. Attractor and motif analysis from the associated Boolean networks reveal the relations between the topological structure of the gene regulation network and the cell fate regulation mechanism. A discrete spatial model equipped with the pBN illustrates how TGF-β and TNF cooperate in initiating and driving the apoptosis wave during catagen.

Influence maximization in Boolean networks

The optimization problem aiming at the identification of minimal sets of nodes able to drive the dynamics of Boolean networks toward desired long-term behaviors is central for some applications, as for example the detection of key therapeutic targets to control pathways in models of biological signaling and regulatory networks. Here, we develop a method to solve such an optimization problem taking inspiration from the well-studied problem of influence maximization for spreading processes in social networks. We validate the method on small gene regulatory networks whose dynamical landscapes are known by means of brute-force analysis. We then systematically study a large collection of gene regulatory networks. We find that for about 65% of the analyzed networks, the minimal driver sets contain less than 20% of their nodes.

Translocating proteins compartment-specifically alter the fate of epithelial-mesenchymal transition in a compartmentalized Boolean network model

Regulation of translocating proteins is crucial in defining cellular behaviour. Epithelial-mesenchymal transition (EMT) is important in cellular processes, such as cancer progression. Several orchestrators of EMT, such as key transcription factors, are known to translocate. We show that translocating proteins become enriched in EMT-signalling. To simulate the compartment-specific functions of translocating proteins we created a compartmentalized Boolean network model. This model successfully reproduced known biological traits of EMT and as a novel feature it also captured organelle-specific functions of proteins. Our results predicted that glycogen synthase kinase-3 beta (GSK3B) compartment-specifically alters the fate of EMT, amongst others the activation of nuclear GSK3B halts transforming growth factor beta-1 (TGFB) induced EMT. Moreover, our results recapitulated that the nuclear activation of glioma associated oncogene transcription factors (GLI) is needed to achieve a complete EMT. Compartmentalized network models will be useful to uncover novel control mechanisms of biological processes. Our algorithmic procedures can be automatically rerun on the https://translocaboole.linkgroup.hu website, which provides a framework for similar future studies.

Structure-based approach to identifying small sets of driver nodes in biological networks

In network control theory, driving all the nodes in the Feedback Vertex Set (FVS) by node-state override forces the network into one of its attractors (long-term dynamic behaviors). The FVS is often composed of more nodes than can be realistically manipulated in a system; for example, only up to three nodes can be controlled in intracellular networks, while their FVS may contain more than 10 nodes. Thus, we developed an approach to rank subsets of the FVS on Boolean models of intracellular networks using topological, dynamics-independent measures. We investigated the use of seven topological prediction measures sorted into three categories-centrality measures, propagation measures, and cycle-based measures. Using each measure, every subset was ranked and then evaluated against two dynamics-based metrics that measure the ability of interventions to drive the system toward or away from its attractors: To Control and Away Control. After examining an array of biological networks, we found that the FVS subsets that ranked in the top according to the propagation metrics can most effectively control the network. This result was independently corroborated on a second array of different Boolean models of biological networks. Consequently, overriding the entire FVS is not required to drive a biological network to one of its attractors, and this method provides a way to reliably identify effective FVS subsets without the knowledge of the network dynamics.

pystablemotifs: Python library for attractor identification and control in Boolean networks

SUMMARY

pystablemotifs is a Python 3 library for analyzing Boolean networks. Its non-heuristic and exhaustive attractor identification algorithm was previously presented in Rozum et al. (2021). Here, we illustrate its performance improvements over similar methods and discuss how it uses outputs of the attractor identification process to drive a system to one of its attractors from any initial state. We implement six attractor control algorithms, five of which are new in this work. By design, these algorithms can return different control strategies, allowing for synergistic use. We also give a brief overview of the other tools implemented in pystablemotifs.

AVAILABILITY AND IMPLEMENTATION

The source code is on GitHub at https://github.com/jcrozum/pystablemotifs/.

SUPPLEMENTARY INFORMATION

Supplementary data are available at Bioinformatics online.

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.

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.

Relationships among generalized positive feedback loops determine possible community outcomes in plant-pollinator interaction networks

Attractors in Boolean network models representing complex systems such as ecological communities correspond to long-term outcomes (e.g., stable communities) in such systems. As a result, identifying efficient methods to find and characterize these attractors allows for a better understanding of the diversity of possible outcomes. Here we analyze networks that model mutualistic communities of plant and pollinator species governed by Boolean threshold functions. We propose a novel attractor identification method based on generalized positive feedback loops and their functional relationships in such networks. We show that these relationships determine the mechanisms by which groups of stable positive feedback loops collectively trap the system in specific regions of the state space and lead to attractors. Put into the ecological context, we show how survival units-small groups of species in which species can maintain a specific survival state-and their relationships determine the final community outcomes in plant-pollinator networks. We find a remarkable diversity of community outcomes: up to an average of 43 attractors possible for networks with 100 species. This diversity is due to the multiplicity of survival units (up to 34) and stable subcommunities (up to 14). The timing of species influx or outflux does not affect the number of attractors, but it may influence their basins of attraction.

Modeling the Pancreatic Cancer Microenvironment in Search of Control Targets

Pancreatic ductal adenocarcinoma is among the leading causes of cancer-related deaths globally due to its extreme difficulty to detect and treat. Recently, research focus has shifted to analyzing the microenvironment of pancreatic cancer to better understand its key molecular mechanisms. This microenvironment can be represented with a multi-scale model consisting of pancreatic cancer cells (PCCs) and pancreatic stellate cells (PSCs), as well as cytokines and growth factors which are responsible for intercellular communication between the PCCs and PSCs. We have built a stochastic Boolean network (BN) model, validated by literature and clinical data, in which we probed for intervention strategies that force this gene regulatory network (GRN) from a diseased state to a healthy state. To do so, we implemented methods from phenotype control theory to determine a procedure for regulating specific genes within the microenvironment. We identified target genes and molecules, such that the application of their control drives the GRN to the desired state by suppression (or expression) and disruption of specific signaling pathways that may eventually lead to the eradication of the cancer cells. After applying well-studied control methods such as stable motifs, feedback vertex sets, and computational algebra, we discovered that each produces a different set of control targets that are not necessarily minimal nor unique. Yet, we were able to gain more insight about the performance of each process and the overlap of targets discovered. Nearly every control set contains cytokines, KRas, and HER2/neu, which suggests they are key players in the system's dynamics. To that end, this model can be used to produce further insight into the complex biological system of pancreatic cancer with hopes of finding new potential targets.

Parity and time reversal elucidate both decision-making in empirical models and attractor scaling in critical Boolean networks

We present new applications of parity inversion and time reversal to the emergence of complex behavior from simple dynamical rules in stochastic discrete models. Our parity-based encoding of causal relationships and time-reversal construction efficiently reveal discrete analogs of stable and unstable manifolds. We demonstrate their predictive power by studying decision-making in systems biology and statistical physics models. These applications underpin a novel attractor identification algorithm implemented for Boolean networks under stochastic dynamics. Its speed enables resolving a long-standing open question of how attractor count in critical random Boolean networks scales with network size and whether the scaling matches biological observations. Via 80-fold improvement in probed network size (N = 16,384), we find the unexpectedly low scaling exponent of 0.12 ± 0.05, approximately one-tenth the analytical upper bound. We demonstrate a general principle: A system's relationship to its time reversal and state-space inversion constrains its repertoire of emergent behaviors.

Finding the fixed points of a Boolean network from a positive feedback vertex set

MOTIVATION

In the modeling of biological systems by Boolean networks, a key problem is finding the set of fixed points of a given network. Some constructed algorithms consider certain structural properties of the regulatory graph like those proposed by Akutsu et al. and Zhang et al., which consider a feedback vertex set of the graph. However, these methods do not take into account the type of action (activation and inhibition) between its components.

RESULTS

In this article, we propose a new algorithm for finding the set of fixed points of a Boolean network, based on a positive feedback vertex set P of its regulatory graph and which works, by applying a sequential update schedule, in time O(2|P|·n2+k), where n is the number of components and the regulatory functions of the network can be evaluated in time O(nk), k≥0. The theoretical foundation of this algorithm is due a nice characterization, that we give, of the dynamical behavior of the Boolean networks without positive cycles and with a fixed point.

AVAILABILITY AND IMPLEMENTATION

An executable file of FixedPoint algorithm made in Java and some examples of input files are available at: www.inf.udec.cl/˜lilian/FPCollector/.

SUPPLEMENTARY INFORMATION

Supplementary material is available at Bioinformatics online.

Qualitative Modeling, Analysis and Control of Synthetic Regulatory Circuits

Qualitative modeling approaches are promising and still underexploited tools for the analysis and design of synthetic circuits. They can make predictions of circuit behavior in the absence of precise, quantitative information. Moreover, they provide direct insight into the relation between the feedback structure and the dynamical properties of a network. We review qualitative modeling approaches by focusing on two specific formalisms, Boolean networks and piecewise-linear differential equations, and illustrate their application by means of three well-known synthetic circuits. We describe various methods for the analysis of state transition graphs, discrete representations of the network dynamics that are generated in both modeling frameworks. We also briefly present the problem of controlling synthetic circuits, an emerging topic that could profit from the capacity of qualitative modeling approaches to rapidly scan a space of design alternatives.

Mathematical modeling of the Candida albicans yeast to hyphal transition reveals novel control strategies

Candida albicans, an opportunistic fungal pathogen, is a significant cause of human infections, particularly in immunocompromised individuals. Phenotypic plasticity between two morphological phenotypes, yeast and hyphae, is a key mechanism by which C. albicans can thrive in many microenvironments and cause disease in the host. Understanding the decision points and key driver genes controlling this important transition and how these genes respond to different environmental signals is critical to understanding how C. albicans causes infections in the host. Here we build and analyze a Boolean dynamical model of the C. albicans yeast to hyphal transition, integrating multiple environmental factors and regulatory mechanisms. We validate the model by a systematic comparison to prior experiments, which led to agreement in 17 out of 22 cases. The discrepancies motivate alternative hypotheses that are testable by follow-up experiments. Analysis of this model revealed two time-constrained windows of opportunity that must be met for the complete transition from the yeast to hyphal phenotype, as well as control strategies that can robustly prevent this transition. We experimentally validate two of these control predictions in C. albicans strains lacking the transcription factor UME6 and the histone deacetylase HDA1, respectively. This model will serve as a strong base from which to develop a systems biology understanding of C. albicans morphogenesis.

Strategies to Enhance Logic Modeling-Based Cell Line-Specific Drug Synergy Prediction

Discrete dynamical modeling shows promise in prioritizing drug combinations for screening efforts by reducing the experimental workload inherent to the vast numbers of possible drug combinations. We have investigated approaches to predict combination responses across different cancer cell lines using logic models generated from one generic prior-knowledge network representing 144 nodes covering major cancer signaling pathways. Cell-line specific models were configured to agree with baseline activity data from each unperturbed cell line. Testing against experimental data demonstrated a high number of true positive and true negative predictions, including also cell-specific responses. We demonstrate the possible enhancement of predictive capability of models by curation of literature knowledge further detailing subtle biologically founded signaling mechanisms in the model topology. In silico model analysis pinpointed a subset of network nodes highly influencing model predictions. Our results indicate that the performance of logic models can be improved by focusing on high-influence node protein activity data for model configuration and that these nodes accommodate high information flow in the regulatory network.

A Guard Cell Abscisic Acid (ABA) Network Model That Captures the Stomatal Resting State

Stomatal pores play a central role in the control of carbon assimilation and plant water status. The guard cell pair that borders each pore integrates information from environmental and endogenous signals and accordingly swells or deflates, thereby increasing or decreasing the stomatal aperture. Prior research shows that there is a complex cellular network underlying this process. We have previously constructed a signal transduction network and a Boolean dynamic model describing stomatal closure in response to signals including the plant hormone abscisic acid (ABA), calcium or reactive oxygen species (ROS). Here, we improve the Boolean network model such that it captures the biologically expected response of the guard cell in the absence or following the removal of a closure-inducing signal such as ABA or external Ca2+. The expectation from the biological system is reversibility, i.e., the stomata should reopen after the closing signal is removed. We find that the model's reversibility is obstructed by the previously assumed persistent activity of four nodes. By introducing time-dependent Boolean functions for these nodes, the model recapitulates stomatal reopening following the removal of a signal. The previous version of the model predicts ∼20% closure in the absence of any signal due to uncertainty regarding the initial conditions of multiple network nodes. We systematically test and adjust these initial conditions to find the minimally restrictive combinations that appropriately result in open stomata in the absence of a closure signal. We support these results by an analysis of the successive stabilization of feedback motifs in the network, illuminating the system's dynamic progression toward the open or closed stomata state. This analysis particularly highlights the role of cytosolic calcium oscillations in causing and maintaining stomatal closure. Overall, we illustrate the strength of the Boolean network modeling framework to efficiently capture cellular phenotypes as emergent outcomes of intracellular biological processes.

Control of Intracellular Molecular Networks Using Algebraic Methods

Many problems in biology and medicine have a control component. Often, the goal might be to modify intracellular networks, such as gene regulatory networks or signaling networks, in order for cells to achieve a certain phenotype, what happens in cancer. If the network is represented by a mathematical model for which mathematical control approaches are available, such as systems of ordinary differential equations, then this problem might be solved systematically. Such approaches are available for some other model types, such as Boolean networks, where structure-based approaches have been developed, as well as stable motif techniques. However, increasingly many published discrete models are mixed-state or multistate, that is, some or all variables have more than two states, and thus the development of control strategies for multistate networks is needed. This paper presents a control approach broadly applicable to general multistate models based on encoding them as polynomial dynamical systems over a finite algebraic state set, and using computational algebra for finding appropriate intervention strategies. To demonstrate the feasibility and applicability of this method, we apply it to a recently developed multistate intracellular model of E2F-mediated bladder cancerous growth and to a model linking intracellular iron metabolism and oncogenic pathways. The control strategies identified for these published models are novel in some cases and represent new hypotheses, or are supported by the literature in others as potential drug targets. Our Macaulay2 scripts to find control strategies are publicly available through GitHub at https://github.com/luissv7/multistatepdscontrol.

A feedback loop of conditionally stable circuits drives the cell cycle from checkpoint to checkpoint

We perform logic-based network analysis on a model of the mammalian cell cycle. This model is composed of a Restriction Switch driving cell cycle commitment and a Phase Switch driving mitotic entry and exit. By generalizing the concept of stable motif, i.e., a self-sustaining positive feedback loop that maintains an associated state, we introduce the concept of a conditionally stable motif, the stability of which is contingent on external conditions. We show that the stable motifs of the Phase Switch are contingent on the state of three nodes through which it receives input from the rest of the network. Biologically, these conditions correspond to cell cycle checkpoints. Holding these nodes locked (akin to a checkpoint-free cell) transforms the Phase Switch into an autonomous oscillator that robustly toggles through the cell cycle phases G1, G2 and mitosis. The conditionally stable motifs of the Phase Switch Oscillator are organized into an ordered sequence, such that they serially stabilize each other but also cause their own destabilization. Along the way they channel the dynamics of the module onto a narrow path in state space, lending robustness to the oscillation. Self-destabilizing conditionally stable motifs suggest a general negative feedback mechanism leading to sustained oscillations.

Signal flow control of complex signaling networks

Complex disease such as cancer is often caused by genetic mutations that eventually alter the signal flow in the intra-cellular signaling network and result in different cell fate. Therefore, it is crucial to identify control targets that can most effectively block such unwanted signal flow. For this purpose, systems biological analysis provides a useful framework, but mathematical modeling of complicated signaling networks requires massive time-series measurements of signaling protein activity levels for accurate estimation of kinetic parameter values or regulatory logics. Here, we present a novel method, called SFC (Signal Flow Control), for identifying control targets without the information of kinetic parameter values or regulatory logics. Our method requires only the structural information of a signaling network and is based on the topological estimation of signal flow through the network. SFC will be particularly useful for a large-scale signaling network to which parameter estimation or inference of regulatory logics is no longer applicable in practice. The identified control targets have significant implication in drug development as they can be putative drug targets.

Model-driven discovery of calcium-related protein-phosphatase inhibition in plant guard cell signaling

The plant hormone abscisic acid (ABA) promotes stomatal closure via multifarious cellular signaling cascades. Our previous comprehensive reconstruction of the stomatal closure network resulted in an 81-node network with 153 edges. Discrete dynamic modeling utilizing this network reproduced over 75% of experimental observations but a few experimentally supported results were not recapitulated. Here we identify predictions that improve the agreement between model and experiment. We performed dynamics-preserving network reduction, resulting in a condensed 49 node and 113 edge stomatal closure network that preserved all dynamics-determining network motifs and reproduced the predictions of the original model. We then utilized the reduced network to explore cases in which experimental activation of internal nodes in the absence of ABA elicited stomatal closure in wet bench experiments, but not in our in silico model. Our simulations revealed that addition of a single edge, which allows indirect inhibition of any one of three PP2C protein phosphatases (ABI2, PP2CA, HAB1) by cytosolic Ca2+ elevation, resolves the majority of the discrepancies. Consistent with this hypothesis, we experimentally show that Ca2+ application to cellular lysates at physiological concentrations inhibits PP2C activity. The model augmented with this new edge provides new insights into the role of cytosolic Ca2+ oscillations in stomatal closure, revealing a mutual reinforcement between repeated increases in cytosolic Ca2+ concentration and a self-sustaining feedback circuit inside the signaling network. These results illustrate how iteration between model and experiment can improve predictions of highly complex cellular dynamics.

Towards control of cellular decision-making networks in the epithelial-to-mesenchymal transition

We present the epithelial-to-mesenchymal transition (EMT) from two perspectives: experimental/technological and theoretical. We review the state of the current understanding of the regulatory networks that underlie EMT in three physiological contexts: embryonic development, wound healing, and metastasis. We describe the existing experimental systems and manipulations used to better understand the molecular participants and factors that influence EMT and metastasis. We review the mathematical models of the regulatory networks involved in EMT, with a particular emphasis on the network motifs (such as coupled feedback loops) that can generate intermediate hybrid states between the epithelial and mesenchymal states. Ultimately, the understanding gained about these networks should be translated into methods to control phenotypic outcomes, especially in the context of cancer therapeutic strategies. We present emerging theories of how to drive the dynamics of a network toward a desired dynamical attractor (e.g. an epithelial cell state) and emerging synthetic biology technologies to monitor and control the state of cells.

A theoretical framework for controlling complex microbial communities

Microbes form complex communities that perform critical roles for the integrity of their environment or the well-being of their hosts. Controlling these microbial communities can help us restore natural ecosystems and maintain healthy human microbiota. However, the lack of an efficient and systematic control framework has limited our ability to manipulate these microbial communities. Here we fill this gap by developing a control framework based on the new notion of structural accessibility. Our framework uses the ecological network of the community to identify minimum sets of its driver species, manipulation of which allows controlling the whole community. We numerically validate our control framework on large communities, and then we demonstrate its application for controlling the gut microbiota of gnotobiotic mice infected with Clostridium difficile and the core microbiota of the sea sponge Ircinia oros. Our results provide a systematic pipeline to efficiently drive complex microbial communities towards desired states.

Edgetic perturbations to eliminate fixed-point attractors in Boolean regulatory networks

The dynamics of complex biological networks may be modeled in a Boolean framework, where the state of each system component is either abundant (ON) or scarce/absent (OFF), and each component's dynamic trajectory is determined by a logical update rule involving the state(s) of its regulator(s). It is possible to encode the update rules in the topology of the so-called expanded graph, analysis of which reveals the long-term behavior, or attractors, of the network. Here, we develop an algorithm to perturb the expanded graph (or, equivalently, the logical update rules) to eliminate stable motifs: subgraphs that cause a subset of components to stabilize to one state. Depending on the topology of the expanded graph, these perturbations lead to the modification or loss of the corresponding attractor. While most perturbations of biological regulatory networks in the literature involve the knockout (fixing to OFF) or constitutive activation (fixing to ON) of one or more nodes, we here consider edgetic perturbations, where a node's update rule is modified such that one or more of its regulators is viewed as ON or OFF regardless of its actual state. We apply the methodology to two biological networks. In a network representing T-LGL leukemia, we identify edgetic perturbations that eliminate the cancerous attractor, leaving only the healthy attractor representing cell death. In a network representing drought-induced closure of plant stomata, we identify edgetic perturbations that modify the single attractor such that stomata, instead of being fixed in the closed state, oscillates between the open and closed states.

Identifying (un)controllable dynamical behavior in complex networks

We present a technique applicable in any dynamical framework to identify control-robust subsets of an interacting system. These robust subsystems, which we call stable modules, are characterized by constraints on the variables that make up the subsystem. They are robust in the sense that if the defining constraints are satisfied at a given time, they remain satisfied for all later times, regardless of what happens in the rest of the system, and can only be broken if the constrained variables are externally manipulated. We identify stable modules as graph structures in an expanded network, which represents causal links between variable constraints. A stable module represents a system "decision point", or trap subspace. Using the expanded network, small stable modules can be composed sequentially to form larger stable modules that describe dynamics on the system level. Collections of large, mutually exclusive stable modules describe the system's repertoire of long-term behaviors. We implement this technique in a broad class of dynamical systems and illustrate its practical utility via examples and algorithmic analysis of two published biological network models. In the segment polarity gene network of Drosophila melanogaster, we obtain a state-space visualization that reproduces by novel means the four possible cell fates and predicts the outcome of cell transplant experiments. In the T-cell signaling network, we identify six signaling elements that determine the high-signal response and show that control of an element connected to them cannot disrupt this response.

BioLQM: A Java Toolkit for the Manipulation and Conversion of Logical Qualitative Models of Biological Networks

Here we introduce bioLQM, a new Java software toolkit for the conversion, modification, and analysis of Logical Qualitative Models of biological regulatory networks. BioLQM provides core modeling operations as building blocks for the development of integrated modeling software, or for the assembly of heterogeneous analysis workflows involving several complementary tools. Based on the definition of multi-valued logical models, bioLQM implements import and export facilities, notably for the recent SBML qual exchange format, as well as for formats used by several popular tools, facilitating the design of workflows combining these tools. Model modifications enable the definition of various perturbations, as well as model reduction, easing the analysis of large models. Another modification enables the study of multi-valued models with tools limited to the Boolean case. Finally, bioLQM provides a framework for the development of novel analysis tools. The current version implements various updating modes for model simulation (notably synchronous, asynchronous, and random asynchronous), as well as some static analysis features for the identification of attractors. The bioLQM software can be integrated into analysis workflows through command line and scripting interfaces. As a Java library, it further provides core data structures to the GINsim and EpiLog interactive tools, which supply graphical interfaces and additional analysis methods for cellular and multi-cellular qualitative models.

General method to find the attractors of discrete dynamic models of biological systems

Analyzing the long-term behaviors (attractors) of dynamic models of biological networks can provide valuable insight. We propose a general method that can find the attractors of multilevel discrete dynamical systems by extending a method that finds the attractors of a Boolean network model. The previous method is based on finding stable motifs, subgraphs whose nodes' states can stabilize on their own. We extend the framework from binary states to any finite discrete levels by creating a virtual node for each level of a multilevel node, and describing each virtual node with a quasi-Boolean function. We then create an expanded representation of the multilevel network, find multilevel stable motifs and oscillating motifs, and identify attractors by successive network reduction. In this way, we find both fixed point attractors and complex attractors. We implemented an algorithm, which we test and validate on representative synthetic networks and on published multilevel models of biological networks. Despite its primary motivation to analyze biological networks, our motif-based method is general and can be applied to any finite discrete dynamical system.

A Novel Data-Driven Boolean Model for Genetic Regulatory Networks

A Boolean model is a simple, discrete and dynamic model without the need to consider the effects at the intermediate levels. However, little effort has been made into constructing activation, inhibition, and protein decay networks, which could indicate the direct roles of a gene (or its synthesized protein) as an activator or inhibitor of a target gene. Therefore, we propose to focus on the general Boolean functions at the subfunction level taking into account the effectiveness of protein decay, and further split the subfunctions into the activation and inhibition domains. As a consequence, we developed a novel data-driven Boolean model; namely, the Fundamental Boolean Model (FBM), to draw insights into gene activation, inhibition, and protein decay. This novel Boolean model provides an intuitive definition of activation and inhibition pathways and includes mechanisms to handle protein decay issues. To prove the concept of the novel model, we implemented a platform using R language, called FBNNet. Our experimental results show that the proposed FBM could explicitly display the internal connections of the mammalian cell cycle between genes separated into the connection types of activation, inhibition and protein decay. Moreover, the method we proposed to infer the gene regulatory networks for the novel Boolean model can be run in parallel and; hence, the computation cost is affordable. Finally, the novel Boolean model and related Fundamental Boolean Networks (FBNs) could show significant trajectories in genes to reveal how genes regulated each other over a given period. This new feature could facilitate further research on drug interventions to detect the side effects of a newly-proposed drug.

Self-sustaining positive feedback loops in discrete and continuous systems

We consider a dynamic framework frequently used to model gene regulatory and signal transduction networks: monotonic ODEs that are composed of Hill functions. We derive conditions under which activity or inactivity in one system variable induces and sustains activity or inactivity in another. Cycles of such influences correspond to positive feedback loops that are self-sustaining and control-robust, in the sense that these feedback loops "trap" the system in a region of state space from which it cannot exit, even if the other system variables are externally controlled. To demonstrate the utility of this result, we consider prototypical examples of bistability and hysteresis in gene regulatory networks, and analyze a T-cell signal transduction ODE model from the literature.

Estimating Attractor Reachability in Asynchronous Logical Models

Logical models are well-suited to capture salient dynamical properties of regulatory networks. For networks controlling cell fate decisions, cell fates are associated with model attractors (stable states or cyclic attractors) whose identification and reachability properties are particularly relevant. While synchronous updates assume unlikely instantaneous or identical rates associated with component changes, the consideration of asynchronous updates is more realistic but, for large models, may hinder the analysis of the resulting non-deterministic concurrent dynamics. This complexity hampers the study of asymptotical behaviors, and most existing approaches suffer from efficiency bottlenecks, being generally unable to handle cyclical attractors and quantify attractor reachability. Here, we propose two algorithms providing probability estimates of attractor reachability in asynchronous dynamics. The first algorithm, named Firefront, exhaustively explores the state space from an initial state, and provides quasi-exact evaluations of the reachability probabilities of model attractors. The algorithm progresses in breadth, propagating the probabilities of each encountered state to its successors. Second, Avatar is an adapted Monte Carlo approach, better suited for models with large and intertwined transient and terminal cycles. Avatar iteratively explores the state space by randomly selecting trajectories and by using these random walks to estimate the likelihood of reaching an attractor. Unlike Monte Carlo simulations, Avatar is equipped to avoid getting trapped in transient cycles and to identify cyclic attractors. Firefront and Avatar are validated and compared to related methods, using as test cases logical models of synthetic and biological networks. Both algorithms are implemented as new functionalities of GINsim 3.0, a well-established software tool for logical modeling, providing executable GUI, Java API, and scripting facilities.

P_UNSAT approach of attractor calculation for Boolean gene regulatory networks

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.