A Parallel Attractor Finding Algorithm Based on Boolean Satisfiability for Genetic Regulatory Networks

In biological systems, the dynamic analysis method has gained increasing attention in the past decade. The Boolean network is the most common model of a genetic regulatory network. The interactions of activation and inhibition in the genetic regulatory network are modeled as a set of functions of the Boolean network, while the state transitions in the Boolean network reflect the dynamic property of a genetic regulatory network. A difficult problem for state transition analysis is the finding of attractors. In this paper, we modeled the genetic regulatory network as a Boolean network and proposed a solving algorithm to tackle the attractor finding problem. In the proposed algorithm, we partitioned the Boolean network into several blocks consisting of the strongly connected components according to their gradients, and defined the connection between blocks as decision node. Based on the solutions calculated on the decision nodes and using a satisfiability solving algorithm, we identified the attractors in the state transition graph of each block. The proposed algorithm is benchmarked on a variety of genetic regulatory networks. Compared with existing algorithms, it achieved similar performance on small test cases, and outperformed it on larger and more complex ones, which happens to be the trend of the modern genetic regulatory network. Furthermore, while the existing satisfiability-based algorithms cannot be parallelized due to their inherent algorithm design, the proposed algorithm exhibits a good scalability on parallel computing architectures.     

MPSQ: a web tool for protein-state searching

MPSQ (multi-protein-states query) is a web-based tool for the discovery of protein states (e.g. biological interactions, covalent modifications, cellular localizations). In particular, large sets of genes can be used to search for enriched state transition network maps (NMs) and features facilitating the interpretation of genomic-scale experiments such as microarrays. One NM collects all the catalogued states of a protein as well as the mutual transitions between the states. For the returned NM, graph visualization is provided for easy understanding and to guide further analysis.     

Analysis of Discrete Bioregulatory Networks Using Symbolic Steady States

A discrete model of a biological regulatory network can be represented by a discrete function that contains all available information on interactions between network components and the rules governing the evolution of the network in a finite state space. Since the state space size grows exponentially with the number of network components, analysis of large networks is a complex problem. In this paper, we introduce the notion of symbolic steady state that allows us to identify subnetworks that govern the dynamics of the original network in some region of state space. We state rules to explicitly construct attractors of the system from subnetwork attractors. Using the results, we formulate sufficient conditions for the existence of multiple attractors resp. a cyclic attractor based on the existence of positive resp. negative feedback circuits in the graph representing the structure of the system. In addition, we discuss approaches to finding symbolic steady states. We focus both on dynamics derived via synchronous as well as asynchronous update rules. Lastly, we illustrate the results by analyzing a model of T helper cell differentiation.     

The role of phase shifts of sensory inputs in walking revealed by means of phase reduction

Detailed neural network models of animal locomotion are important means to understand the underlying mechanisms that control the coordinated movement of individual limbs. Daun-Gruhn and Tóth, Journal of Computational Neuroscience 31(2), 43–60 (2011) constructed an inter-segmental network model of stick insect locomotion consisting of three interconnected central pattern generators (CPGs) that are associated with the protraction-retraction movements of the front, middle and hind leg. This model could reproduce the basic locomotion coordination patterns, such as tri- and tetrapod, and the transitions between them. However, the analysis of such a system is a formidable task because of its large number of variables and parameters. In this study, we employed phase reduction and averaging theory to this large network model in order to reduce it to a system of coupled phase oscillators. This enabled us to analyze the complex behavior of the system in a reduced parameter space. In this paper, we show that the reduced model reproduces the results of the original model. By analyzing the interaction of just two coupled phase oscillators, we found that the neighboring CPGs could operate within distinct regimes, depending on the phase shift between the sensory inputs from the extremities and the phases of the individual CPGs. We demonstrate that this dependence is essential to produce different coordination patterns and the transition between them. Additionally, applying averaging theory to the system of all three phase oscillators, we calculate the stable fixed points - they correspond to stable tripod or tetrapod coordination patterns and identify two ways of transition between them.     

