Construction of Probabilistic Boolean Networks from a Prescribed Transition Probability Matrix: A Maximum Entropy Rate Approach

Modeling genetic regulatory networks is an important problem in genomic research. Boolean Networks (BNs) and their extensions Probabilistic Boolean Networks (PBNs) have been proposed for modeling genetic regulatory interactions. In a PBN, its steady-state distribution gives very important information about the long-run behavior of the whole network. However, one is also interested in system synthesis which requires the construction of networks. The inverse problem is ill-posed and challenging, as there may be many networks or no network having the given properties, and the size of the problem is huge. The construction of PBNs from a given transition-probability matrix and a given set of BNs is an inverse problem of huge size. We propose a maximum entropy approach for the above problem. Newton’s method in conjunction with the Conjugate Gradient (CG) method is then applied to solving the inverse problem. We investigate the convergence rate of the proposed method. Numerical examples are also given to demonstrate the effectiveness of our proposed method.     

Distribution and enumeration of attractors in probabilistic boolean networks

Many mathematical models for gene regulatory networks have been proposed. In this study, the authors study attractors in probabilistic Boolean networks (PBNs). They study the expected number of singleton attractors in a PBN and show that it is (2 - (1=2)/sup L-1)/sup n/, where n is the number of nodes in a PBN and L is the number of Boolean functions assigned to each node. In the case of L = 2, this number is simplified into 1.5/sup n/. It is an interesting result because it is known that the expected number of singleton attractors in a Boolean network (BN) is 1. Then, we present algorithms for identifying singleton and small attractors and perform both theoretical and computational analyses on their average case time complexities. For example, the average case time complexities for identifying singleton attractors of a PBN with L = 2 and L = 3 are O(1.601/sup n/) and O(1.763/sup n/), respectively. The results of computational experiments suggest that these algorithms are much more efficient than the naive algorithm that examines all possible 2/sup n/ states.     

Generating probabilistic boolean networks from a prescribed transition probability matrix

Probabilistic Boolean networks (PBNs) have received much attention in modeling genetic regulatory networks. A PBN can be regarded as a Markov chain process and is characterised by a transition probability matrix. In this study, the authors propose efficient algorithms for constructing a PBN when its transition probability matrix is given. The complexities of the algorithms are also analysed. This is an interesting inverse problem in network inference using steady-state data. The problem is important as most microarray data sets are assumed to be obtained from sampling the steady-state.     

On approximate stochastic control in genetic regulatory networks

The control of probabilistic Boolean networks as a model of genetic regulatory networks is formulated as an optimal stochastic control problem and has been solved using dynamic programming; however, the proposed methods fail when the number of genes in the network goes beyond a small number. There are two dimensionality problems. First, the complexity of optimal stochastic control exponentially increases with the number of genes. Second, the complexity of estimating the probability distributions specifying the model increases exponentially with the number of genes. We propose an approximate stochastic control method based on reinforcement learning that mitigates the curses of dimensionality and provides polynomial time complexity. Using a simulator, the proposed method eliminates the complexity of estimating the probability distributions and, because the method is a model-free method, it eliminates the impediment of model estimation. The method can be applied on networks for which dynamic programming cannot be used owing to computational limitations. Experimental results demonstrate that the performance of the method is close to optimal stochastic control.     

On Construction of Sparse Probabilistic Boolean Networks

In this paper we envisage building Probabilistic Boolean Networks (PBNs) from a prescribed stationary distribution. This is an inverse problem of huge size that can be subdivided into two parts — viz. (i) construction of a transition probability matrix from a given stationary distribution (Problem ST), and (ii) construction of a PBN from a given transition probability matrix (Problem TP). A generalized entropy approach has been proposed for Problem ST and a maximum entropy rate approach for Problem TP respectively. Here we propose to improve both methods, by considering a new objective function based on the entropy rate with an additional term of $L_α$-norm that can help in getting a sparse solution. A sparse solution is useful in identifying the major component Boolean networks (BNs) from the constructed PBN. These major BNs can simplify the identification of the network structure and the design of control policy, and neglecting non-major BNs does not change the dynamics of the constructed PBN to a large extent. Numerical experiments indicate that our new objective function is effective in finding a better sparse solution.     

Detecting small attractors of large Boolean networks by function‐reduction‐based strategy

