Boolean Network Modeling

A Boolean network is specified by a set of nodes and Boolean logic which dictates how the Boolean value of each nodes changes as a function of the Boolean values of other nodes.  The state of the network , i.e. the Boolean values of all the nodes taken together, corresponds to a biological condition.   An edge from node u to node v indicates that the Boolean value of node v affects the Boolean value of node v.  

Given a set of nodes and an experimental measurement of their trajectory, one seeks to recover the network that generated the trajectory, and recover the trajectory without experimental noise. 

If the trajectory does not contain noise, then we would just seek the network with the shortest encoding.  The number of bits used in the encoding tells us how many networks could be created using the parameters that we used.  For example, by adding the first incoming edge to a node we can potentially add N different networks, where N is the number of nodes, because initially there are N choices of a source node.  Equivalently,  we are adding log2(N) bits to the encoding.  Each bit doubles the number of possible networks, and consequently the number of trajectories that are associated with them.  So the shorter the encoding, the less likely we are to select a network that randomly fits a given trajectory.  

In practice, however, measured trajectories always contain noise, represented as bits that don't match the trajectory of the fitted network.  We introduced the Minimal Edit Distance from a State of Ignorance (MEDSI) criterion, which minimizes the sum of network encoding and trajectory error bits.  Like a network encoding bit, adding a trajectory error bit to the model doubles the number of trajectories that are associated with it.  The optimization problem of minimizing the sum of these bits is computationally hard.  The links below describe an exact solution based on ILP and heuristics that can be used to speed up the computation.

Publications:

Constructing logical models of gene regulatory networks by integrating transcription factor-DNA interactions with expression data: an entropy-based approach 

Computing Minimal Boolean Models of Gene Regulatory Networks 

Optimal Inference of Asynchronous Boolean Network Models 

Software:

https://www.github.com/karleg/MEDSI