The small world inside large metabolic networks

The metabolic network of the catabolic, energy and biosynthetic metabolism of Escherichia coli is a paradigmatic case for the large genetic and metabolic networks that functional genomics efforts are beginning to elucidate. To analyse the structure of previously unknown networks involving hundreds or thousands of components by simple visual inspection is impossible, and quantitative approaches are needed to analyse them. We have undertaken a graph theoretical analysis of the E. coli metabolic network and find that this network is a small-world graph, a type of graph distinct from both regular and random networks and observed in a variety of seemingly unrelated areas, such as friendship networks in sociology, the structure of electrical power grids, and the nervous system of Caenorhabditis elegans. Moreover, the connectivity of the metabolites follows a power law, another unusual but by no means rare statistical distribution. This provides an objective criterion for the centrality of the tricarboxylic acid cycle to metabolism. The small-world architecture may serve to minimize transition times between metabolic states, and contains evidence about the evolutionary history of metabolism.     

Emerging Methods and Applications to Decrypt Allostery in Proteins and Nucleic Acids

Many large protein-nucleic acid complexes exhibit allosteric regulation. In these systems, the propagation of the allosteric signaling is strongly coupled to conformational dynamics and catalytic function, challenging state-of-the-art analytical methods. Here, we review established and innovative approaches used to elucidate allosteric mechanisms in these complexes. Specifically, we report network models derived from graph theory and centrality analyses in combination with molecular dynamics (MD) simulations, introducing novel schemes that implement the synergistic use of graph theory with enhanced simulations methods and ab-initio MD. Accelerated MD simulations are used to construct “enhanced network models”, describing the allosteric response over long timescales and capturing the relation between allostery and conformational changes. “Ab-initio network models” combine graph theory with ab-initio MD and quantum mechanics/molecular mechanics (QM/MM) simulations to describe the allosteric regulation of catalysis by following the step-by-step dynamics of biochemical reactions. This approach characterizes how the allosteric regulation changes from reactants to products and how it affects the transition state, revealing a tense-to-relaxed allosteric regulation along the chemical step. Allosteric models and applications are showcased for three paradigmatic examples of allostery in protein-nucleic acid complexes: (i) the nucleosome core particle, (ii) the CRISPR-Cas9 genome editing system and (iii) the spliceosome. These methods and applications create innovative protocols to determine allosteric mechanisms in protein-nucleic acid complexes that show tremendous promise for medicine and bioengineering.     

Uncovering operational interactions in genetic networks using asynchronous Boolean dynamics

Biological networks of large dimensions, with their diagram of interactions, are often well represented by a Boolean model with a family of logical rules. The state space of a Boolean model is finite, and its asynchronous dynamics are fully described by a transition graph in the state space. In this context, a model reduction method will be developed for identifying the active or operational interactions responsible for a given dynamic behaviour. The first step in this procedure is the decomposition of the asynchronous transition graph into its strongly connected components, to obtain a “reduced” and hierarchically organized graph of transitions. The second step consists of the identification of a partial graph of interactions and a sub-family of logical rules that remain operational in a given region of the state space. This model reduction method and its usefulness are illustrated by an application to a model of programmed cell death. The method identifies two mechanisms used by the cell to respond to death-receptor stimulation and decide between the survival and apoptotic pathways.     

A network model for activity-dependent sleep regulation

We develop and characterize a dynamical network model for activity-dependent sleep regulation. Specifically, in accordance with the activity-dependent theory for sleep, we view organism sleep as emerging from the local sleep states of functional units known as cortical columns; these local sleep states evolve through integration of local activity inputs, loose couplings with neighboring cortical columns, and global regulation (e.g. by the circadian clock). We model these cortical columns as coupled or networked activity-integrators that transition between sleep and waking states based on thresholds on the total activity. The model dynamics for three canonical experiments (which we have studied both through simulation and system-theoretic analysis) match with experimentally observed characteristics of the cortical-column network. Most notably, assuming connectedness of the network graph, our model predicts the recovery of the columns to a synchronized state upon temporary overstimulation of a single column and/or randomization of the initial sleep and activity-integration states. In analogy with other models for networked oscillators, our model also predicts the possibility for such phenomena as mode-locking.     