Boolean networks (BNs) are widely used to model gene regulatory networks and to design therapeutic intervention strategies to affect the long‐term behaviour of systems. A central aim of Boolean‐network analysis is to find attractors that correspond to various cellular states, such as cell types or the stage of cell differentiation. This problem is NP‐hard and various algorithms have been used to tackle it with considerable success. The idea is that a singleton attractor corresponds to n consistent subsequences in the truth table. To find these subsequences, the authors gradually reduce the entire truth table of Boolean functions by extending a partial gene activity profile (GAP). Not only does this process delete inconsistent subsequences in truth tables, it also directly determines values for some nodes not extended, which means it can abandon the partial GAPs that cannot lead to an attractor as early as possible. The results of simulation show that the proposed algorithm can detect small attractors with length p = 4 in BNs of up to 200 nodes with average indegree K = 2.Inspec keywords: Boolean functions, genetics, cellular biophysicsOther keywords: detecting small attractors, function‐reduction‐based strategy, model gene regulatory networks, therapeutic intervention strategies, Boolean‐network analysis, cellular states, NP‐hard, singleton attractor, Boolean functions, partial gene activity profile, cell differentiation     

On Generating Optimal Sparse Probabilistic Boolean Networks with Maximum Entropy from a Positive Stationary Distribution

To understand a genetic regulatory network, two popular mathematical models, Boolean Networks (BNs) and its extension Probabilistic Boolean Networks (PBNs) have been proposed. Here we address the problem of constructing a sparse Probabilistic Boolean Network (PBN) from a prescribed positive stationary distribution. A sparse matrix is more preferable, as it is easier to study and identify the major components and extract the crucial information hidden in a biological network. The captured network construction problem is both ill-posed and computationally challenging. We present a novel method to construct a sparse transition probability matrix from a given stationary distribution. A series of sparse transition probability matrices can be determined once the stationary distribution is given. By controlling the number of nonzero entries in each column of the transition probability matrix, a desirable sparse transition probability matrix in the sense of maximum entropy can be uniquely constructed as a linear combination of the selected sparse transition probability matrices (a set of sparse irreducible matrices). Numerical examples are given to demonstrate both the efficiency and effectiveness of the proposed method.     

Algorithm to identify the optimal perturbation based on the net basin‐of‐state of perturbed states in Boolean network

Boolean networks are widely used to model gene regulatory networks and to design therapeutic intervention strategies to affect the long‐term behavior of systems. Here, the authors investigate the 1 bit perturbation, which falls under the category of structural intervention. The authors’ idea is that, if and only if a perturbed state evolves from a desirable attractor to an undesirable attractor or from an undesirable attractor to a desirable attractor, then the size of basin of attractor of a desirable attractor may decrease or increase. In this case, if the authors obtain the net BOS of the perturbed states, they can quickly obtain the optimal 1 bit perturbation by finding the maximum value of perturbation gain. Results from both synthetic and real biological networks show that the proposed algorithm is not only simpler and but also performs better than the previous basin‐of‐states (BOS)‐based algorithm by Hu et al..Inspec keywords: perturbation theory, genetics, Boolean functionsOther keywords: optimal perturbation, perturbed states, Boolean network, gene regulatory networks, basin‐of‐states‐based algorithm, state‐transition diagram, structural intervention, perturbation gain, synthetic biological networks, real biological networks, 1 bit perturbation     

Fuzzy belief propagation in constrained Bayesian networks with application to maintenance decisions

Bayesian networks have been widely applied to domains such as medical diagnosis, fault analysis, and preventative maintenance. In some applications, because of insufficient data and the complexity of the system, fuzzy parameters and additional constraints derived from expert knowledge can be used to enhance the Bayesian reasoning process. However, very few methods are capable of handling the belief propagation in constrained fuzzy Bayesian networks (CFBNs). This paper therefore develops an improved approach which addresses the inference problem through a max-min programming model. The proposed approach yields more reasonable inference results and with less computational effort. By integrating the probabilistic inference drawn from diverse sources of information with decision analysis considering a decision-maker's risk preference, a CFBN-based decision framework is presented for seeking optimal maintenance decisions in a risk-based environment. The effectiveness of the proposed framework is validated based on an application to a gas compressor maintenance decision problem.     

Robust control of uncertain context-sensitive probabilistic Boolean networks

