13 February 2014, 14:15

**Ernst-Abbe-Platz 2, seminar room 3423**

**Detecting and Removing Inconsistencies Between Experimental Data and Signaling Network Topologies Using Integer Linear Programming**

Dr.- Ing. Steffen Klamt

(Max Planck Institute for Dynamics of Complex Technical Systems, Magdeburg, Germany)

Cross-referencing experimental data with our current knowledge of signaling network topologies is one central goal of mathematical modeling of cellular signal transduction networks. We present a new methodology for data-driven interrogation and training of signaling networks. While most published methods for signaling network inference operate on Bayesian, Boolean, or ODE models, our approach uses integer linear programming (ILP) on interaction graphs to encode constraints on the qualitative behavior of the nodes. These (sign consistency) constraints are posed by the network topology and their formulation as ILP allows us to predict the possible qualitative changes (up, down, no change) of the activation levels of the nodes for a given stimulus. We introduce four basic operations to detect and remove inconsistencies between measurements and predicted behavior: (1) find a topology-consistent explanation for responses of signaling nodes measured in a stimulus-response experiment (if none exists, find the closest explanation); (2) determine a minimal set of nodes whose state need to be corrected to make an inconsistent scenario consistent; (3) determine the optimal subgraph of the given network topology which can best reflect measurements from a set of experimental scenarios; (4) find possibly missing edges that would improve the consistency of the graph with respect to a set of experimental scenarios the most.

The applicability of the proposed approach is demonstrated by interrogating a manually curated interaction graph model of EGFR/ErbB signaling against a library of high-throughput phosphoproteomic data measured in primary hepatocytes. Our approach delivers direct conclusions on edges that are likely inactive or missing in hepatocytes relative to canonical pathway maps.

Our framework is highly flexible and the underlying model requires only easily accessible biological knowledge. All related algorithms were implemented in a freely available toolbox (SigNetTrainer) making it an appealing approach for various applications.

Reference

Melas IN, Samaga R, Alexopoulos LG, Klamt S (2013) Detecting and Removing Inconsistencies between Experimental Data and Signaling Network Topologies Using Integer Linear Programming on Interaction Graphs. *PLoS Computational Biology* **9**: e1003204.