Gene perturbation and intervention in probabilistic Boolean networks

MOTIVATION: A major objective of gene regulatory network modeling, in addition to gaining a deeper understanding of genetic regulation and control, is the development of computational tools for the identification and discovery of potential targets for therapeutic intervention in diseases such as cancer. We consider the general question of the potential effect of individual genes on the global dynamical network behavior, both from the view of random gene perturbation as well as intervention in order to elicit desired network behavior. RESULTS: Using a recently introduced class of models, called Probabilistic Boolean Networks (PBNs), this paper develops a model for random gene perturbations and derives an explicit formula for the transition probabilities in the new PBN model. This result provides a building block for performing simulations and deriving other results concerning network dynamics. An example is provided to show how the gene perturbation model can be used to compute long-term influences of genes on other genes. Following this, the problem of intervention is addressed via the development of several computational tools based on first-passage times in Markov chains. The consequence is a methodology for finding the best gene with which to intervene in order to most likely achieve desirable network behavior. The ideas are illustrated with several examples in which the goal is to induce the network to transition into a desired state, or set of states. The corresponding issue of avoiding undesirable states is also addressed. Finally, the paper turns to the important problem of assessing the effect of gene perturbations on long-run network behavior. A bound on the steady-state probabilities is derived in terms of the perturbation probability. The result demonstrates that states of the network that are more 'easily reachable' from other states are more stable in the presence of gene perturbations. Consequently, these are hypothesized to correspond to cellular functional states. AVAILABILITY: A library of functions written in MATLAB for simulating PBNs, constructing state-transition matrices, computing steady-state distributions, computing influences, modeling random gene perturbations, and finding optimal intervention targets, as described in this paper, is available on request from is@ieee.org.     

An approximation method for solving the steady-state probability distribution of probabilistic Boolean networks

MOTIVATION: Probabilistic Boolean networks (PBNs) have been proposed to model genetic regulatory interactions. The steady-state probability distribution of a PBN gives important information about the captured genetic network. The computation of the steady-state probability distribution usually includes construction of the transition probability matrix and computation of the steady-state probability distribution. The size of the transition probability matrix is 2(n)-by-2(n) where n is the number of genes in the genetic network. Therefore, the computational costs of these two steps are very expensive and it is essential to develop a fast approximation method. RESULTS: In this article, we propose an approximation method for computing the steady-state probability distribution of a PBN based on neglecting some Boolean networks (BNs) with very small probabilities during the construction of the transition probability matrix. An error analysis of this approximation method is given and theoretical result on the distribution of BNs in a PBN with at most two Boolean functions for one gene is also presented. These give a foundation and support for the approximation method. Numerical experiments based on a genetic network are given to demonstrate the efficiency of the proposed method.     

Importance of correlations among matrix entries in stochastic models in relation to number of transition matrices

Stochastic matrix models are used to predict population viability and the risk of extinction. Different stochastic methods require different amounts of estimation effort and may lead to divergent estimates. We used 16 transition matrices collected from ten populations of the perennial herb Primula veris to compare population estimates produced by different stochastic methods, such as selection of matrices, selection of vital rates, selection of matrix elements, and Tuljapurkar's approximation. Specifically, we tested the reliability of the methods using different numbers of transition matrices, and examined the importance of correlations among matrix entries. When correlations among matrix entries were included in the models, selection of vital rates produced the lowest and Tuljapurkar's approximation produced the highest estimates of mean population growth rates. Selection of matrices and matrix elements often produced nearly similar population estimates. Simulations based on incompletely estimated correlations among matrix entries considerably differed from those based on all correlations estimated, particularly when correlations were strong. The magnitude of correlations among matrix entries depended on the number of matrices, which made it difficult to generalize correlations within a species. Given that selection of vital rates or matrix elements is used, correlations among matrix entries should usually be included in the model, and they should preferably be estimated from the present data rather than according to other information of the species.     

Intervention in context-sensitive probabilistic Boolean networks

