Experimental design schemes for learning Boolean network models

Abstract

Motivation: A holy grail of biological research is a working model of the cell. Current modeling frameworks, especially in the protein-protein interaction domain, are mostly topological in nature, calling for stronger and more expressive network models. One promising alternative is logic-based or Boolean network modeling, which was successfully applied to model signaling regulatory circuits in human. Learning such models requires observing the system under a sufficient number of different conditions. To date, the amount of measured data is the main bottleneck in learning informative Boolean models, underscoring the need for efficient experimental design strategies.

Results: We developed novel design approaches that greedily select an experiment to be performed so as to maximize the difference or the entropy in the results it induces with respect to current best-fit models. Unique to our maximum difference approach is the ability to account for all (possibly exponential number of) Boolean models displaying high fit to the available data. We applied both approaches to simulated and real data from the EFGR and IL1 signaling systems in human. We demonstrate the utility of the developed strategies in substantially improving on a random selection approach. Our design schemes highlight the redundancy in these datasets, leading up to 11-fold savings in the number of experiments to be performed.

Availability and implementation: Source code will be made available upon acceptance of the manuscript.

Fig. 1.

Overview of the experiment learning algorithm. We start from an ILP (Sharan and Karp, 2012) that learns a Boolean network model M whose readouts have OPT disagreements with the experimental data. In our formulation, this program is duplicated so that two models M₁ and M₂ are learned simultaneously. The models are further constrained so that: they both have at most OPT disagreements with the experimental data and are therefore optimal and that they both simulate an unknown experiment $\widehat{e}$. The objective optimizes the difference between the readouts of the models ($r_{M_1,\widehat{e}},r_{M_2,\widehat{e}}$, resp.) as per Equation (2)

Fig. 2.

Runtime comparison. A comparison of the running times of the maximum difference and maximum entropy approaches. Running times are given on two datasets (EGFR and IL1) when computing a single experiment to be conducted as a function of the number of available optimal models

Fig. 3.

Sensitivity to the number of available models. The estimation of entropy was dependent on the number of available models. In contrast, the maximum difference learning algorithm optimized over all candidate models. In both panels, the x-axis denotes the number of available models for entropy estimation, and the y-axis denotes the third quartile of the number of experiments required to obtain an optimal model (lower is better). Error bars denote standard error. (A) Simulation with EFGR signaling. (B) simulation with IL1 signaling

Fig. 4.

Sensitivity to the number of unknown functions. Increasing the number of unknown functions led to increment in the number of experiments that are required to uncover the underlying model in all but the maximum difference strategy, which retained an almost constant performance. In both panels, the x-axis denotes the number of unknown functions, and the y-axis denotes the third quartile of the number of experiments required to obtain an optimal model (lower is better). Error bars denote standard error. (A) Simulation with EGFR signaling. (B) Simulation with IL1 signaling

Fig. 5.

Performance evaluation on real data. The x-axis denotes the number of initial experiments, and the y-axis denotes the third quartile of the number of additional experiments required to reconstruct a model fitting the data as well as a model obtained from the all the available experimental data. (A) Results on the EGFR system. (B) Results on the IL1 system