Signaling cascades are triggered by extra-cellular stimulation and propagate the signal to regulate transcription. Systematic reconstruction of this regulation requires pathway-targeted, informative experimental data. However, experimental design is difficult since even highly informative experiments might be redundant with other experiments. In addition, experimental outcomes vary not only between different genetic perturbations but also between the combinations of environmental stimuli.

We have developed a practical algorithmic framework that iterates design of experiments and reconstruction of regulatory relationships downstream of a given pathway. The experimental design component of the framework, called MEED, proposes a set of experiments the can be performed in the lab and given as input to the reconstruction component. Both components take advantage of expert knowledge about the signaling system under study, formalized in a predictive logical model. The reconstruction component reconciles the model predictions with the data from the designed experiments to provide a set of identified target genes, their regulators in the pathway and their regulatory mechanisms. Reconstruction based on uninformative data may lead to ambiguous conclusions about the regulation. To avoid ambiguous reconstruction, MEED designs experiments so as to maximize diversity between the predicted expression profiles of genes regulated through different mechanisms.

MEED has several important benefits and advantages over extant experimental design approaches: First, it considers potential dependencies between the suggested experiments, making it possible to design and perform in parallel a set of informative, non-redundant experiments. Second, MEED optimizes not only the required genetic perturbations, but also the combination of environmental stimuli that should trigger the system. Finally, by using only the model predictions, MEED has the ability to choose experiments without access to high-throughput experimental data.

Our framework was extensively analyzed and applied on random models as well as the model of interconnected osmotic stress and pheromone pathways in Saccharomyces cerevisiae. In comparison to other approaches, MEED allowed to provide significantly less ambiguous conclusions about the regulation in this system.