Uterine Synchronization Analysis During Pregnancy and Labor Using Graph Theory,Classification Based on Neural Network and Deep Learning

1) ObjectivesPreterm birth caused by preterm labor is one of the major health problems in the world. In this article, we present a new framework for dealing with this problem through the processing of electrohysterographic signals (EHG) that are recorded during labor and pregnancy. The objective in this research is to improve the classification between labor and pregnancy contractions by using a new approach that focuses on the connectivity analysis based on graph parameters, representative of uterine synchronization, and comparing neural network and machine learning methods in order to classify between labor and pregnancy.2) Material and methodsafter denoising of the 16 EHG signals recorded from pregnant women abdomen, we applied different connectivity methods to obtain connectivity matrices; then by using the graph theory, we extracted some graph parameters from the connectivity matrices; finally, we tested different neural network and machine learning methods on the features obtained from both graph and connectivity methods in order to classify between labor and pregnancy.3) ResultsThe best results were obtained by using the logistic regression method. We also evidence the power of graph parameters extracted from the connectivity matrices to improve the classification results.4) ConclusionThe use of graph analysis associated with machine learning methods can be a powerful tool to improve labor and pregnancy classification based on the analysis of EHG signals.     

Generating Boolean networks with a prescribed attractor structure

MOTIVATION: Dynamical modeling of gene regulation via network models constitutes a key problem for genomics. The long-run characteristics of a dynamical system are critical and their determination is a primary aspect of system analysis. In the other direction, system synthesis involves constructing a network possessing a given set of properties. This constitutes the inverse problem. Generally, the inverse problem is ill-posed, meaning there will be many networks, or perhaps none, possessing the desired properties. Relative to long-run behavior, we may wish to construct networks possessing a desirable steady-state distribution. This paper addresses the long-run inverse problem pertaining to Boolean networks (BNs). RESULTS: The long-run behavior of a BN is characterized by its attractors. The rest of the state transition diagram is partitioned into level sets, the j-th level set being composed of all states that transition to one of the attractor states in exactly j transitions. We present two algorithms for the attractor inverse problem. The attractors are specified, and the sizes of the predictor sets and the number of levels are constrained. Algorithm complexity and performance are analyzed. The algorithmic solutions have immediate application. Under the assumption that sampling is from the steady state, a basic criterion for checking the validity of a designed network is that there should be concordance between the attractor states of the model and the data states. This criterion can be used to test a design algorithm: randomly select a set of states to be used as data states; generate a BN possessing the selected states as attractors, perhaps with some added requirements such as constraints on the number of predictors and the level structure; apply the design algorithm; and check the concordance between the attractor states of the designed network and the data states. AVAILABILITY: The software and supplementary material is available at http://gsp.tamu.edu/Publications/BNs/bn.htm     

Frequency Response and Gap Tuning for Nonlinear Electrical Oscillator Networks

We study nonlinear electrical oscillator networks, the smallest example of which consists of a voltage-dependent capacitor, an inductor, and a resistor driven by a pure tone source. By allowing the network topology to be that of any connected graph, such circuits generalize spatially discrete nonlinear transmission lines/lattices that have proven useful in high-frequency analog devices. For such networks, we develop two algorithms to compute the steady-state response when a subset of nodes are driven at the same fixed frequency. The algorithms we devise are orders of magnitude more accurate and efficient than stepping towards the steady-state using a standard numerical integrator. We seek to enhance a given network''s nonlinear behavior by altering the eigenvalues of the graph Laplacian, i.e., the resonances of the linearized system. We develop a Newton-type method that solves for the network inductances such that the graph Laplacian achieves a desired set of eigenvalues; this method enables one to move the eigenvalues while keeping the network topology fixed. Running numerical experiments using three different random graph models, we show that shrinking the gap between the graph Laplacian''s first two eigenvalues dramatically improves a network''s ability to (i) transfer energy to higher harmonics, and (ii) generate large-amplitude signals. Our results shed light on the relationship between a network''s structure, encoded by the graph Laplacian, and its function, defined in this case by the presence of strongly nonlinear effects in the frequency response.     

