Optimal Inference of Asynchronous Boolean Networks

The network inference problem arises in biological research when one wishes to explain a phenotype using a network of interactions between molecules. The diverse nature of the data and nonlinear dynamics of the network pose significant challenges in choosing the best model. In addition to balancing fit and model size, computational efficiency must be considered. The latter constitutes a central consideration for the researcher since underlying the measurements, which are affected by experimental noise, there is a complex computational mechanism that may be asynchronous and is inherently hard to identify. To address these challenges, we present a novel approach that uses algorithmic complexity to infer an asynchronous Boolean network model from experimental data. We present an algorithm that is optimal within this framework and allows for asynchronicity in network dynamics. Results are described for real data, a literature-derived network and random networks.