Optimal Inference of Asynchronous Boolean Network Models

The network inference problem arises in biological research when one needs to quantitatively choose the best protein-interaction model for explaining a phenotype.  The diverse nature of the data and nonlinear dynamics pose significant challenges in the search for the best methodology.  In addition to balancing fit and model complexity, computational efficiency must be considered.  In this paper, we present a novel approach that finds a solution that fits the observed dataset and otherwise a minimal number of unobserved datasets.  We present algorithms for computing Boolean networks that optimally satisfy this criterion, and allow for asynchronicitynetwork dynamics.  Furthermore, we show that using our methodology a solution to the pseudo-time inference problem, which is pertinent to the analysis of single-cell data, can be intertwined with network inference.  Results are described for real and simulated datasets.