Boolean Network Modeling

A Boolean network is specified by a set of nodes, and for each node the Boolean logic by which it changes its values as a function of a subset of the nodes.  Models such as Boolean Circuits and Cellular Automata are special cases of Boolean networks.  In Bioinformatics, we are interested in Boolean networks as a model for Gene Regulatory Network.  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 did 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 an incoming edge to a node we can potentially add N-1 different networks, where N is the number of nodes, because initially there are N-1 choice 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 can be fitted.  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 can be fitted.  The optimization problem of minimizing the sum of these bits is computationally hard and there are several approaches to address it.  The MEDSI concept is based on Kolmogorov Complexity applied to Boolean network inference with noisy trajectories.  In a recent paper, we described a 0/1 Integer Linear Programming approach and heuristics that can speed it up.

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 (Conference)

Computing Minimal Boolean Models of Gene Regulatory Networks (preprint)

Journal of Computational Biology (submitted: April 11 2023 ; Accepted: September 28 2023)