Uncertainty is an intrinsic phenomenon in control of gene regulatory networks (GRNs). The presence of uncertainty is related to impreciseness of GRN models due to: (1) Errors caused by imperfection of measurement devices and (2) Models' inability to fully capture a complex structure of the GRN. Consequently, there is a discrepancy between actual behaviour of the GRN and what is predicted by its mathematical model. This can result in false control signals, which can drive a cell to an undesirable state. To address the problem of control under uncertainties, a risk-sensitive control paradigm is proposed. Robustness is accomplished by minimisation of the mean exponential cost as opposed to, for instance, minimisation of the mean square cost by risk-neutral controllers. The authors derive an optimal risk-sensitive controller when a GRN is modelled by a context-sensitive probabilistic Boolean network (CSPBN). By using a relation between the relative entropy and free-energy, a relative stability of the cost achieved by the risk-sensitive controller is demonstrated when the distribution of the CSPBN attractors is perturbed, as opposed to the cost of the risk-neutral controller that exhibits increase. The use of the relation between the relative entropy and free-energy to analyse the influence of a particular attractor on the robustness of the controller is studied. The efficiency of the risk-sensitive controller is tested for the CSPBN obtained from the study of malignant melanoma.     

Integer programming‐based method for observability of singleton attractors in Boolean networks

Boolean network (BN) is a popular mathematical model for revealing the behaviour of a genetic regulatory network. Furthermore, observability, an important network feature, plays a significant role in understanding the underlying network. Several studies have been done on analysis of observability of BNs and complex networks. However, the observability of attractor cycles, which can serve as biomarker detection, has not yet been addressed in the literature. This is an important, interesting and challenging problem that deserves a detailed study. In this study, a novel problem was first proposed on attractor observability in BNs. Identification of the minimum set of consecutive nodes can be used to discriminate different attractors. Furthermore, it can serve as a biomarker for different disease types (represented as different attractor cycles). Then a novel integer programming method was developed to identify the desired set of nodes. The proposed approach is demonstrated and verified by numerical examples. The computational results further illustrates that the proposed model is effective and efficient.Inspec keywords: integer programming, Boolean algebra, complex networks, diseasesOther keywords: disease, consecutive nodes, biomarker detection, attractor cycles, complex networks, genetic regulatory network, mathematical model, Boolean networks, singleton attractors, integer programming‐based method     

Optimal design of hybrid laminates with discrete ply angles for maximum buckling load and minimum cost

The design of hybrid symmetric laminated plates consisting of high-stiffness surface and low-stiffness core layers is presented. In the first problem the maximization of buckling load is carried out over a discrete set of ply angles. In the second problem the minimum number of high-stiffness plies is determined for a given buckling load to minimize the material cost. Boolean variables are introduced to specify stacking sequence. Solution of the linear optimization problem yields an optimal stacking sequence. The effect of hybridization is investigated for various problem parameters such as the aspect ratio of the laminate and the number of plies. The optimal designs are obtained with upper bound constraints on the effect of bending-twisting coupling stiffnesses. Results are given for hybrid graphite-epoxy/glass-epoxy laminates under both uniaxial and biaxial loadings.     

Convergence control of the iterative procedure for performance-measure-based probabilistic structural design optimization

The advanced mean value (AMV) iterative scheme is commonly used to evaluate probabilistic constraints in the performance measure approach (PMA) for probabilistic structural design optimization (PSDO). However, the iterative procedure of PSDO may fail to converge. In this article, the chaotic dynamics theory is suggested to investigate and attack the non-convergence difficulties of PMA-based PSDO. Essentially, the AMV iterative formula forms a discrete dynamical system with control parameters. If the AMV iterative sequences present the numerical instabilities of periodic oscillation, bifurcation, and even chaos in some control parameter interval, then the outer optimization loop in PSDO cannot converge and acquire the correct optimal design. Furthermore, the stability transformation method (STM) of chaos feedback control is applied to perform the convergence control of AMV, in order to capture the desired fixed points in the whole control parameter interval. Meanwhile, PSDO is solved by the approaches of PMA two-level and PMA with the sequential approximate programming (SAP)—PMA with SAP. Numerical results of several examples illustrate that STM can smoothly overcome the convergence failure of PSDO resulting from the periodic oscillation, bifurcation, and chaotic solutions of AMV iterative procedure for evaluating the probabilistic constraints. Moreover, the probabilistic optimization with uniform random variables, which is widely recognized as a highly nonlinear and fairly difficult problem, can be attacked through introducing the strategy of chaos control. In addition, the approach of PMA with SAP combining with STM is quite effective and efficient.     

Physics-constrained non-Gaussian probabilistic learning on manifolds