MOTIVATION: Intervention in a gene regulatory network is used to help it avoid undesirable states, such as those associated with a disease. Several types of intervention have been studied in the framework of a probabilistic Boolean network (PBN), which is essentially a finite collection of Boolean networks in which at any discrete time point the gene state vector transitions according to the rules of one of the constituent networks. For an instantaneously random PBN, the governing Boolean network is randomly chosen at each time point. For a context-sensitive PBN, the governing Boolean network remains fixed for an interval of time until a binary random variable determines a switch. The theory of automatic control has been previously applied to find optimal strategies for manipulating external (control) variables that affect the transition probabilities of an instantaneously random PBN to desirably affect its dynamic evolution over a finite time horizon. This paper extends the methods of external control to context-sensitive PBNs. RESULTS: This paper treats intervention via external control variables in context-sensitive PBNs by extending the results for instantaneously random PBNs in several directions. First, and most importantly, whereas an instantaneously random PBN yields a Markov chain whose state space is composed of gene vectors, each state of the Markov chain corresponding to a context-sensitive PBN is composed of a pair, the current gene vector occupied by the network and the current constituent Boolean network. Second, the analysis is applied to PBNs with perturbation, meaning that random gene perturbation is permitted at each instant with some probability. Third, the (mathematical) influence of genes within the network is used to choose the particular gene with which to intervene. Lastly, PBNs are designed from data using a recently proposed inference procedure that takes steady-state considerations into account. The results are applied to a context-sensitive PBN derived from gene-expression data collected in a study of metastatic melanoma, the intent being to devise a control strategy that reduces the WNT5A gene's action in affecting biological regulation, since the available data suggest that disruption of this influence could reduce the chance of a melanoma metastasizing.     

Bias in Markov models of disease

We examine bias in Markov models of diseases, including both chronic and infectious diseases. We consider two common types of Markov disease models: ones where disease progression changes by severity of disease, and ones where progression of disease changes in time or by age. We find sufficient conditions for bias to exist in models with aggregated transition probabilities when compared to models with state/time dependent transition probabilities. We also find that when aggregating data to compute transition probabilities, bias increases with the degree of data aggregation. We illustrate by examining bias in Markov models of Hepatitis C, Alzheimer’s disease, and lung cancer using medical data and find that the bias is significant depending on the method used to aggregate the data. A key implication is that by not incorporating state/time dependent transition probabilities, studies that use Markov models of diseases may be significantly overestimating or underestimating disease progression. This could potentially result in incorrect recommendations from cost-effectiveness studies and incorrect disease burden forecasts.     

Prediction of the ensembles of RNA secondary structures. Kinetic analysis of self-organization

A new approach to the problem of prediction of secondary structures of RNA, which is based on the kinetic analysis of self-organising molecules is proposed. Structural reconstructions that take place during formation of secondary structures are described in terms of Markov process. A set of states and probability transition were defined. Monte-Carlo methods were used to describe this process. Probability distributions of various secondary structures depending on time are given. Examples of calculations for ensembles of secondary structures of some tRNAs are described. An effective method of steady-state ensemble research, which is based on a quick RESETTING of all possible variance of the secondary structures of RNAs is given. By ascribing to each of these structures the value of probabilities as a function of free energy it was possible to obtain the Boltzmann ensemble of secondary structures.     

Uncovering and Testing the Fuzzy Clusters Based on Lumped Markov Chain in Complex Network

Identifying clusters, namely groups of nodes with comparatively strong internal connectivity, is a fundamental task for deeply understanding the structure and function of a network. By means of a lumped Markov chain model of a random walker, we propose two novel ways of inferring the lumped markov transition matrix. Furthermore, some useful results are proposed based on the analysis of the properties of the lumped Markov process. To find the best partition of complex networks, a novel framework including two algorithms for network partition based on the optimal lumped Markovian dynamics is derived to solve this problem. The algorithms are constructed to minimize the objective function under this framework. It is demonstrated by the simulation experiments that our algorithms can efficiently determine the probabilities with which a node belongs to different clusters during the learning process and naturally supports the fuzzy partition. Moreover, they are successfully applied to real-world network, including the social interactions between members of a karate club.     