Emergence of the Mitochondrial Reticulum from Fission and Fusion Dynamics

Mitochondria form a dynamic tubular reticulum within eukaryotic cells. Currently, quantitative understanding of its morphological characteristics is largely absent, despite major progress in deciphering the molecular fission and fusion machineries shaping its structure. Here we address the principles of formation and the large-scale organization of the cell-wide network of mitochondria. On the basis of experimentally determined structural features we establish the tip-to-tip and tip-to-side fission and fusion events as dominant reactions in the motility of this organelle. Subsequently, we introduce a graph-based model of the chondriome able to encompass its inherent variability in a single framework. Using both mean-field deterministic and explicit stochastic mathematical methods we establish a relationship between the chondriome structural network characteristics and underlying kinetic rate parameters. The computational analysis indicates that mitochondrial networks exhibit a percolation threshold. Intrinsic morphological instability of the mitochondrial reticulum resulting from its vicinity to the percolation transition is proposed as a novel mechanism that can be utilized by cells for optimizing their functional competence via dynamic remodeling of the chondriome. The detailed size distribution of the network components predicted by the dynamic graph representation introduces a relationship between chondriome characteristics and cell function. It forms a basis for understanding the architecture of mitochondria as a cell-wide but inhomogeneous organelle. Analysis of the reticulum adaptive configuration offers a direct clarification for its impact on numerous physiological processes strongly dependent on mitochondrial dynamics and organization, such as efficiency of cellular metabolism, tissue differentiation and aging.     

Attractor analysis of asynchronous Boolean models of signal transduction networks

Prior work on the dynamics of Boolean networks, including analysis of the state space attractors and the basin of attraction of each attractor, has mainly focused on synchronous update of the nodes’ states. Although the simplicity of synchronous updating makes it very attractive, it fails to take into account the variety of time scales associated with different types of biological processes. Several different asynchronous update methods have been proposed to overcome this limitation, but there have not been any systematic comparisons of the dynamic behaviors displayed by the same system under different update methods. Here we fill this gap by combining theoretical analysis such as solution of scalar equations and Markov chain techniques, as well as numerical simulations to carry out a thorough comparative study on the dynamic behavior of a previously proposed Boolean model of a signal transduction network in plants. Prior evidence suggests that this network admits oscillations, but it is not known whether these oscillations are sustained. We perform an attractor analysis of this system using synchronous and three different asynchronous updating schemes both in the case of the unperturbed (wild-type) and perturbed (node-disrupted) systems. This analysis reveals that while the wild-type system possesses an update-independent fixed point, any oscillations eventually disappear unless strict constraints regarding the timing of certain processes and the initial state of the system are satisfied. Interestingly, in the case of disruption of a particular node all models lead to an extended attractor. Overall, our work provides a roadmap on how Boolean network modeling can be used as a predictive tool to uncover the dynamic patterns of a biological system under various internal and environmental perturbations.     

State reduction for network intervention in probabilistic Boolean networks