An extension of the probabilistic learning on manifolds (PLoM), recently introduced by the authors, has been presented: In addition to the initial data set given for performing the probabilistic learning, constraints are given, which correspond to statistics of experiments or of physical models. We consider a non-Gaussian random vector whose unknown probability distribution has to satisfy constraints. The method consists in constructing a generator using the PLoM and the classical Kullback-Leibler minimum cross-entropy principle. The resulting optimization problem is reformulated using Lagrange multipliers associated with the constraints. The optimal solution of the Lagrange multipliers is computed using an efficient iterative algorithm. At each iteration, the Markov chain Monte Carlo algorithm developed for the PLoM is used, consisting in solving an Itô stochastic differential equation that is projected on a diffusion-maps basis. The method and the algorithm are efficient and allow the construction of probabilistic models for high-dimensional problems from small initial data sets and for which an arbitrary number of constraints are specified. The first application is sufficiently simple in order to be easily reproduced. The second one is relative to a stochastic elliptic boundary value problem in high dimension.     

A Genetic Algorithm to Solve Capacity Assignment Problem in a Flow Network

Computer networks and power transmission networks are treated as capacitated flow networks. A capacitated flow network may partially fail due to maintenance. Therefore, the capacity of each edge should be optimally assigned to face critical situations—i.e., to keep the network functioning normally in the case of failure at one or more edges. The robust design problem (RDP) in a capacitated flow network is to search for the minimum capacity assignment of each edge such that the network still survived even under the edge’s failure. The RDP is known as NP-hard. Thus, capacity assignment problem subject to system reliability and total capacity constraints is studied in this paper. The problem is formulated mathematically, and a genetic algorithm is proposed to determine the optimal solution. The optimal solution found by the proposed algorithm is characterized by maximum reliability and minimum total capacity. Some numerical examples are presented to illustrate the efficiency of the proposed approach.     

An Enhanced Transcribing Scheme for the Numerical Solution of a Class of Optimal Control Problems

An enhanced scheme of transcribing the system dynamics for the numerical solution of optimal control problems is proposed. This new scheme is based on the standard method of direct collocation that converts an optimal control problem into a nonlinear programming problem via simultaneous state and control discretization. When compared with the standard method, the enhanced scheme has the advantage of higher solution accuracy with minimal additional computational effort. It is particularly suited for systems with states that are related to each other in a special form. For such systems, the ensuing nonlinear programming problem has the same number of constraints as those using the standard method. Numerical results on several optimal control problems using the enhanced scheme are presented, together with comparisons with the results obtained from the standard scheme.     

A Parallel Strategy for the Logical‐probabilistic Calculus‐based Method to Calculate Two‐terminal Reliability

The theory of network reliability has been applied to many complicated network structures, such as computer and communication networks, piping systems, electricity networks, and traffic networks. The theory is used to evaluate the operational performance of networks that can be modeled by probabilistic graphs. Although evaluating network reliability is an Non‐deterministic Polynomial‐time hard problem, numerous solutions have been proposed. However, most of them are based on sequential computing, which under‐utilizes the benefits of multi‐core processor architectures. This paper addresses this limitation by proposing an efficient strategy for calculating the two‐terminal (terminal‐pair) reliability of a binary‐state network that uses parallel computing. Existing methods are analyzed. Then, an efficient method for calculating terminal‐pair reliability based on logical‐probabilistic calculus is proposed. Finally, a parallel version of the proposed algorithm is developed. This is the first study to implement an algorithm for estimating terminal‐pair reliability in parallel on multi‐core processor architectures. The experimental results show that the proposed algorithm and its parallel version outperform an existing sequential algorithm in terms of execution time. Copyright © 2015 John Wiley & Sons, Ltd.     

Adaptive opportunistic fair scheduling in power-controlled code division multiple access systems

The authors treat the multiuser scheduling problem for practical power-controlled code division multiple access (CDMA) systems under the opportunistic fair scheduling (OFS) framework. OFS is an important technique in wireless networks to achieve fair and efficient resource allocation. Power control is an effective resource management technique in CDMA systems. Given a certain user subset, the optimal power control scheme can be derived. Then the multiuser scheduling problem refers to the optimal user subset selection at each scheduling interval to maximise certain metric subject to some specific physical-layer constraints. The authors propose discrete stochastic approximation algorithms to adaptively select the user subset to maximise the instantaneous total throughput or a general utility. Both uplink and downlink scenarios are considered. They also consider the time-varying channels where the algorithm can track the time-varying optimal user subset. Simulation results to show the performance of the proposed algorithms in terms of the throughput/ utility maximisation, the fairness, the fast convergence and the tracking capability in time-varying environments are presented.