Optimal Inference of Asynchronous Boolean Networks

Abstract 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 size, computational efficiency must be considered. Importantly, underlying the measurements, which are affected by experimental noise, there is a complex computational mechanism that is inherently hard to identify. To address these difficulties, we present a novel approach that uses algorithmic complexity to infer a Boolean network model from experimental data. We present an algorithm that is optimal within this framework and allows for asynchronicity network 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. Competing Interest Statement The authors have declared no competing interest. Footnotes Revised according to reviewer comments - Added computational complexity section, replaced simulation section, added more discussion of several topics and applied editing comments