MOTIVATION: A key goal of studying biological systems is to design therapeutic intervention strategies. Probabilistic Boolean networks (PBNs) constitute a mathematical model which enables modeling, predicting and intervening in their long-run behavior using Markov chain theory. The long-run dynamics of a PBN, as represented by its steady-state distribution (SSD), can guide the design of effective intervention strategies for the modeled systems. A major obstacle for its application is the large state space of the underlying Markov chain, which poses a serious computational challenge. Hence, it is critical to reduce the model complexity of PBNs for practical applications. RESULTS: We propose a strategy to reduce the state space of the underlying Markov chain of a PBN based on a criterion that the reduction least distorts the proportional change of stationary masses for critical states, for instance, the network attractors. In comparison to previous reduction methods, we reduce the state space directly, without deleting genes. We then derive stationary control policies on the reduced network that can be naturally induced back to the original network. Computational experiments study the effects of the reduction on model complexity and the performance of designed control policies which is measured by the shift of stationary mass away from undesirable states, those associated with undesirable phenotypes. We consider randomly generated networks as well as a 17-gene gastrointestinal cancer network, which, if not reduced, has a 2(17) × 2(17) transition probability matrix. Such a dimension is too large for direct application of many previously proposed PBN intervention strategies.     

A simple network thermodynamic method for series-parallel coupled flows: II. The non-linear theory, with applications to coupled solute and volume flow in a series membrane

Building on the linear network thermodynamic model presented in the first paper in this series (Mikulecky, Wiegand &; Shiner, 1977), a method of non-linear analysis is developed based mainly on the methods of Chua (1969). Using coupled salt and volume flow through membranes as an example, it is shown that the Kedem &; Katchalsky (1963a,b,c) linear model of series combinations of membranes behaves in a physically unrealistic manner (negative and infinite concentrations occur in the compartment between the membranes). Using the model introduced by Patlak, Goldstein &; Hoffman (1963) to obtain characteristics for a non-linear 2-port, the series network is well behaved and self-regulated. In the coordinate system of the linear reciprocal 2-port, the non-linear 2-port is shown to be a non-reciprocal element. Another co-ordinate system, which utilizes unidirectional fluxes (as measured by isotope fluxes, for example) and their conjugate driving forces, shows the non-linear 2-port to be separable in the sense of Li (1962) and Rosen (1968). A set of three pseudo-independent force-flow pairs completely characterizes the system and is compatible with a very simple non-linear network analysis which utilizes experimentally accessible and practical parameters such as the unidirectional solute fluxes, concentrations in the baths, volume flow and the hydrostatic minus effective osmotic pressure. As constitutive relations, the forward and backward permeabilities, which are dependent on volume flow and the filtration coefficient are all that are needed. A reflection coefficient appears in the driving force conjugate to volume flow in that the effective osmotic pressure is δΔπ and thus four independent coefficients, two of which depend on volume flow, are needed to determine the system. From the network analysis, the global properties of the series and/or parallel combinations of non-linear 2-ports are readily obtained. Although applied to a particular example, these non-linear methods are perfectly general. They are essentially the graphical form of the algebraic analysis in the linear theory, and are essentially based on the generalized version of Kirchhoff's laws used in graph and network theory. In the particular case of coupled solute and volume flow through membranes the non-linear element has a natural piecewise linearization which allows the linear theory to be applied using different values for the elements in each region.In an initial analysis, a linear network is drawn using the I-equivalent network of 1-port elements to model the linear 2-port in a series system. From this over-simplication a great deal of the qualitative behavior of the system can be visualized. For example, it is an easy way to see that solute will be accumulated or depleted in the central compartment between the membranes in an asymmetric series system. After this the non-linear analysis is used to further quantitatively describe the system's behavior and such phenomena as rectification of volume flow in the series membrane system. An appendix introduces a general theory for a class of non-linear transport phenomena.     

Dynamic models of gene expression and classification