A generalized mover-stayer model for panel data

A generalized mover-stayer model is described for conditionally Markov processes under panel observation. Marginally the model represents a mixture of nested continuous-time Markov processes in which sub-models are defined by constraining some transition intensities to zero between two or more states of a full model. A Fisher scoring algorithm is described which facilitates maximum likelihood estimation based only on the first derivatives of the transition probability matrices. The model is fit to data from a smoking prevention study and is shown to provide a significant improvement in fit over a time-homogeneous Markov model. Extensions are developed which facilitate examination of covariate effects on both the transition intensities and the mover-stayer probabilities.     

A method for defining steady-state unidirectional fluxes through branched chemical, osmotic and chemiosmotic reactions

A general mathematical technique is described for deriving analytical expressions and obtaining numerical solutions for the steady-state unidirectional fluxes between two chemical states via any set of intermediate states present within any hypothetical system of unbranched or branched and overlapping elementary processes. The technique is a restricted application of the theory of Markov processes with conditional probabilities being assigned to the chemical state transitions constituting the system of reactions. While, in principle, the technique requires the summation of an infinite power series of a matrix defining the conditional probabilities of single state transitions, the power series is evaluated by means of the Taylor series expansion for matrices. As this technique allows isotopic exchange velocity equations to be derived from systems of reactions in which no distinction between the labelled and unlabelled species is required it provides a distinct and independent alternative to previously proposed methods. The technique is illustrated by application to a mechanism for second-order carrier-mediated transport.     

Evidence for cooperativity between nicotinic acetylcholine receptors in patch clamp records

It is often assumed that ion channels in cell membrane patches gate independently. However, in the present study nicotinic receptor patch clamp data obtained in cell-attached mode from embryonic chick myotubes suggest that the distribution of steady-state probabilities for conductance multiples arising from concurrent channel openings may not be binomial. In patches where up to four active channels were observed, the probabilities of two or more concurrent openings were greater than expected, suggesting positive cooperativity. For the case of two active channels, we extended the analysis by assuming that 1) individual receptors (not necessarily identical) could be modeled by a five-state (three closed and two open) continuous-time Markov process with equal agonist binding affinity at two recognition sites, and 2) cooperativity between channels could occur through instantaneous changes in specific transition rates in one channel following a change in conductance state of the neighboring channel. This allowed calculation of open and closed sojourn time density functions for either channel conditional on the neighboring channel being open or closed. Simulation studies of two channel systems, with channels being either independent or cooperative, nonidentical or identical, supported the discriminatory power of the optimization algorithm. The experimental results suggested that individual acetylcholine receptors were kinetically identical and that the open state of one channel increased the probability of opening of its neighbor.     

Marginal distributions of genetic coalgebras

We consider the backward evolution of a particular type of Mendelian genetic system whose transition probabilities give place to the so-called coalgebras with genetic realization and describe the equilibrium states of such mathematical objects and therefore those of the genetic system. We exploit the relationship between the genetic coalgebras modeling the transference of the genetic inheritance and cubic stochastic matrices of type (1, 2) studying first the ergodicity of these matrices in terms of the stationary probability distributions of the bivariate Markov chains defined by their accompanying matrices. Then we apply the obtained results to describe the equilibrium states of coalgebras with genetic realization.     

A compact statistical model of the song syntax in Bengalese finch

Songs of many songbird species consist of variable sequences of a finite number of syllables. A common approach for characterizing the syntax of these complex syllable sequences is to use transition probabilities between the syllables. This is equivalent to the Markov model, in which each syllable is associated with one state, and the transition probabilities between the states do not depend on the state transition history. Here we analyze the song syntax in Bengalese finch. We show that the Markov model fails to capture the statistical properties of the syllable sequences. Instead, a state transition model that accurately describes the statistics of the syllable sequences includes adaptation of the self-transition probabilities when states are revisited consecutively, and allows associations of more than one state to a given syllable. Such a model does not increase the model complexity significantly. Mathematically, the model is a partially observable Markov model with adaptation (POMMA). The success of the POMMA supports the branching chain network model of how syntax is controlled within the premotor song nucleus HVC, but also suggests that adaptation and many-to-one mapping from the syllable-encoding chain networks in HVC to syllables should be included in the network model.     