Powerful new methods, like expression profiles using cDNA arrays, have been used to monitor changes in gene expression levels as a result of a variety of metabolic, xenobiotic or pathogenic challenges. This potentially vast quantity of data enables, in principle, the dissection of the complex genetic networks that control the patterns and rhythms of gene expression in the cell. Here we present a general approach to developing dynamic models for analyzing time series of whole genome expression. In this approach, a self-consistent calculation is performed that involves both linear and non-linear response terms for interrelating gene expression levels. This calculation uses singular value decomposition (SVD) not as a statistical tool but as a means of inverting noisy and near-singular matrices. The linear transition matrix that is determined from this calculation can be used to calculate the underlying network reflected in the data. This suggests a direct method of classifying genes according to their place in the resulting network. In addition to providing a means to model such a large multivariate system this approach can be used to reduce the dimensionality of the problem in a rational and consistent way, and suppress the strong noise amplification effects often encountered with expression profile data. Non-linear and higher-order Markov behavior of the network are also determined in this self-consistent method. In data sets from yeast, we calculate the Markov matrix and the gene classes based on the linear-Markov network. These results compare favorably with previously used methods like cluster analysis. Our dynamic method appears to give a broad and general framework for data analysis and modeling of gene expression arrays. Electronic Publication     

Intervention in Context-Sensitive Probabilistic Boolean Networks Revisited

An approximate representation for the state space of a context-sensitive probabilistic Boolean network has previously been proposed and utilized to devise therapeutic intervention strategies. Whereas the full state of a context-sensitive probabilistic Boolean network is specified by an ordered pair composed of a network context and a gene-activity profile, this approximate representation collapses the state space onto the gene-activity profiles alone. This reduction yields an approximate transition probability matrix, absent of context, for the Markov chain associated with the context-sensitive probabilistic Boolean network. As with many approximation methods, a price must be paid for using a reduced model representation, namely, some loss of optimality relative to using the full state space. This paper examines the effects on intervention performance caused by the reduction with respect to various values of the model parameters. This task is performed using a new derivation for the transition probability matrix of the context-sensitive probabilistic Boolean network. This expression of transition probability distributions is in concert with the original definition of context-sensitive probabilistic Boolean network. The performance of optimal and approximate therapeutic strategies is compared for both synthetic networks and a real case study. It is observed that the approximate representation describes the dynamics of the context-sensitive probabilistic Boolean network through the instantaneously random probabilistic Boolean network with similar parameters.     

生物分子网络弹性研究进展

弹性是生物分子网络重要且基础的属性之一,一方面弹性赋予生物分子网络抵抗内部噪声与环境干扰并维持其自身基本功能的能力,另一方面,弹性为网络状态的恢复制造了阻力。生物分子网络弹性研究试图回答如下3个问题：a. 生物分子网络弹性的产生机理是什么？b. 弹性影响下生物分子网络的状态如何发生转移？c. 如何预测生物网络状态转换临界点,以防止系统向不理想的状态演化？因此,研究生物分子网络弹性有助于理解生物系统内部运作机理,同时对诸如疾病发生临界点预测、生物系统状态逆转等临床应用具有重要的指导意义。鉴于此,本文主要针对以上生物分子网络弹性领域的3个热点研究问题,在研究方法和生物学应用上进行了系统地综述,并对未来生物分子网络弹性的研究方向进行了展望。     

Statistical analysis of channel current from a membrane patch. I. Some stochastic properties of ion channels or molecular systems in equilibrium

The stochastic behavior of single-channel current in a steady-state has been interpreted as the channel's state transitions between several open and shut states, and these transitions have been regarded as a homogeneous Markov process. When a channel is in equilibrium, the principle of detailed balance holds for every step in the state transition scheme. Here we show two stochastic properties of a channel, or any molecule obeying a reversible state transition scheme, under the constraint of detailed balance. First, the distribution functions and the probability density functions of shut or open dwell-time are expressed by the sum of exponential terms with positive coefficients. The same holds for the time-dependent open (or shut) frequency after the shut (or open) transition. Second, the time course of state transition from the state SI to SJ (PI,J(t] is proportional to its reverse transition time course (PJ,I(t], even if SI and SJ are widely separated. The same relation holds also for a transition scheme having transition pathways to the absorbing states. If analysis of a channel current record shows it to be incompatible with either of these two properties, the channel is not in equilibrium but in a steady-state with an energy-consuming cyclic flow. These two properties are also useful for the analysis of any molecular process obeying a homogeneous Markov process or a network of first-order chemical reactions.