Restricted transition probabilities and their applications to some problems in the dynamics of biological populations

In this paper a theory of a class of restricted transition probabilities is developed and applied to a problem in the dynamics of biological populations under the assumption that the underlying stochastic process is a continuous time parameter Markov chain with stationary transition probabilities. The paper is divided into three parts. Part one contains sufficient background from the theory of Markov processes to define restricted transition probabilities in a rigorous manner. In addition, some basic concepts in the theory of stochastic processes are interpreted from the biological point of view. Part two is concerned with the problem of finding representations for restricted transition probabilities. Finally, in part three the theory of restricted transition probabilities is applied to the problem of finding and analyzing some properties of the distribution function of the maximum size attained by the population in a finite time interval for a rather wide class of Markov processes. Some other applications of restricted transition probabilities to other problems in the dynamics of biological populations are also suggested. These applications will be discussed more fully in a companion paper. The research reported in this paper was supported by the United States Atomic Energy Commission, Division of Biology and Medicine Project AT(45-1)-1729.     

Markov chains: computing limit existence and approximations with DNA

We present two algorithms to perform computations over Markov chains. The first one determines whether the sequence of powers of the transition matrix of a Markov chain converges or not to a limit matrix. If it does converge, the second algorithm enables us to estimate this limit. The combination of these algorithms allows the computation of a limit using DNA computing. In this sense, we have encoded the states and the transition probabilities using strands of DNA for generating paths of the Markov chain.     

Markov chain analysis finds a significant influence of neighboring bases on the occurrence of a base in eucaryotic nuclear DNA sequences both protein-coding and noncoding

Sixty-four eucaryotic nuclear DNA sequences, half of them coding and half noncoding, have been examined as expressions of first-, second-, or third-order Markov chains. Standard statistical tests found that most of the sequences required at least second-order Markov chains for their representation, and some required chains of third order. For all 64 sequences the observed one-step second-order transition count matrices were effective in predicting the two-step transition count matrices, and 56 of 64 were effective in predicting the three-step transition count matrices. The departure from random expectation of the observed first- and second-order transition count matrices meant that a considerable sample of eucaryotic nuclear DNA sequences, both protein coding and noncoding, have significant local structure over subsequences of three to five contiguous bases, and that this structure occurs throughout the total length of the sequence. These results suggested that present DNA sequences may have arisen from the duplication, concatenation, and gradual modification of very early short sequences.     

Adaptive processing techniques based on hidden Markov models for characterizing very small channel currents buried in noise and deterministic interferences.

Techniques for characterizing very small single-channel currents buried in background noise are described and tested on simulated data to give confidence when applied to real data. Single channel currents are represented as a discrete-time, finite-state, homogeneous, Markov process, and the noise that obscures the signal is assumed to be white and Gaussian. The various signal model parameters, such as the Markov state levels and transition probabilities, are unknown. In addition to white Gaussian noise, the signal can be corrupted by deterministic interferences of known form but unknown parameters, such as the sinusoidal disturbance stemming from AC interference and a drift of the base line owing to a slow development of liquid-junction potentials. To characterize the signal buried in such stochastic and deterministic interferences, the problem is first formulated in the framework of a Hidden Markov Model and then the Expectation Maximization algorithm is applied to obtain the maximum likelihood estimates of the model parameters (state levels, transition probabilities), signals, and the parameters of the deterministic disturbances. Using fictitious channel currents embedded in the idealized noise, we first show that the signal processing technique is capable of characterizing the signal characteristics quite accurately even when the amplitude of currents is as small as 5-10 fA. The statistics of the signal estimated from the processing technique include the amplitude, mean open and closed duration, open-time and closed-time histograms, probability of dwell-time and the transition probability matrix. With a periodic interference composed, for example, of 50 Hz and 100 Hz components, or a linear drift of the baseline added to the segment containing channel currents and white noise, the parameters of the deterministic interference, such as the amplitude and phase of the sinusoidal wave, or the rate of linear drift, as well as all the relevant statistics of the signal, are accurately estimated with the algorithm we propose. Also, if the frequencies of the periodic interference are unknown, they can be accurately estimated. Finally, we provide a technique by which channel currents originating from the sum of two or more independent single channels are decomposed so that each process can be separately characterized. This process is also formulated as a Hidden Markov Model problem and solved by applying the Expectation Maximization algorithm. The scheme relies on the fact that the transition matrix of the summed Markov process can be construed as a tensor product of the transition matrices of individual processes.     

On the long-run sensitivity of probabilistic Boolean networks

Boolean networks and, more generally, probabilistic Boolean networks, as one class of gene regulatory networks, model biological processes with the network dynamics determined by the logic-rule regulatory functions in conjunction with probabilistic parameters involved in network transitions. While there has been significant research on applying different control policies to alter network dynamics as future gene therapeutic intervention, we have seen less work on understanding the sensitivity of network dynamics with respect to perturbations to networks, including regulatory rules and the involved parameters, which is particularly critical for the design of intervention strategies. This paper studies this less investigated issue of network sensitivity in the long run. As the underlying model of probabilistic Boolean networks is a finite Markov chain, we define the network sensitivity based on the steady-state distributions of probabilistic Boolean networks and call it long-run sensitivity. The steady-state distribution reflects the long-run behavior of the network and it can give insight into the dynamics or momentum existing in a system. The change of steady-state distribution caused by possible perturbations is the key measure for intervention. This newly defined long-run sensitivity can provide insight on both network inference and intervention. We show the results for probabilistic Boolean networks generated from random Boolean networks and the results from two real biological networks illustrate preliminary applications of sensitivity in intervention for practical problems.     

Markov chain analysis finds a significant influence of neighboring bases on the occurrence of a base in eucaryotic nuclear DNA sequences both protein-coding and noncoding

Summary Sixty-four eucaryotic nuclear DNA sequences, half of them coding and half noncoding, have been examined as expressions of first-, second-, or third-order Markov chains. Standard statistical tests found that most of the sequences required at least second-order Markov chains for their representation, and some required chains of third order. For all 64 sequences the observed one-step second-order transition count matrices were effective in predicting the two-step transition count matrices, and 56 of 64 were effective in predicting the three-step transition count matrices. The departure from random expectation of the observed first- and second-order transition count matrices meant that a considerable sample of eucaryotic nuclear DNA sequences, both protein coding and noncoding, have significant local structure over subsequences of three to five contiguous bases, and that this structure occurs throughout the total length of the sequence. These results suggested that present DNA sequences may have arisen from the duplication, concatenation, and gradual modification of very early short sequences.     

Sampling errors create bias in Markov models for community dynamics: the problem and a method for its solution

Repeated, spatially explicit sampling is widely used to characterize the dynamics of sessile communities in both terrestrial and aquatic systems, yet our understanding of the consequences of errors made in such sampling is limited. In particular, when Markov transition probabilities are calculated by tracking individual points over time, misidentification of the same spatial locations will result in biased estimates of transition probabilities, successional rates, and community trajectories. Nonetheless, to date, all published studies that use such data have implicitly assumed that resampling occurs without error when making estimates of transition rates. Here, we develop and test a straightforward maximum likelihood approach, based on simple field estimates of resampling errors, to arrive at corrected estimates of transition rates between species in a rocky intertidal community. We compare community Markov models based on raw and corrected transition estimates using data from Endocladia muricata-dominated plots in a California intertidal assemblage, finding that uncorrected predictions of succession consistently overestimate recovery time. We tested the precision and accuracy of the approach using simulated datasets and found good performance of our estimation method over a range of realistic sample sizes and error rates.