Jacques Nicolas

Martin Gebser

Roland Kaminski

Sven Thiele

Alexander Bockmayr

Axel Von Kamp

David Gilbert

Heike Siebert

Regina Samaga

Steffen Klamt

Gregory Batt

Mireille Ducasse

Christine Froidevaux

Joachim Selbig

Keywords: systems biology, logical signaling networks, answer set programming ix

First of all, I would like to thank Anne Siegel and Torsten Schaub, my two thesis advisors. Both Anne and Torsten, have trusted on

More generally, the inference of Boolean networks from time-series gene expression data has been addressed by several authors under different hypotheses and methods [START_REF] Liang | REVEAL, a general reverse engineering algorithm for inference of genetic network architectures[END_REF][START_REF] Akutsu | Inferring qualitative relations in genetic networks and metabolic pathways[END_REF][START_REF] Ideker | Discovery of regulatory interactions through perturbation: inference and experimental design[END_REF][START_REF] Lähdesmäki | On learning gene regulatory networks under the Boolean network model[END_REF]. Recently, some of these methods have been compared in [START_REF] Berestovsky | An evaluation of methods for inferring boolean networks from time-series data[END_REF]. Nonetheless, overall, our work presents some significant differences. To start with, all of them are focused on gene regulatory networks and gene expression time-series data, whereas we work on signaling transduction networks and phosphorylation activities at a pseudo-steady state. Further, they work only with Boolean experimental observations which would correspond to adopt a binary discretization scheme in our framework. Moreover, except for the so-called Best-Fit Extension Problem [START_REF] Lähdesmäki | On learning gene regulatory networks under the Boolean network model[END_REF], they look for Boolean networks fully consistent with the time-series Boolean data. Meanwhile, herein we consider an objective function which describes the goodness of the model based on the numerical data that is subsequently optimized. Finally, all these contributions focus on a "local" inference in the following sense. They aim at learning the Boolean function for each node based on (local) input-output behaviors for such node. In contrast, our learning is based on (global) behaviors over the input-output layers in a network containing non-controllable/non-observable species.

Importantly, in contrast to the standard approach of modeling a signaling network by means of one logical model only, we show that there may be several thousands of feasible models. This fact motivates the second problem we address in this thesis which consists of finding an optimal experimental design in order to discriminate among all feasible logical networks. Broadly speaking, experimental design for model discrimination consists of finding an input that maximize the difference of the outputs of the rival models. In this context, we aim at

Résumé

Décrypter le fonctionnement des réseaux biologiques est l'une des missions centrales de la biologie des systèmes. En particulier, les réseaux de signalisation sont essentiels pour la compréhension de la réponse cellulaire à des perturbations externes et internes. Notamment, ces réseaux sont impliqués en santé humaine et leur contrôle a un impact sur l'identification et la caractérisation de cibles de médicaments. Pour affronter la complexité de ces réseaux, modélisations mathématiques et informatiques sont nécessaires. D'une part, les approches mathématiques ou quantitatives permettent une analyse fine mais sont généralement limitées à des réseaux relativement petits. D'autre part, la modélisation informatique ou qualitative permet de traiter de grands réseaux, en s'appuyant sur d'autres représentations abstraites. Parmi les différentes approches qualitatives, les modéles logiques sont relativement simples, mais en mesure de capturer des comportements intéressants et pertinents dans la cellule. Dans ce cadre, les chercheurs essaient généralement de modéliser un système biologique particulier, en utilisant un seul modèle logique. Ensuite, des analyses dynamiques et structurales sont menées sur ce modèle. Toutefois, en raison de plusieurs facteurs, tels que l'observabilité limitée ou de l'incertitude dans les mesures expérimentales, il a été montré qu'un tel modèle est en pratique non identifiable dans de nombreux cas. En effet, les connaissances biologiques et les hypothèses découlant de ces analyses sont susceptibles d'être incomplètes, erronées, ou biaisées par des décisions prises au moment de l'identification ou de la construction du modèle.

Dans cette thèse, nous proposons un cadre de modélisation informatique afin d'obtenir des découvertes plus robustes dans le cadre de réseaux de signalisation modélisés sous forme logique. Plus précisément, nous nous concentrons sur la modélisation de la réponse des réseaux logiques au moyen du raisonnement automatisé à l'aide de Programmation par Ensembles-Réponses (Answer Set Programming, ASP). De manière générale, ASP fournit un langage déclaratif pour la modélisation de divers problèmes de représentation des connaissances et de raisonnement. L'idée de base de ASP est d'exprimer un problème sous la forme d'un programme logique de sorte que les modèles de sa représentation, les answer sets (ensemblesréponses), fournissent les solutions au problème initial. En outre, différents solveurs disponibles pour ASP offrent plusieurs modes de raisonnement pour l'évaluation de la multitude de réponses : énumération régulière et projective, intersection, union, et optimisation multicritères. Par conséquent, en s'appuyant sur la richesse de son langage de modélisation et de ses capacités de résolution très efficaces, nous utilisons ASP pour répondre à trois problèmes difficiles dans le contexte des réseaux logiques de signalisation.

xi Résumé Premièrement, nous abordons le problème consistant à apprendre, à partir d'un graphe d'interaction et d'observations expérimentales, les réseaux booléens qui décrivent la réponse immédiate du système. Aujourd'hui, pour certains systèmes biologiques, un graphe des interactions causales qui décrivent un réseau de signalisation à grande échelle peut être extrait de bases de données publiques [START_REF] Guziolowski | Automatic generation of causal networks linking growth factor stimuli to functional cell state changes[END_REF] ou être appris à l'aide de méthodes statistiques et de données expérimentales [START_REF] Sachs | Causal protein-signaling networks derived from multiparameter single-cell data[END_REF]. Cependant, les relations fonctionnelles dans les réseaux de signalisation ne peuvent pas être capturées seulement à l'aide d'analyse de graphes [Klamt et al., 2006b]. Dans ce contexte, les auteurs de [START_REF] Saez-Rodriguez | Discrete logic modelling as a means to link protein signalling networks with functional analysis of mammalian signal transduction[END_REF] ont proposé une méthode pour apprendre, à partir d'un graphe d'interaction et des activités de phosphorylation mesurées à un état pseudo-stationnaire de la cellule, les modèles logiques booléens de la réponse précoce compatible avec les données expérimentales. A l'origine, un algorithme génétique a été proposé pour résoudre le problème d'optimisation sous-jacent, et un logiciel a été fourni : CellNOpt [START_REF] Terfve | CellNOptR: a flexible toolkit to train protein signaling networks to data using multiple logic formalisms[END_REF]. Cependant, les méthodes de recherche stochastiques ne peuvent pas caractériser les modèles intégralement : ces approches sont intrinsèquement incapables non seulement de fournir un ensemble complet de solutions, mais aussi de garantir qu'une solution optimale a été trouvée. Certaines variations de ce problème ont été abordées avec une approche de programmation linéaire [Mitsos et al., 2009, Sharan and[START_REF] Sharan | Reconstructing Boolean models of signaling[END_REF]. En dépit de leur succès à surmonter certaines insuffisances des algorithmes génétiques, comme la performance et la preuve de l'optimalité globale, l'énumération de toutes les solutions optimales (ou presque optimales) n'a pas été étudiée dans ces travaux. En combinant à la fois l'optimisation multi-critères et l'énumération fournie par ASP, nous montrons dans cette thèse qu'il est possible d'énumérer tous les modèles logiques expliquant les données expérimentales de manière sous-optimale.

Plus généralement, l'inférence de réseaux booléens à partir de données de séries temporelles d'expression génique a été abordée par plusieurs auteurs sous différentes hypothèses [START_REF] Liang | REVEAL, a general reverse engineering algorithm for inference of genetic network architectures[END_REF][START_REF] Akutsu | Inferring qualitative relations in genetic networks and metabolic pathways[END_REF][START_REF] Ideker | Discovery of regulatory interactions through perturbation: inference and experimental design[END_REF][START_REF] Lähdesmäki | On learning gene regulatory networks under the Boolean network model[END_REF]. Récemment, certaines de ces méthodes ont été comparées dans [START_REF] Berestovsky | An evaluation of methods for inferring boolean networks from time-series data[END_REF]. Cependant, globalement, notre travail présente des différences significatives. Pour commencer, les références précédentes sont toutes concentrées sur les réseaux de régulation de gènes et des données de séries temporelles d'expression génique, tandis que nous travaillons sur la signalisation des réseaux de transduction et à l'aide de mesures d'activités de phosphorylation à un état pseudo-stationnaire. En outre, les approches d'apprentissage de réseaux fonctionnent uniquement avec des observations expérimentales booléennes, ce qui correspondrait à adopter un schéma de discrétisation binaire dans notre cadre. De plus, sauf pour le Best-Fit Extension problem [START_REF] Lähdesmäki | On learning gene regulatory networks under the Boolean network model[END_REF], les recherches consistent à identifier des réseaux booléens entièrement compatibles avec les données booléennes. Au lieu de cela, nous considérons ici une fonction objectif qui décrit la correction du modèle basée sur des données quantitatives. C'est cette fonction objectif numérique qui est ensuite optimisée. Enfin, toutes les contributions mentionnées ci-dessus portent sur une inférence "locale" dans le sens suivant : elles visent à l'apprentissage de la fonction booléenne pour chaque noeud sur la base des comportements entrées-sorties (locales) pour un tel noeud. En revanche, notre méthode d'apprentissage est basée sur les comportements (globaux) d'entrée-sortie dans un xii Résumé réseau contenant des espèces non-controlables ou non-observables.

A la différence des approches classiques de modélisation d'un réseau de signalisation par un modèle logique seulement, on montre ainsi qu'il peut y avoir plusieurs milliers de modèles qui expliquent tous de manière sous-optimale les données entrées-sorties. Ce fait motive le deuxième problème que nous abordons dans cette thèse qui consiste à trouver un plan d'expérience optimal afin de discriminer les réseaux logiques possibles. D'une manière générale, le plan expérimental pour discriminer une famille de modèles consiste à trouver une entrée qui maximise la différence des sorties des modèles concurrents. Dans ce contexte, nous nous efforçons de trouver le nombre minimum de conditions expérimentales permettant de discriminer chaque paire de comportements entrée-sortie. En outre, nous adoptons un critère introduit dans une approche de modélisation quantitative [START_REF] Mélykúti | Discriminating between rival biochemical network models: three approaches to optimal experiment design[END_REF]. Dans ce travail, les auteurs font valoir que, en principe, en maximisant la différence entre les sorties de deux modèles différents, on garantit que même une mesure bruitée a une bonne chance de faire la distinction entre eux. Nous adaptons cette idée dans le contexte de nos modèles logiques booléens et les comportements logiques entrées-sorties. Aussi, nous cherchons à minimiser la complexité des expériences en termes de nombre de stimuli et d'inhibitions. Encore une fois, en s'appuyant sur les capacités d'optimisation multi-critères de l'ASP, nous pouvons identifier la meilleure série d'expériences afin d'affiner la famille de modèles disponibles à un moment donné.

La plupart des travaux antérieurs sur la conception de plans expérimentaux reposent sur des modélisations (semi-) quantitatives [START_REF] Kremling | A benchmark for methods in reverse engineering and model discrimination: problem formulation and solutions[END_REF][START_REF] Vatcheva | Experiment selection for the discrimination of semi-quantitative models of dynamical systems[END_REF][START_REF] Mélykúti | Discriminating between rival biochemical network models: three approaches to optimal experiment design[END_REF][START_REF] Stegmaier | Robust optimal design of experiments for model discrimination using an interactive software tool[END_REF][START_REF] Busetto | Near-optimal experimental design for model selection in systems biology[END_REF]. Dans le contexte de la modélisation symbolique, les approches existantes sont moins établies. Il est intéressant de noter que, en général, les modèles formels s'appuient sur des fonctions de prédiction qui peuvent être utilisées pour générer des hypothèses testables et réaliser les expériences. Quand même, nous nous référons ici au problème spécifique consistant à proposer automatiquement de nouvelles expériences qui permettent de discriminer une famille de modèles. À ce jour, cette question a été abordée sous différentes hypothèses de modélisation et avec différentes méthodes [START_REF] Ideker | Discovery of regulatory interactions through perturbation: inference and experimental design[END_REF][START_REF] Yeang | Validation and refinement of gene-regulatory pathways on a network of physical interactions[END_REF][START_REF] Barrett | Iterative reconstruction of transcriptional regulatory networks: an algorithmic approach[END_REF][START_REF] Szczurek | Elucidating regulatory mechanisms downstream of a signaling pathway using informative experiments[END_REF][START_REF] Sparkes | Towards robot scientists for autonomous scientific discovery[END_REF]. Pourtant, leur application pratique reste une question ouverte. Une approche particulièrement intéressante est celle présentée dans [START_REF] Sharan | Reconstructing Boolean models of signaling[END_REF]. Dans ce travail, les auteurs ont étudié une variante de notre problème d'apprentissage par le biais de la programmation linéaire. Aussi, ils ont esquissé un algorithme pour trouver l'expérience la plus informative permettant de discriminer des modèles booléens rivaux. Cependant, aucune application n'a été fournie. Dans l'ensemble, par rapport à toutes les contributions cités précédemment, notre travail se positionne comme suit. Sauf pour [START_REF] Szczurek | Elucidating regulatory mechanisms downstream of a signaling pathway using informative experiments[END_REF], les approches précédentes visent à sélectionner exactement une expérience à chaque itération. Par conséquent, c'est seulement après que l'expérience proposée a été effectuée dans le laboratoire et que les modèles ont été (partiellement) discriminés, qu'une une autre expérience peut être conçue. En revanche, mais de façon similaire à [START_REF] Szczurek | Elucidating regulatory mechanisms downstream of a signaling pathway using informative experiments[END_REF], nous nous efforçons de trouver d'un seul coup le plus petit nombre d'expériences pour discriminer de manière optimale tous les modèles à la fois. De plus, motivé par [START_REF] Mélykúti | Discriminating between rival biochemical network models: three approaches to optimal experiment design[END_REF], une caractéristique de notre travail est xiii l'emploi d'un critère d'optimalité basé sur la maximisation de la somme des différences deux à deux. En général, les méthodes précédentes ont adopté une approche basé sur la théorie de l'information où le critère principal est donné au moyen de ce qu'on appelle l'entropie de Shannon [START_REF] Shannon | A mathematical theory of communication[END_REF].

En principe, l'itération sur la boucle de modélisation et d'expérimentation donnera des modèles logiques plus précis et réduira la taille de la famille de modèles compatibles. Cependant, il peut y avoir à la fin plusieurs modèles qui ne peuvent être discriminés à l'aide des capacités expérimentales disponibles. Dans ce cas, au lieu de sélectionner un seul modèle, nous visons à raisonner sur le comportement de l'ensemble d'entre eux. Ainsi, ceci nous conduit à étudier un troisième problème qui consiste à trouver l'ensemble des stratégies d'intervention minimale afin de contrôler la réponse du système biologique. Plus précisément, nous cherchons à déterminer les ensembles d'activations et inhibitions forçant un ensemble d'espèces cibles à parvenir à un état d'équilibre attendu, dans le cadre de différents scénarios, et ceci pour tous les réseaux logiques d'une famille donnée. Malheureusement, les algorithmes dédiés introduits dans [START_REF] Samaga | Computing combinatorial intervention strategies and failure modes in signaling networks[END_REF] sont gourmands en calculs, en raison des mécanismes hautement combinatoires dans les réseaux logiques. Par conséquent, ces algorithmes sont limités à calculer de petits ensembles d'intervention et ne passent pas à l'échelle sur des réseaux de grande taille. Il faut noter que, en général, plusieurs interventions (ou mutations) sont nécessaires pour faire face à la robustesse et à la complexité cellulaire [START_REF] Stelling | Robustness of cellular functions[END_REF]. Par ailleurs, les interventions identifiées doivent permettre au système de réaliser les objectifs attendus dans chaque réseau logique possible. Du fait de ces limitations, il est difficile de prouver que les solutions identifiées sont biologiquement robustes vis-à-vis de petites variations du système ou de son environnement. Par contre, en raisonnant sur une famille de réseaux logiques, nous espérons trouver des stratégies d'intervention robustes.

Plus généralement, le problème de l'identification des acteurs-clé dans les réseaux logiques de signalisation a été abordé dans [START_REF] Li | Predicting essential components of signal transduction networks: A dynamic model of guard cell abscisic acid signaling[END_REF][START_REF] Abdi | Fault diagnosis engineering of digital circuits can identify vulnerable molecules in complex cellular pathways[END_REF], Wang and Albert, 2011[START_REF] Layek | Cancer therapy design based on pathway logic[END_REF]. Contrairement à notre travail, ces contributions ont plutôt mis l'accent sur la prédiction de ce qui se passerait si certaines molécules ne se comportaient pas comme attendu. À cette fin, les auteurs de [START_REF] Li | Predicting essential components of signal transduction networks: A dynamic model of guard cell abscisic acid signaling[END_REF][START_REF] Abdi | Fault diagnosis engineering of digital circuits can identify vulnerable molecules in complex cellular pathways[END_REF][START_REF] Layek | Cancer therapy design based on pathway logic[END_REF] s'appuient sur le diagnostic de fautes dans des circuits pour identifier les molécules vulnérables qui jouent un rôle crucial dans le dysfonctionnement des réseaux de signalisation. Dans ce contexte, une grande vulnérabilité suggère que, avec une forte probabilité, le réseau de signalisation ne fonctionne pas correctement si cette molécule particulière est dysfonctionnelle ("stuck-at-0" ou "stuck-at-1" en terminologie des circuits digitaux). Il est intéressant de noter que, en raison des limites de calcul, en général, les auteurs ont limité leurs études à de petits nombres de défauts simultanés. L'approche présentée dans [START_REF] Wang | Elementary signaling modes predict the essentiality of signal transduction network components[END_REF] ne s'appuie pas sur des circuits digitaux, mais plutôt sur la théorie des graphes. Dans ce travail, les auteurs ont proposé deux mesures de connectivité basées sur les chemins les plus courts, ou sur les dénommés elementary signaling modes. Puis, en utilisant ces mesures, leur méthode fournit un classement des noeuds via les effets de la perte de connectivité entre les entrées et les sorties du réseau. Il faut noter que, malgré les réglages spécifiques pour chaque problème et les approches informatiques de ces contributions, tous ont considéré un seul réseau logique xiv Résumé pour décrire le système. Or, comme nous l'avons mentionné plus haut, nous avons montré qu'il peut exister une famille de modèles importante qui peuvent tous expliquer aussi bien les données expérimentales. Les interventions qui permettent de réaliser certains objectifs à l'aide d'un réseau donné sont susceptibles d'échouer dans une autre réseau qui peut décrire le système tout aussi bien. Être capable, comme nous le faisons, de répondre à la même question sur le calcul des interventions permettant de forcer une réponse attendue, mais pour une famille de modèles, conduit finalement à des stratégies plus robustes.

Nous illustrons les approches répondant à chacun des problèmes mentionnés ci-dessus, en considérant un exemple de voies de signalisation dans des cellules hépatiques humaines et des données expérimentales disponibles publiquement. Dans tous les cas, les performances de calcul sont significativement améliorées par rapport à des algorithmes dédiés pour résoudre les mêmes problèmes. Mais encore plus important, la nature exhaustive d'ASP nous permet d'énumérer toutes les solutions admissibles qui pouvaient être omises lors de l'utilisation des méthodes existantes. Aussi, grâce à la richesse de son langage de modélisation et ses méthodes de résolution efficaces, ASP permet de raisonner sur un ensemble de réseaux logiques pour réaliser des découvertes plus robustes.

Au final, la contribution de cette thèse concerne trois axes différents. Du côté de la modélisation, le cadre proposé introduit une approche de modélisation formelle unifiée pour le raisonnement sur les réseaux logiques de signalisation. Sur le plan informatique, cette thèse illustre le potentiel d'ASP pour traiter des problèmes combinatoires difficiles de recherche et d'optimisation liés à la modélisation qualitative des systèmes biologiques. Enfin, du côté applicatif, nous avons conçu un logiciel fournissant une interface qui rend transparente l'utilisation d'ASP par des utilisateurs biologistes ou modélisateurs, et peut être intégré dans d'autres outils disponibles pour la simulation et l'analyse des modèles logiques.

Pour finir, le travail présenté dans cette thèse a soulevé plusieurs questions intéressantes pour de futures recherches. En particulier, nos travaux ont ouvert la voie à une caractérisation exhaustive des modèles logiques possibles pour un système donné. Maintenant, nous devons développer un cadre de modélisation approprié pour interpréter et tirer partie de cette caractérisation. Ce cadre de modélisation doit être nécessairement guidé par les technologies expérimentales disponibles, qui nous permettent de confirmer ou d'infirmer les hypothèses générées. Par exemple, les essais phospho-protéomiques comme celui utilisé pour l'apprentissage de réseaux sont réalisés sur une population de cellules. On ne sait donc pas comment interpréter la multitude de réseaux logiques et leurs comportements d'entrée-sortie au niveau d'une cellule individuelle. Etant donné l'existence de plusieurs comportements d'entrée-sortie logiques qui correspondent à différents mécanismes internes, nous devons élucider si ces mécanismes sont un simple artefact des modélisations logiques, ou s'ils représentent réellement les mécanismes moléculaires variables qui à leur tour apparaissent plus ou moins souvent au sein de chaque cellule ou à une échelle de la population. De plus, en dépit de l'incertitude intrinsèque dans les systèmes biologiques, il est encore assez difficile d'évaluer la quantité de bruit dans les mesures et comment cela influe sur nos modèles mathématiques ou formels. Cela soulève la question de l'identifiabilité et dans quelle mesure les nouvelles expériences peuvent permettre de construire des modèles logiques plus fins. La méthode de conception xv Résumé de plans expérimentaux que nous proposons nécessite d'être validée et pourrait représenter un premier pas dans cette direction. Enfin, il serait particulièrement intéressant d'explorer plus notre approche permettant de trouver des stratégies d'intervention en raisonnant sur un ensemble de réseaux logiques. En principe, une telle approche devrait permettre de tirer des enseignements sur l'incertitude et la non-identifiabilité des systèmes étudiés. Cependant, nous devons à nouveau élucider si une telle famille de réseaux décrit des voies alternatives au sein d'une seule cellule ou à l'échelle de la population. Enfin, toutes ces questions s'intègrent dans un cadre de modélisation intégratif qui se positionne à différentes échelles de temps et de causalité. À cette fin, le développement de systèmes de raisonnement hybrides tirant parti de l'expressivité de plusieurs technologies et approches de modélisation apparaît comme une piste très prometteuse pour de futures recherches en informatique. 4.1 Representative Boolean logic models (V, φ 1 ), (V, φ 2 ), and (V, φ 3 ) for 3 different logical input-output behaviors. The correspoinding mappings are:

φ 1 = {d � → a ∨ ¬c, e � → b ∨ c, f � → d ∧ e, g � → e ∧ ¬c}, φ 2 = {d � → a ∨ b, e � → b ∨ c, f � → d ∧ e, g � → e ∧ ¬c}, and
φ 3 = {d � → a, e � → b ∨ c, f � → d ∧ e,

5.1

Alternative logical networks (V, φ 1 ), (V, φ 2 ), (V, φ 3 ), (V, φ 4 ), and (V, φ 5 ) describing a given system equally well. The correspoinding mappings are: M 5306 (green bars), have the same strategies and thus we plot them together. .

φ 1 = {d � → a ∨ ¬c, e � → b ∨ c, f � → d ∧ e, g � → e ∧ ¬c}, φ 2 = {d � → a ∨ (b ∧ ¬c), e � → b ∨ c, f � → d ∧ e, g � → e ∧ ¬c}, φ 3 = {d � → a, e � → b ∨ c, f � → d ∧ e, g � → e ∧ ¬c}, φ 4 = {d � → a ∨ b, e � → b ∨ c, f � → d ∧ e, g � → e ∧ ¬c}, and
φ 5 = {d � → a ∨ b ∨ ¬c, e � → b ∨ c, f � → d ∧ e, g � → e ∧ ¬c}.

5.

3 Robust intervention strategies. We plot the 14 intervention strategies found with respect to M 16 and M 144 . Each path from the node "SCENARIOS CONSTRAINTS" to the node "SCENARIOS GOALS", describes a different strategy where species are intervened according the their coloring: red for inhibitions and green for activations. Out of the 14 strategies only 6, the ones highlighted with stronger red, are conserved among all logical networks in M 5306 . . . . . . . . . . . . . . .

C = {i 1 � → t , i 2 � → f , g � → f } and initial assignment A with either A = A u or A = A f . . . . 17
3.1 Enumeration of (nearly) optimal Boolean logic models. We report for each tolerance T , the number of Boolean logic models found M , the CPU time used by the ASP solver t enum , the range of MSEs Θ mse k and Θ mse , the range of sizes Θ si ze , the number of logical input-output behaviors B and the CPU time used by the script implementing Algorithm 1. 41

Fixpoints

F j i for Ω (V,φ j | C i ) reachable from A f with j = 1, 2, 3 and i = 1, 2. Logical networks (V, φ j ) are shown in Figure 4.1 whereas C 1 = {b � → t } and C 2 = {b � → t , c � → t }. . . . . . . 49 4.
2 Input-output discrimination over the search space of experiments C (3,2). We report for each set of input-output behaviors B m from Table 3.1, the minimum number of experimental conditions required to discriminate between every pair of behaviors (ε), the time for finding such a minimum (t ε ), the maximum number of pairwise differences (Θ diff ), the mean and standard deviation pairwise differences (µ diff and σ diff ), the minimum number of stimuli (Θ V S ), the minimum number of inhibitors (Θ V K ), and the time for finding an optimum experimental condition (t opt ). Also, in parentheses, we report overall CPU time for the 8 threads. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 58 5.1 Enumeration of all inclusion-minimal intervention strategies up to a given size k = 2, 3, 4, 5, or unbounded (∞). For each set of logical networks (M i ), we report the number of intervention strategies (I ) and the CPU time (t enum ). Also, in parentheses, we report the time strictly during solving. . . . . . . . . . . . . . . . 71 xxv 1 Introduction

Systems biology and signaling networks

Systems biology

Systems biology is an interdisciplinary field aiming at the investigation and understanding of biology at a system and multi-scale level [START_REF] Ideker | A new approach to decoding life: systems biology[END_REF][START_REF] Kitano | Systems biology: a brief overview[END_REF]. After biological entities have been identified in a specific environment, it remains to elucidate how they interact with each other in order to carry out a particular biological function. Thus, rather than focusing on the components themselves, one is interested on the nature of the links that connect them and the functionalities arising from such interactions. Notably, advances on high-throughput experimental technologies have been one of the main driving forces of systems biology. Such technologies have allowed biologists to study biological systems as a whole rather than as individual components. Nevertheless, the "reductionist" approach of molecular biology has been fundamental for the construction of the large catalogues of biological entities available nowadays. In fact, some authors have considered systems biology not as a new field of research but instead, as an approach to biomedical research combining "reductionist" and "integrationist" techniques [START_REF] Kohl | Systems biology: An approach[END_REF].

As it is often the case, the application of novel technologies has led to profound conceptual and philosophical changes in biology. From the early days of molecular biology, there exists the idea that the DNA sequence dictates most of cell actions, as the instructions in a computer program. Recently, together with the advent of systems biology, such a mechanistic understanding has been strongly revisited. Instead, an informatic perspective on the role of the genome has been established. From this point of view, the focus is on what the cell does with and to its genome products rather than on what the genome directs the cell to execute [START_REF] Shapiro | Revisiting the central dogma in the 21st century[END_REF]. Then, for any biological system one can envision at least a three-way interaction between DNA products, the environment and the phenotype [START_REF] Kohl | Systems biology: An approach[END_REF]. In this scheme, the group of entities mediating between such interactions are the so-called biological networks. Deciphering the functioning of these complex networks is the central task of systems biology. Importantly, in order to cope with the increasing complexity of large-scale networks, mathematical and computational modeling is required. Hence, the development of such modeling approaches is a major goal in the field.

From the early millennium, many efforts have been made to develop relevant formalisms and modeling frameworks to take into account the specificities of complex biological systems. Among them, one can distinguish between mathematical and computational modeling approaches [START_REF] Fisher | Executable cell biology[END_REF]. Essentially, mathematical (or quantitative) models are based on denotational semantics, that is, models are specified by mathematical equations describing how certain quantities change over time [START_REF] Aldridge | Physicochemical modelling of cell signalling pathways[END_REF]. On the other hand, computational (or qualitative) models are based on operational semantics, that is, models are specified in terms of a sequence of steps describing how the states of an abstract machine relate to each other (not necessarily deterministically) [START_REF] Melham | Modelling, abstraction, and computation in systems biology: A view from computer science[END_REF]. Notably, each type of models provides a different level of abstraction enabling to address different kinds of questions. In fact, hybrid modeling precisely aims at exploiting the best of both worlds whenever possible [START_REF] Henzinger | The theory of hybrid automata[END_REF]. In any case, it is clear that intuition is not enough to face the complexity of large-scale biological systems. Thus, systematic and elaborated methodological tools are required by (systems) biologists. Moreover, the development of such modeling frameworks is leading to a hypothesis-driven research in biology [START_REF] Ideker | A new approach to decoding life: systems biology[END_REF][START_REF] Kitano | Systems biology: a brief overview[END_REF]. At first, due to the lack of information, multiple hypotheses are usually generated from prior knowledge and either mathematical, computational or hybrid modeling. Next, decision-making methods can be used to suggest new experiments in order to reduce ambiguous hypotheses [START_REF] Kreutz | Systems biology: experimental design[END_REF]. Finally, new experimental data is produced to test the generated hypotheses, the models are refined, and the loop is started over again. Interestingly, to some extent, this iterative process could be automatized allowing an autonomous scientific discovery [START_REF] Sparkes | Towards robot scientists for autonomous scientific discovery[END_REF].

Signaling networks

Among the biological networks mediating between genes, the environment and the phenotype, signal transduction networks are crucial for the understanding of the response to external and internal perturbations [START_REF] Gomperts | Signal Transduction[END_REF]. To be more precise, signal transduction occurs when an extracellular signaling molecule binds to a specific cell surface receptor protein. Such a binding causes a conformational change in the receptor that initiates a sequence of reactions leading to a specific cellular response such as growth, survival, apoptosis (cell death), and migration. Post-translational modifications, notably protein phosphorylation, play a key role in signaling. Importantly, signaling networks are involved in biomedical processes and their control has a crucial impact on drug target identification and diagnosis. Unfortunately, little is known still about the exact chaining and composition of signaling events within these networks in specific cells and specific conditions. For example, in cancer cells, signaling networks frequently become compromised, leading to abnormal behaviors and responses to external stimuli [START_REF] Hanahan | Hallmarks of Cancer: The Next Generation[END_REF]. Thus, many current and emerging cancer treatments are designed to block nodes in signaling networks, thereby altering signaling cascades [Gom-perts et al., 2009[START_REF] Hainaut | Targeting the hallmarks of cancer: towards a rational approach to next-generation cancer therapy[END_REF][START_REF] Csermely | Structure and dynamics of molecular networks: a novel paradigm of drug discovery: a comprehensive review[END_REF]. Researchers expect that, advancing our understanding of how these networks are deregulated across specific environments will ultimately lead to more effective treatment strategies for patients. In fact, there is emerging experimental evidence that the combinatorics of interactions between cellular components in signaling networks is a primary mechanism for generating highly specialized biological systems [START_REF] Papin | Reconstruction of cellular signalling networks and analysis of their properties[END_REF]. In this context, phosphorylation assays are a recent form of high-throughput data providing information about protein-activity modifications in a specific cell type upon various combinatorial perturbations [START_REF] Alexopoulos | Networks inferred from biochemical data reveal profound differences in toll-like receptor and inflammatory signaling between normal and transformed hepatocytes[END_REF]. Therefore, moving beyond causal and canonical interactions towards mechanistic and specialized descriptions of signaling networks is a major challenge in systems biology. Importantly, cellular signaling networks operate over a wide range of timescales (from fractions of a seconds to hours). Thus, taking this into account often leads to significant simplifications [START_REF] Papin | Reconstruction of cellular signalling networks and analysis of their properties[END_REF], Macnamara et al., 2012].

Finally, we conclude this brief introduction to systems biology and signaling networks by noting that biological functionality is multilevel [START_REF] Noble | Biophysics and systems biology[END_REF]. That is, signaling networks by no means could function in isolation from metabolic and regulatory processes. Hence, integrative modeling approaches considering these multiple levels of causation pose indeed a long-term goal in the field.

Computational modeling and methods

Computational modeling

The simplest abstraction to describe signaling networks is by means of standard graph theory. Nodes in the graph typically describe biological species whereas signed and directed edges represent causal relations among them (activatory or inhibitory effects). Nowadays, there exist public repositories such as Pathways Commons [START_REF] Cerami | Pathway commons, a web resource for biological pathway data[END_REF], Pathways Interaction Database [START_REF] Schaefer | Pid: the pathway interaction database[END_REF], and KEGG [START_REF] Kanehisa | Kegg for representation and analysis of molecular networks involving diseases and drugs[END_REF] that contain curated knowledge about intracellular causal molecular interactions found in different cell types and species. Thus, on the one hand, one can query such databases in order to retrieve canonical cellular signaling networks [START_REF] Guziolowski | Automatic generation of causal networks linking growth factor stimuli to functional cell state changes[END_REF]. On the other hand, in order to build context-specific causal interaction graphs, machine learning was applied for the automated inference from experimental observations relying on Bayesian networks [START_REF] Sachs | Causal protein-signaling networks derived from multiparameter single-cell data[END_REF][START_REF] Needham | A primer on learning in Bayesian networks for computational biology[END_REF]. Next, several graph-theoretical concepts can be used to understand structural properties of the biological system under study. However, functional relationships in signaling networks cannot be captured by means of graph theory only [Klamt et al., 2006b]. If two proteins modeled by nodes a and b have a positive effect on a third one c, this would be described in a graph by edges a → c, b → c. Nevertheless, it is unclear whether a or b can independently activate c, or if both are required. Therefore, due to the lack of mechanistic information, causal interaction graphs have null or very limited prediction power.

In order to qualitatively describe functional relations between species, numerous discrete dynamical systems approaches have been proposed. Among them, logic-based models have become very popular in the last few years [START_REF] Réka | Discrete dynamic modeling of cellular signaling networks[END_REF][START_REF] Morris | Logic-based models for the analysis of cell signaling networks[END_REF][START_REF] Wang | Boolean modeling in systems biology: an overview of methodology and applications[END_REF][START_REF] Saadatpour | Boolean modeling of biological regulatory networks: A methodology tutorial[END_REF]. Generally speaking, species in the system are described by propositional variables and their relationships are captured by means of propositional formulas. Then, such a set of formulas determines the evolution of the system over discrete time steps. That is, the future state of each variables is determined by the current states of other variables through its corresponding formula. In this context, Boolean networks [START_REF] Kauffman | Metabolic stability and epigenesis in randomly constructed genetic nets[END_REF] provide a modeling approach able to capture interesting and relevant behaviors in the cell despite their simplicity [START_REF] Bornholdt | Boolean network models of cellular regulation: prospects and limitations[END_REF]. Notably, this simplicity is due to the high level of abstraction and synchronous update scheme in Boolean networks. That is, one needs to assume that all species in the system update their (discrete) state at the same time. In particular, this leads to deterministic dynamical behaviors. Nonetheless, it has been shown that, to some extent, the (early) response in signaling networks can be appropriately modeled with Boolean networks [START_REF] Saez-Rodriguez | A logical model provides insights into t cell receptor signaling[END_REF], Samaga et al., 2009, Saez-Rodriguez et al., 2011]. In order to overcome some shortcomings in (synchronous) Boolean networks, more elaborate logical frameworks have been proposed. For instance, asynchronous automata networks [START_REF] Thomas | Boolean formalization of genetic control circuits[END_REF][START_REF] Thomas | Regulatory networks seen as asynchronous automata: A logical description[END_REF], and probabilistic Boolean networks [START_REF] Shmulevich | Probabilistic Boolean networks: a rule-based uncertainty model for gene regulatory networks[END_REF] are often able to capture more complex (non-deterministic) dynamical behaviors [START_REF] Shmulevich | Gene perturbation and intervention in probabilistic Boolean networks[END_REF][START_REF] Sánchez | Segmenting the fly embryo: logical analysis of the role of the segment polarity cross-regulatory module[END_REF][START_REF] Calzone | Mathematical modelling of cell-fate decision in response to death receptor engagement[END_REF]. However, in order to capture such behaviors in large-scale networks, the computational cost is often significantly high due to the combinatorial explosion of possible states at simulation. More broadly, other computational formalisms have been proposed to describe complex dynamical systems by incorporating (semi-) quantitative information, for instance, piecewiselinear models [ [START_REF] Jong | Qualitative simulation of genetic regulatory networks using piecewise-linear models[END_REF], Petri nets [START_REF] Chaouiya | Petri net modelling of biological networks[END_REF], π-calculus [START_REF] Regev | Representation and simulation of biochemical processes using the π-calculus process algebra[END_REF], and rule-based modeling [START_REF] Hlavacek | Rules for modeling signal-transduction systems[END_REF]. Piecewise-linear models rely on class of piecewise-linear differential equations to provide a coarse-grained description tailored to qualitative simulation. Although related to asynchronous automata networks, piecewise-linear models account for larger generality whereas their base mathematical formalism, namely, differential equations, facilitate the integration of quantitative data towards pure mathematical models. Petri nets provide a very intuitive (graphical) framework to represent production and consumption effects like in metabolic networks but, signaling events are not so easily modeled with standard settings. In fact, several extensions have been defined to increase the expressivity of standard Petri nets, such as stochastic, coloured, and continuous Petri nets [START_REF] Heiner | How might Petri nets enhance your systems biology toolkit[END_REF]. The π-calculus is an abstract process language developed for specifying concurrent computational systems [START_REF] Milner | Communicating and Mobile Systems: The π-calculus[END_REF]. In our context, the key idea is to model a biological system as a network of communicating processes (molecular species) through specific channels (binding sites). Furthermore, the so-called stochastic π-calculus [START_REF] Priami | Application of a stochastic name-passing calculus to representation and simulation of molecular processes[END_REF] has been proposed to describe more accurate dynamical behaviors. Finally, in contrast to the aforementioned general purpose modeling frameworks, rule-based modeling relies on domain-specific languages to model biochemical networks [START_REF] Hlavacek | Rules for modeling signal-transduction systems[END_REF][START_REF] Calzone | BIOCHAM: an environment for modeling biological systems and formalizing experimental knowledge[END_REF][START_REF] Danos | Formal molecular biology[END_REF]. Similarly to π-calculus, it allows modelers to take into account physicochemical parameters that capture details about proteins and their interactions at the level of binding sites. Notably, as one considers more proteins and binding sites, the number of possible protein complexes and combinations of protein modifications tends to increase exponentially [START_REF] Papin | Reconstruction of cellular signalling networks and analysis of their properties[END_REF]. Therefore, the explicit writing of all possible chemical reactions for signaling networks with more than a few proteins is out of reach. In fact, the main motivation for rule-based modeling is to provide a symbolic representation to face this combinatorial complexity, whereas various implementations allow to automatically generate a computational model to be executed.

Current challenges in logic-based modeling

In this thesis, we are interested in logic-based models, particularly Boolean networks and slight variations thereof. We note that, such modeling approach is among the simplest computational abstractions (after causal interaction graphs). Nevertheless, initially simple logic-models have been refined in an iterative fashion by adding layers of complexity yielding more precise descriptions [Wittmann et al., 2009, Samaga andKlamt, 2013]. This is especially useful in the case of poorly understood biological systems where kinetic information is scarce and hard to obtain at early stages of modeling. Thus, despite their high level of abstraction, logic-based models are well-suited to guide exploratory research where more detailed modeling frameworks are hard to adopt due to the lack of information. In this context, it is important to note that a large majority of the authors working with such kinds of models rely on ad-hoc methods to build them. In most cases, models are constructed manually based on information extracted from literature, experimental data, and human-expert knowledge. Notably, the manual identification of logic rules underlying the system being studied is often hard, error-prone, and time consuming. In this context, researchers typically aim at modeling a given biological system by means of one logical network only. Afterwards, dynamical and structural analysis (often computationally demanding) are conducted over the model, for instance, the identification of key-players [START_REF] Abdi | Fault diagnosis engineering of digital circuits can identify vulnerable molecules in complex cellular pathways[END_REF][START_REF] Samaga | Computing combinatorial intervention strategies and failure modes in signaling networks[END_REF], Wang and Albert, 2011[START_REF] Layek | Cancer therapy design based on pathway logic[END_REF] or logical steady states [START_REF] Christensen | Reconstruction and logical modeling of glucose repression signaling pathways in saccharomyces cerevisiae[END_REF][START_REF] Saadatpour | Dynamical and structural analysis of a t cell survival network identifies novel candidate therapeutic targets for large granular lymphocyte leukemia[END_REF][START_REF] Mendoza | Genetic control of flower morphogenesis in arabidopsis thaliana: a logical analysis[END_REF]. However, due to several factors, such as limited observability or the uncertainty in experimental measurements, the model is often non-identifiable. Hence, biological insights and novel hypotheses resulting from these analyses are likely to be incomplete, incorrect, or biased by methodological decisions. Therefore, automated learning of logic-based models is required in order to achieve unbiased and more robust discoveries.

Reverse engineering in systems biology consists of building mathematical and computational models of biological systems based on the available knowledge and experimental data. Towards the construction of predictive models, one can convert the generic prior knowledge (for example, canonical cell signaling networks) into a quantitative or qualitative model (for instance, a set of differential equations or a set of logic rules) that can be simulated or executed. Next, if enough experimental data is available, the model can be fitted to it in order to obtain the most plausible models for certain environmental conditions or specific cell type. This is normally achieved by defining an objective fitness function to be optimized [START_REF] Banga | Optimization in computational systems biology[END_REF]. Optimization over quantitative modeling leads to continuous optimization problems. On the other hand, reverse engineering considering qualitative models typically give rise to combinatorial (discrete) optimization problems. Notably, this subject represents a very active area of research as illustrated by the successive "DREAM" challenges [START_REF] Stolovitzky | Dialogue on reverse-engineering assessment and methods: the dream of high-throughput pathway inference[END_REF]. Importantly, methods for reverse engineering of biological systems are highly dependent on available (amount of) data, prior knowledge and modeling hypotheses. For instance, an inference method from gene expression data collected by DNA microarrays, may not be applicable to biochemical data like phosphorylation assays collected using xMAP Luminex technology. In particular, reverse engineering of logical models for signaling networks by confronting prior knowledge on causal interactions with phosphorylation activities has been first addressed in [START_REF] Saez-Rodriguez | Discrete logic modelling as a means to link protein signalling networks with functional analysis of mammalian signal transduction[END_REF]. Therein, authors have shown that the model is non-identifiable as soon as we consider the experimental error from measurements. Hence, rather than looking for the optimum logical model, one aims at finding (nearly) optimal models within certain tolerance. Interestingly, in the context of mathematical modeling, authors in [START_REF] Chen | Input-output behavior of ErbB signaling pathways as revealed by a mass action model trained against dynamic data[END_REF] have elaborated upon the same argument. Clearly, an exhaustive enumeration of (nearly) optimal solutions would allow for identifying admissible logical models without any methodological bias. Furthermore, all subsequent analysis will certainly profit from having such a complete characterization of feasible models. That is, being able to address a given problem but considering an ensemble of logical models may lead to more robust solutions. In fact, this is in line with recent work showing that an ensemble of models often yields more robust predictions than each model in isolation [START_REF] Kuepfer | Ensemble modeling for analysis of cell signaling dynamics[END_REF][START_REF] Marbach | Wisdom of crowds for robust gene network inference[END_REF]. Importantly, existing approaches, namely stochastic search and mathematical programming, are not well-suited to cope with this question in an exhaustive manner. Hence, there is an increasing demand of more powerful computational methods in order to achieve robust discoveries in the context of logic-based modeling.

Computational methods

Regardless of the modeling approach and specific biological question, numerous computational methods have been proposed to solve the underlying search and optimization problems. On the one hand, we find dedicated algorithms implementations either looking at exact solutions or by means of stochastic local search [START_REF] Hoos | Stochastic Local Search[END_REF]. For instance, Cell-NetAnalyzer [Klamt et al., 2006a] implements various graph algorithms for structural and functional analysis of signaling networks whereas CellNOpt [START_REF] Terfve | CellNOptR: a flexible toolkit to train protein signaling networks to data using multiple logic formalisms[END_REF] relies on a genetic algorithm for training logical models to experimental observations. By their algorithmic nature, such dedicated solutions allow for having control on how the problem is solved. However, in order to address large-scale problems, a significant amount of effort is needed for the development and maintenance of such algorithms. Also, it is often the case that, as soon as we introduce a slight modification in the problem specification, it is rather hard to adapt such dedicated algorithms to it. On the other hand, several problem solving technologies exist which allow us to provide a specification, in some kind of machine-readable format, of what the problem is but without giving an algorithm to solve it. Afterwards, a general purpose solver is able to extract and (efficiently) traverse the search space looking for solutions. Popular methods found in the literature include, (mixed) integer linear programming ((M)ILP) [Mitsos et al., 2009, Sharan and[START_REF] Sharan | Reconstructing Boolean models of signaling[END_REF], model checking by means of temporal logic [START_REF] Chabrier | Symbolic model checking of biochemical networks[END_REF]Fages, 2003, Batt et al., 2005], satisfiability testing (SAT) [START_REF] Dubrova | A SAT-based algorithm for finding attractors in synchronous Boolean networks[END_REF]Teslenko, 2011, Guo et al., 2014], and constraint logic programing (CLP) [START_REF] Soliman | Invariants and other structural properties of biochemical models as a constraint satisfaction problem[END_REF][START_REF] Gay | Solving subgraph epimorphism problems using CLP and SAT[END_REF]. 1 While each of these computational methods has proven to be very useful for solving challenging problems, in general, they provide different kinds of complementary features. Furthermore, in general, the performance of each solver is subject to specific parameters (search heuristics) and problems.

In what follows we introduce Answer Set Programming (ASP), the computational method adopted in this thesis. But before, let us highlight two distinct features compared to aforementioned methods. Firstly, ASP provides a fully declarative and executable modeling language. This is in contrast with other general solving technologies, such as (M)ILP and SAT, where the user is responsible of converting the problem specification (e.g., mathematical inequalities or Boolean formulas) and input data into the machine-readable format accepted by the solver. Typically, this is done ad hoc by means of some imperative programming language yielding an overhead to the solving process. Secondly, ASP provides several built-in reasoning modes, such as search, enumeration, and multi-objective optimization, among others. Notably, each of the previously mentioned methods (and extensions thereof) provides some but not all such functionalities. Thus, in order to achieve such automated reasoning modes, one needs to develop dedicated algorithms on top of the solver yielding again, an overhead to the process.

Answer Set Programming at a glance Answer Set Programming (ASP; [START_REF]Knowledge Representation, Reasoning and Declarative Problem Solving[END_REF], Gebser et al., 2012a]) provides a declarative framework for modeling combinatorial problems in Knowledge Representation and Reasoning. The unique pairing of declarativeness and performance in state-of-the-art ASP solvers allows for concentrating on an actual problem, rather than a smart way of implementing it. The basic idea of ASP is to express a problem in a logical format so that the models of its representation provide the solutions to the original problem. Problems are expressed as logic programs and the resulting models are referred to as answer sets. Although determining whether a program has an answer set is the fundamental decision problem in ASP, more reasoning modes are needed for covering the variety of reasoning problems encountered in applications. Hence, a modern ASP solver, like clasp [Gebser et al., 2012b] supports several reasoning modes for assessing the multitude of answer sets, among them, regular and projective enumeration, intersection and union, and multi-criteria optimization. As well, these reasoning modes can be combined, for instance, for computing the intersection of all optimal models. This is accomplished in several steps. At first, a logic program with first-order variables is turned into a propositional logic program by means of efficient database techniques. This is in turn passed to a solver computing the answer sets of the resulting program by using advanced Boolean constraint technology. For optimization, a solver like clasp uses usually branch-andbound algorithms but other choices, like computing unsatisfiable cores, are provided as well.

The enumeration of all optimal models is done via the option --opt-mode=optN. At first an optimal model is determined along with its optimum value. This computation has itself two distinct phases. First, an optimal model candidate must be found and second, it must be shown that there is no better candidate; the latter amounts to a proof of unsatisfiability and is often rather demanding (because of its exhaustive nature). Then, all models possessing the optimum score are enumerated. Notice that this way one can enumerate all (strictly) optimal solutions. Nonetheless, we are often interested in (nearly) optimal answer sets as well. For a concrete example on how we address this in practice, we refer the reader to the encoding provided in Listing 3.2 and its solving in Listing 3.4.

Our encodings are written in the input language of gringo 4 series. Such a language implements most of the so-called ASP-Core-2 standard. 2 In what follows, we introduce its basic syntax and we refer the reader to the available documentation for more details. An atom is a predicate symbol followed by a sequence of terms (e.g. p(a,b),q(X,f(a,b))). A term is a constant (e.g. c, 42) or a function symbol followed by a sequence of terms (e.g. f(a,b), g(X,10)) where uppercase letters denote first-order variables. Then, a rule is of the form

h:-b 1 , . . . , b n .
where h (head) is an atom and any b j (body) is a literal of the form a or not a for an atom a where the connective not corresponds to default negation. The connectives :-and , can be read as if and and, respectively. Furthermore, a rule without body is a fact, whereas a rule without head is an integrity constraint. A logic program consists of a set of rules, each of which is terminated by a period. An atom preceded with default negation, not, is satisfied unless the atom is found to be true. In ASP, the semantics of a logic program is given by the stable models semantics [START_REF] Gelfond | The stable model semantics for logic programming[END_REF]. Intuitively, the head of a rule has to be true whenever all its body literals are true. This semantics requires that each true atom must also have some derivation, that is, an atom cannot be true if there is no rule deriving it. This implies that only atoms appearing in some head can appear in answer sets.

We end this quick introduction by three language constructs particularly interesting for our encodings. First, the so called choice rule of the form, {h 1 ; . . . ; h m }:b 1 , . . . , b n . allows us to express choices over subsets of atoms. Any subset of its head atoms can be included in an answer set, provided the body literals are satisfied. Note that using a choice rule one can easily generate an exponential search space of candidate solutions. Second, a 1.2. Computational modeling and methods conditional literal is of the form l : l 1 , . . . , l n

The purpose of this language construct is to govern the instantiation of the literal l through the literals l 1 , . . . , l n . In this respect, the conditional literal above can be regarded as the list of elements in the set {l | l 1 , . . . , l n }. Finally, for solving (multi-criteria) optimization problems, ASP allows for expressing (multiple) cost functions in terms of a weighted sum of elements subject to minimization and/or maximization. Such objective functions are expressed in gringo 4 in terms of (several) optimization statements of the form

#opt{w 1 @l 1 , t 1 1 , . . . , t m 1 : b 1 , . . . , b n 1 ; . . . ; w k @l k , t 1 k , . . . , t m k : b 1 k , . . . , b n k }.
where #opt ∈ {"#mi ni mi ze", "#maxi mi ze"}, w i , l i , t 1 i , . . . , t m i are terms and b 1 i , . . . , b n i are literals for k ≥ 0, 1 ≤ i ≤ k, m i ≥ 0 and n i ≥ 0. Furthermore, w i and l i stand for an integer weight and priority level. Priorities allow for representing lexicographically ordered optimization objectives, greater levels being more significant than smaller ones.

Answer Set Programming for systems biology. Our work contributes to a growing list of ASP applications in systems biology. Almost a decade ago, Baral et al. have proposed applying knowledge representation and reasoning methodologies to the problem of representing and reasoning about signaling networks [START_REF] Baral | A knowledge based approach for representing and reasoning about signaling networks[END_REF]. More recently, several authors have addressed the question of pruning or identification of biological networks using ASP. Durzinsky et al. have studied the problem consisting of reconstructing all possible networks consistent with experimental time series data [START_REF] Durzinsky | Automatic network reconstruction using ASP[END_REF]. Gebser et al. have addressed the problem consisting of detecting inconsistencies and repairing in large biological networks [Gebser et al., 2011b[START_REF] Gebser | Repair and prediction (under inconsistency) in large biological networks with answer set programming[END_REF]. Fayruzov et al. have used ASP to represent the dynamics in Boolean networks and find their attractors [START_REF] Fayruzov | Modelling gene and protein regulatory networks with answer set programming[END_REF]. Ray et al. have integrated numerical and logical information in order to find the most likely states of a biological system under various constraints [START_REF] Ray | Analyzing pathways using asp-based approaches[END_REF]. Furthermore, Ray et al. have used an ASP system to propose revisions to metabolic networks [START_REF] Ray | Logic-based steady-state analysis and revision of metabolic networks with inhibition[END_REF]. Papatheodorou et al. have used ASP to integrate RNA expression with signaling pathway information and infer how mutations affect ageing [START_REF] Papatheodorou | Using Answer Set Programming to integrate RNA expression with signalling pathway information to infer how mutations affect ageing[END_REF]. Finally, Schaub and Thiele have first investigated the metabolic network expansion problem with ASP [START_REF] Schaub | Metabolic network expansion with ASP[END_REF] and recently, their work has been extendend and applied in a real-case study by [START_REF] Collet | Extending the metabolic network of Ectocarpus siliculosus using answer set programming[END_REF].

Altogether, this series of contributions illustrates the potential of ASP to address combinatorial search and optimization problems appearing in the field. Nonetheless, its strictly discrete nature poses interesting challenges for future work towards hybrid reasoning system allowing for qualitative and quantitative modeling.

Original contribution

The contribution of this thesis is on three different axes. Firstly, on the modeling axis we introduce a novel mathematical framework for characterizing and reasoning on the response of logical signaling networks. Secondly, on the methodological axis we contribute to a growing list of successful applications of Answer Set Programming in systems biology. Thirdly, on the implementation axis we present a software providing a complete pipeline for automated reasoning on the response of logical signaling networks. More precisely, the main contributions of this thesis are:

• a mathematical framework for reasoning on the response of logical signaling networks relying on propositional logic and fixpoint semantics together with a basic ASP representation (Chapter 2)

• an ASP formulation to address the problem consisting of learning from an interaction graph and experimental data, (Boolean) logical networks describing the immediateearly response of the system (Chapter 3)

• a proposal for finding optimal experimental designs to discriminate between rival logical models. Furthermore, an ASP formulation to solve this problem is provided (Chapter 4)

• an ASP formulation to address the problem consisting of finding all inclusion-minimal intervention strategies for an ensemble of feasible logical networks (Chapter 5)

• a software toolbox providing an interface to the ASP-based solutions for each of the problems mentioned above (Chapter 6)

A first approach to the subject presented in Chapter 3 was published in [START_REF] Videla | Revisiting the Training of Logic Models of Protein Signaling Networks with[END_REF], and an extended version is under revision for a special issue of the journal Theoretical Computer Science. Nonetheless, results presented in Chapter 3 are mostly based on the work published in [START_REF] Guziolowski | Exhaustively characterizing feasible logic models of a signaling network using Answer Set Programming[END_REF]. Therein, we have also provided an informal description for the problem addressed in Chapter 4 which has been properly developed in this thesis. The work in Chapter 5 is an unpublished extension of the paper presented in [START_REF] Kaminski | Minimal Intervention Strategies in Logical Signaling Networks with Answer Set Programming[END_REF]. Finally, the software described in Chapter 6 was introduced first in [ [START_REF] Guziolowski | Exhaustively characterizing feasible logic models of a signaling network using Answer Set Programming[END_REF] but the version presented in this thesis contains several improvements and new features.

Organization of the thesis

The dissertation is organized in seven chapters, including the introduction and the conclusion.

In Chapter 2 we provide a precise definition of logical networks, their graphical representation and related mathematical notions used throughout this thesis. Next, we introduce a mathematical characterization of the response in logical networks based on a single-step operator and fixpoint semantics. Based on this mathematical characterization, we introduce a generic 1.4. Organization of the thesis representation using ASP. Interestingly, such a representation is relatively simple yet flexible enough to be extended and adapted for specific applications as we illustrate in the subsequent chapters. In Chapter 3 we address the problem consisting of learning from an interaction graph and phosphorylation activities at a pseudo-steady state, (Boolean) logical networks describing the immediate-early response of the system. We provide a characterization of this problem using the notions introduced in Chapter 2 and adapting our ASP representation accordingly. Also, we show that there are multiple (possibly many) logical networks compatible with the experimental observations. In particular, this leads to logical input-output predictions suffering a significant level of uncertainty. Thus, in Chapter 4 we introduce a method to suggest new experiments for discrimination of input-output behaviors and generate models providing more reliable predictions. We provide a characterization of this problem using the notions introduced in previous chapters and adapting our ASP representation accordingly.

In Chapter 5 we address the problem consisting of finding inclusion-minimal intervention strategies in logical signaling networks. Towards this end, we revisit and extend a previous definition of this problem using the notions introduced in Chapter 2, and adapting our ASP representation. In Chapter 6 we present a software package providing an interface to the ASP-based solutions detailed in previous chapters. We describe its high-level design, main features, and usage. Finally, in Chapter 7 we discuss the strengths and weaknesses of our modeling and computational methods. Furthermore, we conclude with prospective lines of research and future directions to explore questions raised by our work.

2 Generic framework for reasoning on the response of logical networks

Here we provide a precise definition of logical networks, their graphical representation and related mathematical notions used throughout this thesis. Next, following the investigations of [START_REF] Inoue | Logic programming for boolean networks[END_REF] we introduce a mathematical characterization of the response in logical networks based on a single-step operator and fixpoint semantics. Based on this mathematical characterization, we introduce a generic representation using Answer Set Programming. Interestingly, such a representation is relatively simple yet flexible enough to be extended and adapted for specific applications as we illustrate in the subsequent chapters.

Preliminaries

Propositional logic and mathematical notation

Given a finite set V of propositional variables, we form propositional formulas from V with the connectives ⊥, �, ¬, ∨, and ∧ in the standard way. Further, we consider (partial) truth assignments over V mapping formulas to truth values {t , f , u} according to Kleene's semantics [START_REF] Kleene | Introduction to metamathematics[END_REF]. Clearly, two-valued assignments are restricted to range {t , f } according to classical (Boolean) logic semantics. We recall the truth tables for classical (Boolean) and Kleene's logics in Table 2.1 and Table 2.2, respectively.

Let f : X → Y , be a (partial) function mapping values x ∈ X � ⊆ X to values y ∈ Y . We denote the set of values x such that f (x) is defined, i.e. X � , with d om( f ). We sometimes represent mappings extensionally as sets, viz. {x

� → f (x) | x ∈ d om( f )}, for checking containment, dif- Table 2.1: Truth tables for classical (Boolean) logic. a ∧ b b t f a t t f f f f a ∨ b b t f a t t t f t f a ¬a t f f t
a ∧ b b t f u a t t f u f f f f u u f u a ∨ b b t f u a t t t t f t f u u t u u a ¬a t f f t u u
ference, etc. To avoid conflicts when composing two-valued truth assignments, we define

A • B = (A \ B ) ∪ B where B = {v � → s | v � → s ∈ B } and t = f , f = t .
2.2 Characterizing the response of logical networks 2.2.1 Logical networks and interaction graphs Logical networks. A logical network consists of a finite set V of propositional variables and a (partial) function φ mapping a variable v ∈ V to a propositional formula φ(v) over V . The logical steady states of (V, φ) are given by truth assignments yielding identical values for v and φ(v) for all v ∈ d om(φ). Generally speaking, such logical networks can be seen as synchronous Boolean networks [START_REF] Kauffman | Metabolic stability and epigenesis in randomly constructed genetic nets[END_REF]. However, since we consider both, two-and three-valued logics, we refrain from using the term "Boolean". Without loss of generality, we assume only formulas in disjunctive normal form.1 For illustration, let us consider the logical network consisting of the set V of species variables {i 1 , i 2 , a, . . . , g , o 1 , o 2 } along with the function φ defined as:

φ =      a � → ¬d b � → a ∧ i 1 c � → b ∨ e d � → c e � → ¬i 1 ∧ i 2 f � → e ∨ g g � → f o 1 � → c o 2 � → g     
Note that φ leaves the specification of the (input) variables i 1 and i 2 undefined. Furthermore, we represent logical networks as (signed) directed hypergraphs as shown in Figure 2.1a. A (signed) directed hypergraph is defined by a pair (V, H ) with vertices V and (signed) directed hyperedges H ; a (signed) directed hyperedge is a pair (S, t ) where S is a finite, non-empty set of pairs (v i , s i ) with v i ∈ V, s i ∈ {1, -1} and t ∈ V . 2 Then, we say that the (signed) directed hypergraph (V, H ) represents the logical network (V, φ) if and only if for every v ∈ d om(φ) and variable w ∈ V that occurs positively (resp. negatively) in some conjunct ψ of φ(v), there is a hyperedge (S ψ , v) with (w, 1) ∈ S ψ (resp. (w, -1) ∈ S ψ ); and vice versa. Following the example shown in Figure 2.1a, if we consider the mapping φ(e) = ¬i 1 ∧i 2 , we need to verify the existence of the hyperedge (S ¬i 1 ∧i 2 , e) with S ¬i 1 ∧i 2 = {(i 1 , -1), (i 2 , 1)}. Similarly, for the mapping Interaction graphs. Next, we introduce the notion of the interaction graph underlying a logical network (V, φ). An interaction graph (V, E , σ) is a signed and directed graph with vertices V , directed edges E ⊆ V × V and signature σ ⊆ E × {1, -1}. Moreover, we say that

Σ (V,φ) = (V, E , σ)
is the underlying interaction graph of (V, φ) if for every edge (v, w) ∈ E with ((v, w), 1) ∈ σ (resp. ((v, w), -1) ∈ σ), the variable v occurs positively (resp. negatively) in the formula φ(w). Note that there is a one-to-many relation in the sense that the same graph (V, E , σ) corresponds to the underlying interaction graph Σ (V,φ) for possibly many logical networks (V, φ). Now, we can rely on standard notions from graph theory to capture several concepts on logical networks. Recall that a path in a graph is a sequence of edges connecting a sequence of vertices. The length of a path is given by the number of edges whereas its sign is the product of the signs of the traversed edges. Herein, we consider only paths with length greater than zero. Thus, an edge (v, v) is required in order to consider the existence of a path from v to v. We say there is a positive (resp. negative) path from v to w in (V, φ) if and only if there is a positive (resp. negative) path from v to w in Σ (V,φ) . Furthermore, we say there is a positive (resp. negative) feedback-loop in (V, φ) if and only if for some v ∈ V there is a positive (resp. negative) path from v to v in Σ (V,φ) .

Characterizing the response of the system

Clamping variables. Let (V, φ) be a logical network describing a biological system of interest.

For capturing changes in the environment of such a biological system, for instance, due to an experimental intervention (over-expression or knock-out), we introduce the notion of clamping variables in the network for overriding their original specification. Towards this end, we define a clamping assignment C as a partial two-valued truth assignment over V . Then, we define the mapping φ| C as

φ| C (v) =      � if v � → t ∈ C ⊥ if v � → f ∈ C φ(v) if v ∈ d om(φ) \ d om(C )
yielding the modified logical network (V, φ| C ). Moreover, it is worth noting that d om(φ) ⊆ d om(φ| C ). Let us illustrate this with our toy example in Figure 2.1a. Let C be the clamping assignment defined by {i

1 � → t , i 2 � → f , g � → f }. Then, φ| C is a complete mapping over V defined as φ| C =      i 1 � → � i 2 � → ⊥ a � → ¬d b � → a ∧ i 1 c � → b ∨ e d � → c e � → ¬i 1 ∧ i 2 f � → e ∨ g g � → ⊥ o 1 � → c o 2 � → g     
In practice, clamping assignments are usually restricted to a subset of variables X ⊆ V . Moreover, certain variables in X may be further restricted to be clamped either to a single truth value, viz. t or f , or not clamped at all. These restriction will be typically related to contextspecific application settings, for instance, the kind of biological entity described by each variable and "real-world" experimental limitations over such entity.

Fixpoint semantics. Next, for capturing the synchronous updates in a logical network (V, φ), we define the following operator on either two-or three-valued (complete) truth assignments over V :3

Ω (V,φ) (A) = {v � → A(φ(v)) | v ∈ d om(φ)} ∪ {v � → A(v) | v ∈ V \ d om(φ)}.
where A is extended to formulas in the standard way. Notice that the definition above captures the fact that unmapped variables in φ remain unchanged with respect to the value assigned in A. Furthermore, for capturing the trajectory of state A we define the iterative variant of Ω (V,φ) as

Ω 0 (V,φ) (A) = A and Ω j +1 (V,φ) (A) = Ω (V,φ) � Ω j (V,φ) (A) � .
In biological terms, a sequence (Ω j (V,φ) (A)) j ∈J captures the signal propagation starting in state A. In particular, we are interested in the fixpoint of Ω (V,φ) reachable from certain initial assignment A. Importantly, the existence of such a fixpoint is not necessarily guaranteed. In general, it depends on the definition of A and the presence or absence of feedback-loops in (V, φ). But in case of existence, such a fixpoint describes a logical steady state which is interpreted as the response of the biological system described by (V, φ). To be more precise, the choice of A is related to how we model the absence of information in the context of either two-or three-valued logics. Hence, when we consider three-valued logics, we use the initial Table 2.3: Exemplary iterated application of Ω (V,φ| C ) for (V, φ) in Figure 2.1a, clamping assignment

C = {i 1 � → t , i 2 � → f , g � → f } and initial assignment A with either A = A u or A = A f . φ| C (v) � ⊥ ¬d a ∧ i 1 b ∨ e c ¬i 1 ∧ i 2 e ∨ g ⊥ c g v ∈ V i 1 i 2 a b c d e f g o 1 o 2 3-valued Ω 0 (V,φ| C ) (A u ) u u u u u u u u u u u Ω 1 (V,φ| C ) (A u ) t f u u u u u u f u u Ω 2 (V,φ| C ) (A u ) t f u u u u f u f u f Ω 3 (V,φ| C ) (A u ) t f u u u u f f f u f Ω 4 (V,φ| C ) (A u ) t f u u u u f f f u f 2-valued Ω 0 (V,φ| C ) (A f ) f f f f f f f f f f f Ω 1 (V,φ| C ) (A f ) t f t f f f f f f f f Ω 2 (V,φ| C ) (A f ) t f t t f f f f f f f Ω 3 (V,φ| C ) (A f ) t f t t t f f f f f f Ω 4 (V,φ| C ) (A f ) t f t t t t f f f t f Ω 5 (V,φ| C ) (A f ) t f f t t t f f f t f Ω 6 (V,φ| C ) (A f ) t f f f t t f f f t f Ω 7 (V,φ| C ) (A f ) t f f f f t f f f t f Ω 8 (V,φ| C ) (A f ) t f f f f f f f f f f Ω 9 (V,φ| C ) (A f ) t f t f f f f f f f f assignment A u = {v � → u | v ∈ V }.
Interestingly, in this context a fixpoint is reached regardless of the presence or absence of feedback-loops in the network. Moreover, such a fixpoint poses the property that each of its variables is assigned to u unless there is a cause to assign it to either t or f . On the other hand, when we consider two-valued logics, we use the initial assignment

A f = {v � → f | v ∈ V }.
Unfortunately, in this context, the presence of negative feedback-loops typically avoids reaching a fixpoint [Remy et al., 2008, Paulevé and[START_REF] Paulevé | Static analysis of boolean networks based on interaction graphs: A survey[END_REF].

Next, let us illustrate the iterated application of Ω (V,φ| C ) for our toy example in the context of both, two-and three-valued logics. Recall that we have defined φ| C above for clamping assignment

C = {i 1 � → t , i 2 � → f , g � → f }.
The resulting assignments from the computation of

Ω j (V,φ| C ) (A) with either A = A u or A = A f are shown in Table 2.3. Notably, when we consider three-valued logic, Ω 3 (V,φ| C ) (A u ) = Ω 4 (V,φ| C ) (A u ) results in the fixpoint {i 1 � → t , i 2 � → f , a � → u, b � → u, c � → u, d � → u, e � → f , f � → f , g � → f , o 1 � → u, o 2 � → f } .
Meanwhile, under two-valued logic we obtain

Ω 1 (V,φ| C ) (A f ) = Ω 9 (V,φ| C ) (A f
) which leads to an oscillatory behavior for variables a, b, c, d and o 1 . Notice that these variables correspond to the ones assigned to u in the fixpoint reached for Ω 3 (V,φ| C ) (A u ). In this case, the oscillatory behavior is induced by the negative feedback-loop over the path a, b, c, d . Thus, one can verify that for example, if we remove the mapping d � → c from the definition of φ (leaving d undefined in φ),

then Ω 4 (V,φ| C ) (A f ) would result in the fixpoint {i 1 � → t , i 2 � → f , a � → t , b � → t , c � → t , d � → f , e � → f , f � → f , g � → f , o 1 � → t , o 2 � → f } .
In fact, in this thesis whenever we consider a logical network (V, φ) under two-valued logic, we enforce that (V, φ) is free of feedback-loops. Notably as detailed in Chapter 3, although not capable of capturing dynamical properties, this simplification guarantees the existence of a fixpoint while it allows us to characterize the so-called immediate-early response in signaling networks.

Logical networks and their response with Answer Set Programming

Logical networks. Let (V, φ) be a logical network. We represent the variables V as facts over the predicate variable/1, namely variable(v) for all v ∈ V . Recall that we assume φ(v)

to be in disjunctive normal form for all v ∈ V . Hence, φ(v) is a set of clauses and a clause a set of literals. We represent formulas using predicates formula/2, dnf/2, and clause/3.

The facts formula(v,s φ(v) ) map variables v ∈ V to their corresponding formulas φ(v), facts dnf(s φ(v) ,s ψ ) associate φ(v) with its clauses ψ ∈ φ(v), facts clause(s ψ ,v,1
) associate clause ψ with its positive literals v ∈ ψ ∩ V , and facts clause(s ψ ,v,-1) associate clause ψ with its negative literals ¬v ∈ ψ. Note that each s (•) stands for some arbitrary but unique name in its respective context here. Listing 2.1 shows the representation of our toy example logical network in Figure 2.1a.

Listing 2.1: Logical networks representation as logical facts variable ( i1 ) . variable ( i2 ) . variable ( o2 ) . variable ( o1 ). variable ( a ) . variable ( b ) . variable ( c ) . variable ( d ) . variable ( e ) . variable ( f ) . variable ( g ) .

formula (a ,0) . formula (b ,2) . formula (c ,1) . formula (d ,4) . formula (e ,3) . formula (f ,6) . formula (g ,5) . formula ( o1 ,4) . formula ( o2 ,7) .

dnf (0 ,5) . dnf (1 ,6) . dnf (1 ,0) . dnf (2 ,3) . dnf (3 ,7) . dnf (4 ,1) . dnf (5 ,2) . dnf (6 ,4) . dnf (6 ,6) . dnf (7 ,4) .

clause (0 ,b ,1) . clause (1 ,c ,1) . clause (2 ,f ,1) . clause (3 ,a ,1) . clause (3 , i1 ,1) . clause (4 ,g ,1) . clause (5 ,d , -1) . clause (6 ,e ,1) . clause (7 , i2 ,1) . clause (7 , i1 , -1) .

Clamping variables. The representation of clamping assignments is straightforward. Note that in the following we use 1 and -1 for truth assignments to t and f , respectively. Let C be a clamping assignment over V , we represent the assignments in C as facts over the predicate

clamped/2, namely clamped(v,s) with s = 1 if C (v) = t and s = -1 if C (v) = f . The example clamping assignment C = {i 1 � → t , i 2 � → f , g � → f } is shown in Listing 2.2.
Listing 2.2: Clamping assignment as logical facts clamped ( i1 ,1) . clamped ( i2 , -1) . clamped (g , -1) .

Furthermore, we introduce two rules deriving predicates eval/2 and free/2. The predicate eval/2 captures the fact that clamped variables are effectively fixed to the corresponding evaluation. Finally, we use the predicate free/2 to represent the fact that every variable not clamped in C , is subject to the corresponding mapping φ(v). Both rules are shown in Listing 2.3.

Listing 2.3: Clamped and free variables

eval (V , S ) : -clamped (V , S ) . free (V , D ) : -formula (V , D ) ; dnf (D , _ ) ; not clamped (V , _ ) .
Two-and three-valued logics. Next, we describe how we model either two-or three-valued logics in ASP. In fact, the rule modeling the propagation of (positive) true values is the same for both logics. Essentially, we exploit the fact that formulas φ(v) are in disjunctive normal form. Hence, under both logics we derive eval(v,1) if v is not clamped and there exists a conjunct ψ ∈ φ(v) such that all its literals evaluate positively. The rule describing this is shown in Listing 2.4.

Listing 2.4: Positive propagation common to two-and three-valued logics eval (V ,1) : -free (V , D ) ; eval (W , T ) : clause (J ,W , T ) ; dnf (D ,J ) .

Meanwhile, the propagation of (negative) false values depends on the type of logic under consideration. On one hand, when we consider two-valued logic, we use the rule shown in Listing 2.5 to derive eval(v,-1) if it cannot be proved that v evaluates positively, that is, not eval(v,1).

Listing 2.5: Negative propagation for two-valued logic (with default negation) eval (V , -1) : -variable ( V ) ; not eval (V ,1) .

On the other hand, when we consider three-valued logic, we use the rules shown in Listing 2.6.

Notice that in this case, we derive eval(v,-1) only if it can be proved that all clauses ψ ∈ φ(v) evaluate negatively. A clause φ evaluates negatively if at least one of its literals evaluates negatively. Clauses evaluating negatively are represented with the predicate eval_clause/2.

Listing 2.6: Negative propagation for three-valued logic (with explicit proof) eval_clause (J , -1) : -clause (J ,V , S ) ; eval (V , -S ) . eval (V , -1) : -free (V , D ) ; eval_clause (J , -1) : dnf (D , J ) .

Correctness of the ASP representation. The following two propositions show the correctness of our ASP representation for finding the fixpoint under either two-or three-valued logics, respectively. We refer the reader to the appendix for detailed proofs. Let us introduce the used notation first. For a logical network (V, φ) and clamping assignment C over V , let us denote with τ((V, φ),C ) the set of logical facts as in Listing 2.1 and Listing 2.2. Furthermore, for x = 3, . . . , 6 let us denote with Π 2.x the set of rules defined in Listing 2.x.

Proposition 2.2.1. Let (V, φ) be a logical network without feedback-loops and let C be a clamping assignment over V .

Then, there is an answer set

X of τ((V, φ),C )∪Π 2.3 ∪Π 2.4 ∪Π 2.5 such that F = {v � → t | eval(v,1) ∈ X } ∪ {v � → f | eval(v,-1) ∈ X } if and only if F is the unique fixpoint of Ω (V,φ| C ) reachable from A f .
Proposition 2.2.2. Let (V, φ) be a logical network and let C be a clamping assignment over V .

Then, there is an answer set X of τ((

V, φ),C ) ∪ Π 2.3 ∪ Π 2.4 ∪ Π 2.6 such that such that F = {v � → t | eval(v,1) ∈ X } ∪ {v � → f | eval(v,-1) ∈ X } ∪ {v � → u | eval(v,1) ∉ X , eval(v,-1) ∉ X } if and only if F is the unique fixpoint of Ω (V,φ| C ) reachable from A u .

Conclusion

In this chapter we have introduced the fundamental mathematical notions used throughout this thesis. More precisely, we have characterized the response of logical networks under either two-or three-valued logics based on fixpoint semantics. Furthermore, a representation using Answer Set Programming which allow for modeling logical networks and perform automated reasoning on their response has been provided. Notably, such a representation can be easily elaborated to consider specific application settings. For example, in Chapter 3 we extend our representation to learn logical networks from a given interaction graph confronting their response with experimental observations. Moreover, we consider several clamping assignments simultaneously instead of only one. In Chapter 4 we elaborate upon our representation in order to search for clamping assignments leading to different responses among several logical networks. In that context, the clamping assignments found are interpreted as experiments which would allow to discriminate the logical networks at hand. Finally, in Chapter 5 we adapt our representation again aiming at reasoning over a family of logical networks and finding clamping assignments leading to responses satisfying specific goals. Altogether, this constitutes a generic, flexible, and unified framework for modeling logical networks and perform automated reasoning on their response.

Learning Boolean logic models of immediate-early response

The manual identification of logic rules underlying a biological system is often hard, errorprone and time consuming. Therefore, automated inference of (Boolean) logical networks from experimental data is a fundamental question towards the construction of large-scale predictive models. This chapter addresses the problem consisting of learning from an interaction graph and phosphorylation activities at a pseudo-steady state, (Boolean) logical networks describing the immediate-early response of the system.

Introduction

In what follows, we briefly summarize the main biological hypotheses in [START_REF] Saez-Rodriguez | Discrete logic modelling as a means to link protein signalling networks with functional analysis of mammalian signal transduction[END_REF] providing the foundation for the concept of Boolean logic models of immediate-early response. Concretely, a Boolean logic model of immediate-early response is a logical network (V, φ) as defined in Chapter 2, without feedback-loops and using classical (Boolean) logics.

The main assumption under Boolean logic models as treated in [START_REF] Saez-Rodriguez | Discrete logic modelling as a means to link protein signalling networks with functional analysis of mammalian signal transduction[END_REF] is the following. The response of a biological system to external perturbations occurs at several time scales [START_REF] Papin | Reconstruction of cellular signalling networks and analysis of their properties[END_REF]]. Thus, one can discriminate between fast and slow events. Under this assumption, at a given time after perturbation, the system reaches a state on which fast events are relevant, but slow events (such as protein degradation) have a relatively insignificant effect. In this context, we say that the system has reached a pseudo-steady state describing the early events or immediate-early response. Qualitatively, these states can be computed as logical steady states in the Boolean network (V, φ) [Klamt et al., 2006b]. In fact, the discrimination between fast and slow events has an important consequence. Since we focus on fast or early events, it is assumed that oscillation or multi-stability caused by feedbackloops [Remy et al., 2008, Paulevé and[START_REF] Paulevé | Static analysis of boolean networks based on interaction graphs: A survey[END_REF] cannot happen until the second phase of signal propagation occurring at a slower time scale. Therefore, feedback-loops are not included in Boolean logic models of immediate-early response assuming that they will become active in a late phase [START_REF] Macnamara | State-time spectrum of signal transduction logic models[END_REF]. Notably, it follows that starting from any initial state, a Boolean logic model of immediate-early response reaches a unique steady state or fixpoint in polynomial time [START_REF] Paulevé | Static analysis of boolean networks based on interaction graphs: A survey[END_REF]. Thus, such modeling approach, although not capable of capturing dynamical properties, provides a relatively simple framework for input-output predictive models.

Learning Boolean logic models of immediate-early response. Nowadays, for certain biological systems, a graph of causal interactions describing a large-scale signaling network can be retrieved from public databases [START_REF] Guziolowski | Automatic generation of causal networks linking growth factor stimuli to functional cell state changes[END_REF] or by means of statistical methods and experimental data [START_REF] Sachs | Causal protein-signaling networks derived from multiparameter single-cell data[END_REF]. However, functional relationships in signaling networks cannot be captured by means of graph theory only [Klamt et al., 2006b].

In this context and based on the assumptions described above, authors in [START_REF] Saez-Rodriguez | Discrete logic modelling as a means to link protein signalling networks with functional analysis of mammalian signal transduction[END_REF] have proposed a method to learn from an interaction graph and phosphorylation activities at a pseudo-steady state, Boolean logic models of immediate-early response fitting experimental data. Originally, a genetic algorithm implementation was proposed to solve the underlying optimization problem, and a software was provided, CellNOpt [START_REF] Terfve | CellNOptR: a flexible toolkit to train protein signaling networks to data using multiple logic formalisms[END_REF]. Nonetheless, stochastic search methods cannot characterize the models precisely: they are intrinsically unable not just to provide a complete set of solutions, but also to guarantee that an optimal solution is found. Some variations of our problem were addressed using a mathematical programming approach [Mitsos et al., 2009, Sharan and[START_REF] Sharan | Reconstructing Boolean models of signaling[END_REF]. Despite their success to overcome some shortcomings of the genetic algorithm, such as performance and global optimality, the enumeration of all (nearly) optimal solutions was not considered.

More generally, the inference of Boolean networks from time-series gene expression data has been addressed by several authors under different hypotheses and methods [START_REF] Liang | REVEAL, a general reverse engineering algorithm for inference of genetic network architectures[END_REF][START_REF] Akutsu | Inferring qualitative relations in genetic networks and metabolic pathways[END_REF][START_REF] Ideker | Discovery of regulatory interactions through perturbation: inference and experimental design[END_REF][START_REF] Lähdesmäki | On learning gene regulatory networks under the Boolean network model[END_REF]. Recently, some of these methods have been compared in [START_REF] Berestovsky | An evaluation of methods for inferring boolean networks from time-series data[END_REF]. Nonetheless, overall, our work presents some significant differences. To start with, all of them are focused on gene regulatory networks and gene expression time-series data, whereas we work on signaling transduction networks and phosphorylation activities at a pseudo-steady state. Further, they work only with Boolean experimental observations which would correspond to adopt a binary discretization scheme in our framework. Moreover, except for the so-called Best-Fit Extension Problem [START_REF] Lähdesmäki | On learning gene regulatory networks under the Boolean network model[END_REF], they look for Boolean networks fully consistent with the time-series Boolean data. Meanwhile, herein we consider an objective function which describes the goodness of the model based on the numerical data that is subsequently optimized. Finally, all these contributions focus on a "local" inference in the following sense. They aim at learning the Boolean function for each node based on (local) input-output behaviors for such node. In contrast, our learning is based on (global) behaviors over the input-output layers in a network containing non-controllable/non-observable species.

In the remainder of this chapter we provide a precise characterization of this problem using the notions introduced in Chapter 2 and adapting our Answer Set Programming representation accordingly. Furthermore, we validate our approach using real-world signaling pathways in human liver cells and publicly available experimental data.

Problem

Problem

Prior knowledge network and phospho-proteomics dataset

Prior knowledge network. A prior knowledge network is an interaction graph (V, E , σ) as defined in Chapter 2. In addition, we distinguish three special subsets of species in V namely, the stimuli (V S ), the knock-outs (V K ) and the readouts (V R ). Nodes in V S denote extracellular ligands that can be stimulated and thus, we assume they have indegree equal to zero. Nodes in V K denote intracellular species that can be inhibited or knocked-out by various experimental tools such as small-molecule drugs, antibodies, or RNAi. Finally, nodes in V R denote species that can be measured by using an antibody. Notably, species in none of these sets, are neither measured, nor manipulated for the given experimental setup. Let us denote with V U the set of such nodes. Then, except for V R and V K that may intersect, the sets V S ,V K ,V R and V U are pairwise mutually disjoint. An early simplification consists on compressing the PKN in order to collapse most of the nodes in V U . This often results on a significant reduction of the search space that must be explored during learning. Thus, herein we assume a compressed PKN as an input and we refer the interested reader to [START_REF] Saez-Rodriguez | Discrete logic modelling as a means to link protein signalling networks with functional analysis of mammalian signal transduction[END_REF] for more details on this subject.

Phospho-proteomics dataset. Given a PKN (V, E , σ), the concept of an experimental condition over (V, E , σ) is captured by a clamping assignment over variables V S ∪ V K . Recall that clamping assignments were defined in Chapter 2 as partial two-valued assignments. To be more precise, while variables in V S can be clamped to either t or f , variables in V K can only be clamped to f . Next, if C is an experimental condition and v ∈ V S , then

C (v) = t (resp. f ) indicates that the stimulus v is present (resp. absent), while if v ∈ V K , then C (v) = f indicates
that the species v is inhibited or knocked out. In fact, since extracellular ligands by default are assumed to be absent, for the sake of simplicity we can omit clampings to f over variables in V S . Therefore, if C is an experimental condition and v ∈ d om(C ) then, either v ∈ V S and

C (v) = t , or v ∈ V K and C (v) = f
. Furthremore, the concept of an experimental observation under an experimental condition C is captured by a partial mapping

P C : V R � → [0, 1]. That is, d om(P C ) ⊆ V R denotes the set of measured readouts under the experimental condition C . If v ∈ d om(P C ), then P C (v)
represents the phosphorylation activity (at a pseudo-steady state) of the readout v under C . Notably, it is rather critical to choose a time point that is characteristic for the fast or early events in the biological system under consideration [START_REF] Macnamara | State-time spectrum of signal transduction logic models[END_REF]. Since phosphorylation assays represents an average across a population of cells, the phosphorylation activity for each readout is usually normalized to [0, 1]. Finally, an experimental dataset ξ is a finite set of pairs (C i , P C i ) with experimental conditions C i and experimental observations P C i . Further, we denote with N ξ the size of ξ given by the number of measured readouts across all experimental conditions i = 1, . . . , n, i.e.,

N ξ = � n i =1 � � d om(P C i ) � � .
Let us illustrate the concepts described above with our toy example in correspond to activations and inhibitions, respectively. Green nodes represent ligands that can be experimentally stimulated (V S ). Red nodes represent species that can be inhibited or knocked out (V K ). Blue nodes represent species that can be measured (V R ). White nodes are neither measured, nor manipulated (V U ).

and V R = { f , g }. Furthermore, let ξ = ((C 1 , P C 1 ), . . . , (C 4 , P C 4 )) be an example experimental dataset over (V, E , σ) defined by

C 1 = {a � → t , c � → t } P C 1 = { f � → 0.9, g � → 0.0} C 2 = {a � → t , c � → t , d � → f } P C 2 = { f � → 0.1, g � → 0.9} C 3 = {a � → t } P C 3 = { f � → 0.0, g � → 0.1} C 4 = {a � → t , b � → t } P C 4 = { f � → 1.0, g � → 0.8}. (3.1)
In words, the experimental conditions C 1 , . . . ,C 4 can be read as follows. In C 1 , stimuli a and c are present, stimulus b is absent and

d is not inhibited; in C 2 , stimuli a, b, c are like in C 1 but d is inhibited; in C 3 ,

Problem

Boolean input-output predictions

Let (V, E , σ) be a PKN. Further, let ξ = (C i , P C i ) be an experimental dataset over (V, E , σ) with i = 1, . . . , n. As detailed above, a Boolean logic model of immediate-early response is defined by a logical network (V, φ) without feedback-loops and using classical (Boolean) logics. Hence, now we can define the predictions (output) provided by a Boolean logic model of immediateearly response with respect to a given set of experimental conditions (input). Towards this end, we rely on our framework introduced in Chapter 2 and characterize the response of logical networks using fixpoint semantics. More precisely, for i = 1, . . . , n let F i be the fixpoint of

Ω (V,φ| C i ) reachable from A f = {v � → f | v ∈ V }.
Notice that such a fixpoint always exists given that (V, φ) is free of feedback-loops. In words, each F i describe the logical response (starting from A f ) of (V, φ) with respect to the experimental condition or clamping assignment C i .

Next, we define a straightforward transformation from truth values to binary but numerical values. Such a transformation provides a more convenient notation in order to compare predictions and phosphorylation activities. The Boolean prediction of (V, φ) with respect to the experimental condition C i is a function π i : V → {0, 1} defined as

π i (v) = � 1 if F i (v) = t 0 if F i (v) = f .
As we see below, during learning we aim at explaining the given experimental dataset ξ. Therefore, we are particularly interested in predictions with respect to the experimental conditions included in ξ and over the measured variables in each experimental condition. Nevertheless, predictions with respect to non-performed experimental conditions and/or over non-observed species can be useful to generate testable hypotheses on the response of the system.

As an example, consider the Boolean logic model (V, φ) from Figure 3.1c and the experimental condition C 2 from the dataset given in (3.1). Then, the clamped logical network (V, φ| C 2 ) is defined by the mapping

φ| C 2 = {a � → �; b � → ⊥; c � → �; d � → ⊥; e � → b ∨ c; f � → d ∧ e; g � → e ∧ ¬c}.
Next, the fixpoint of Ω (V,φ| C 2 ) reachable from A f can be computed as detailed in Chapter 2 yielding the assignment F 2 defined as

F 2 = {a � → t , b � → f , c � → t , d � → f , e � → t , f � → f , g � → f }.
Finally, the Boolean prediction for (V, φ) under the experimental condition C 2 is given by

π 2 = {a � → 1, b � → 0, c � → 1, d � → 0, e � → 1, f � → 0, g � → 0}.

Learning Boolean logic models

Search space. We aim at learning Boolean logic models from a PKN and an experimental dataset. In fact, any learned model has to be supported by some evidence in the prior knowledge. To be more precise, given a PKN (V, E , σ) we consider only Boolean logic models (V, φ) without feedback-loops and such that, for each variable v ∈ V , if w occurs positively (resp. negatively) in φ(v) then, there exists an edge (w, v) ∈ E and ((w, v), 1) ∈ σ (resp. ((w, v), -1) ∈ σ).

Towards this end, we consider a pre-processing step where the given PKN is expanded to generate a (signed) directed hypergraph describing all plausible logical interactions. For each v ∈ V having non-zero indegree, let P r ed (v) be the set of its (signed) predecessors, namely, P r ed

(v) = {(u, s) | (u, v) ∈ E , ((u, v), s) ∈ σ}.
Furthermore, let P (v) be the powerset of P r ed (v), namely, 2 P r ed (v) . Then, (V, H ) is the (signed) directed hypergraph expanded from (V, E , σ) with nodes V and (signed) directed hyperedges

H if for each v ∈ V , (p, v) ∈ H whenever p ∈ P (v).
Next, Boolean logic models must essentially result from pruning (V, H ). Additionally, we impose two constraints related to the fact that our Boolean logic models essentially aim at providing a framework for input-output predictions.1 Firstly, for any variable u defined in φ all variables w ∈ φ(u) must be reachable from some stimuli variable. That is, we consider only Boolean logic models (V, φ) such that for every u ∈ d om(φ) and w ∈ φ(u), either w ∈ V S or there exist v ∈ V S and a path from v to w in the underlying interaction graph Σ (V,φ) . Secondly, every variable u defined in φ must reach some readout variable. That is, we consider only Boolean logic models (V, φ) such that for every u ∈ d om(φ) there exist v ∈ V R and a path from u to v in the underlying interaction graph Σ (V,φ) . Finally, let us denote with M (V,E ,σ) the search space of Boolean logic models satisfying the conditions given above: evidence in (V, E , σ), no feedback-loops and reachability from/to stimuli/readouts.

In Figure 3.1 we show an exemplary PKN (Figure 3.1a) and the corresponding expanded (signed) directed hypergraph (Figure 3.1b). As described in Chapter 2, (signed) directed hypergraphs can be directly linked to logical networks. Thus, by considering each (signed) directed hyperedge in Figure 3.1b as either present or absent (and verifying the additional constraints with respect to feedback-loops and reachability from/to stimuli/readouts), one can generate the search space of Boolean logic models M (V,E ,σ) .

Lexicographic multi-objective optimization. For a given PKN (V, E , σ), there are exponentially many candidate Boolean logic models (V, φ) having an evidence on it. Therefore, authors in [START_REF] Saez-Rodriguez | Discrete logic modelling as a means to link protein signalling networks with functional analysis of mammalian signal transduction[END_REF] put forward the idea of training Boolean logic models by confronting their corresponding Boolean predictions with phosphorylation activities at a pseudo-steady state. In this context, two natural optimization criteria arise in order to conduct the learning: (1) model accuracy (biologically meaningful), and (2) model complexity (Occam's razor principle). In fact, this is a typical scenario on automatized learning of predictive models [START_REF] Freitas | A critical review of multi-objective optimization in data mining[END_REF].

Problem

We now provide the precise formulation for each optimization criteria. Let (V, E , σ) be a PKN. Let ξ = (C i , P C i ) be an experimental dataset over (V, E , σ) with i = 1, . . . , n. Let (V, φ) be a Boolean logic model having evidence in (V, E , σ) and let π 1 , . . . , π n be its Boolean predictions with each π i defined under C i . Firstly, based on the residual sum of squares (RSS) we define the residual (Θ r ss ) of (V, φ) with respect to ξ as

Θ r ss ((V, φ), ξ) = n � i =1 � v∈d om(P C i ) (P C i (v) -π i (v)) 2 . (3.2)
Secondly, for a given logical formula φ(v), let us denote its length by |φ(v)|. Then, we define the size (Θ si ze ) of (V, φ) as

Θ si ze ((V, φ)) = � v∈d om(φ) |φ(v)|. (3.3)
A popular and relatively simple approach to cope with multi-objective optimization is to transform it into a single-objective optimization. Towards this end, one usually combines all criteria by defining a function using free parameters in order to assign different weights to each criterion. In fact, this is exactly the approach adopted in [START_REF] Saez-Rodriguez | Discrete logic modelling as a means to link protein signalling networks with functional analysis of mammalian signal transduction[END_REF]. Therein, a single-objective function is defined that balances residual and size using a parameter α chosen to maximize the predictive power of the model. Moreover, it has been shown that "predictive power" is best for α < 0.1. However, as detailed in [START_REF] Freitas | A critical review of multi-objective optimization in data mining[END_REF], this approach suffers from known drawbacks. First, it depends on "magic values" for each weight often based on intuition or empirically determined. Second, it combines different scales of measurements that need to be normalized. Third, it combines non-commensurable criteria producing meaningless quantities. On the other hand, the lexicographic approach allows us to assign different priorities to different objectives in a qualitative fashion. Notably, in our context logic models providing high predictive power are significantly more relevant than the sizes of such models. Thus, the lexicographic approach is very convenient to cope with the multi-objective nature of our optimization problem. Yet another popular approach is to look for Pareto optimal models. However, this method will lead to a large number of models providing either none or very low predictive power. For example, consider the Boolean logic model (V, φ) with φ = �, i.e. the empty model. Such a model is trivially consistent with any input PKN (V, E , σ) while it minimizes the objective function size, i.e. Θ si ze ((V, φ)) = 0. Therefore, (V, φ) is Pareto optimal although it does not provide any valuable information.

Similarly, one can show that many other (non-empty) models will be Pareto optimal as well although they provide very low predictive power. Hence, Pareto optimality is not well suited for our problem. Notwithstanding, other multi-objective optimization methods (cf. [START_REF] Marler | Survey of multi-objective optimization methods for engineering[END_REF]) could be investigated in the future. To conclude, our lexicographic multiobjective optimization consists of minimizing first Θ r ss , and then with lower priority Θ si ze :

(V, φ opt ) ∈ arg min (V,φ)∈M (V,E ,σ) (Θ r ss ((V, φ), ξ), Θ si ze ((V, φ))). (3.4)
Enumeration of (nearly) optimal models. Information provided by high-throughput data is intrinsically uncertain due to experimental errors. Therefore, one is not only interested in optimal models but in nearly optimal models as well. In this context, authors in [START_REF] Saez-Rodriguez | Discrete logic modelling as a means to link protein signalling networks with functional analysis of mammalian signal transduction[END_REF] have considered Boolean logic models minimizing their objective function within certain tolerance, e.g. 10% of the minimum. Next, they argue that all models found can explain the data similarly or equally well if one take into account the experimental error. Notice that, in the aforecited work the optimization is addressed using a genetic algorithm. Hence, "minimum" refers to the one found during the execution of the algorithm which is not necessarily the global minimum. Moreover, due to the incompleteness of stochastic search methods, it is very likely that certain solutions within the allowed tolerance are not found.

In practice, one can execute the genetic algorithm several times in order to overcome this issue to some extent. Nonetheless, as we have shown in [START_REF] Guziolowski | Exhaustively characterizing feasible logic models of a signaling network using Answer Set Programming[END_REF], a significant number of models may be missing even after several executions. Similarly but in the context of quantitative modeling (based on ordinary differential equations) and using a simulated annealing algorithm, authors in [START_REF] Chen | Input-output behavior of ErbB signaling pathways as revealed by a mass action model trained against dynamic data[END_REF] have elaborated upon the same argument. Interestingly, despite the fact that the model appears to be non-identifiable in both contexts, viz. qualitative and quantitative modeling, biologically relevant insights have been reported in the two aforecited studies. Notably, minimization over size in (3.4) is based on Occam's razor principle. On the one hand, one can consider that larger logic models overfit the available dataset by introducing excessive complexity [START_REF] Saez-Rodriguez | Discrete logic modelling as a means to link protein signalling networks with functional analysis of mammalian signal transduction[END_REF][START_REF] Prill | Crowdsourcing network inference: the DREAM predictive signaling network challenge[END_REF].

On the other hand, one can argue that it is actually necessary to consider such "spurious" links in order to capture cellular robustness and complexity [START_REF] Stelling | Robustness of cellular functions[END_REF]. Therefore, let (V, φ opt ) be a Boolean logical model as defined in (3.4). Then, considering that tolerance over residual and size may yield biologically relevant models, we are particularly interested in enumerating all (nearly) optimal Boolean logic models (V, φ) such that,

Θ r ss ((V, φ), ξ) ≤ Θ r ss ((V, φ opt ), ξ) + t r ss Θ si ze ((V, φ)) ≤ Θ si ze ((V, φ opt )) + t si ze
with t r ss and t si ze denoting the tolerance over residual and size, respectively.

Logical input-output behaviors. Next, we introduce the notion of logical input-output behaviors. As we show below, in practice the enumeration of (nearly) optimal models often leads to a large number of logical networks, namely, (V, φ j ) with j = 1, . . . , m and m � 1. Notably, each φ j is a different mapping from variables to propositional formulas. However, it may happen (and it often happens) that for all v ∈ V R , several logical networks describe exactly the same response to every possible experimental condition (clamping assignments over variables V S ∪ V K ). In such a case, we say that those logical networks describe the same input-output behavior. To be more precise, recall that we consider a PKN (V, E , σ).

Notice that in each experimental condition over (V, E , σ), every stimulus v ∈ V S and inhibitor v ∈ V K , can be either clamped or not. Thus, let us denote with C the space of all possible clamping assignments or experimental conditions C i over (V, E , σ). Notably, the number of possible clamping assignments is given by |C | = 2 |V S |+|V K | . Then, let (V, φ j ), (V, φ j � ) be two (nearly) optimal Boolean logic models. Furthermore, let F j i and F j � i be the fixpoints of Ω (V,φ j | C i ) and Ω (V,φ j � | C i ) reachable from A f , respectively. We say that (V, φ j ) and (V, φ j � ) describe the same logical input-output behavior if and only if

F j i (v) = F j � i (v) for all v ∈ V R and C i ∈ C .
Importantly, this abstraction allows us to group logical networks regardless of their "internal wirings" and focus on their input-output predictions. In practice, this also facilitates the analysis and interpretation of results whereas it provides a way to extract robust insights despite the high variability.

Learning Boolean logic models with Answer Set Programming

In order to express and solve the multi-objective optimization described in (3.4) by using ASP, one needs to discretize the function defined in (3.2). A very simple approach converts numerical data into binary data according to a threshold. Furthermore, we propose a finer multi-valued discretization scheme. In fact, the only non-integer variables in (3.2) are the experimental observations P C i (v). Then, we approximate these values up to 1 10 k introducing a parametrized approximation function δ k (e.g. using the floor or closest integer functions). Next, we define the discrete residual Θ r ss k as

Θ r ss k ((V, φ), ξ) = n � i =1 � v∈d om(P C i ) � 10 k δ k (P C i (v)) -10 k π i (v) � 2 . (3.5)
The minimizations of Θ r ss and Θ r ss k may yield different Boolean logic models. Nonetheless, one can prove that finding all models minimizing Θ r ss k within a certain tolerance allows us to find all models minimizing Θ r ss as well. To be more precise, one proves the following result.

Proposition 3.3.1. Let (V, E , σ) be a PKN. Let ξ be an experimental dataset over (V, E , σ) with size N ξ . Let k ∈ N define the discretization scheme. Let us denote with µ and µ k , the corresponding minima for Θ r ss and Θ r ss k over the space of models M (V,E ,σ) with respect to ξ:

µ = min (V,φ)∈M (V,E ,σ) Θ r ss ((V, φ), ξ) µ k = min (V,φ)∈M (V,E ,σ) Θ r ss k ((V, φ), ξ).
Then 10 -2k µ k converges to µ when k increases, with an exponential speed:

µ k = 10 2k µ + O(10 k ).
Moreover, any Boolean logic model minimizing Θ r ss , also minimizes Θ r ss k within the following tolerance t k :

t k = 2 � N ξ µ k + N ξ µ k .
Notice that µ k increases exponentially with k. Furthermore, in practice, µ k is significantly greater than N ξ provided that k ≥ 1. Thus, the tolerance t k is relatively small, for instance 0.1, i.e. 10% of µ k . Next, we aim at enumerating all (nearly) optimal Boolean logic models (V, φ)

such that, Θ r ss k ((V, φ), ξ) ≤ Θ r ss k ((V, φ opt ), ξ) + t r ss Θ si ze ((V, φ)) ≤ Θ si ze ((V, φ opt )) + t si ze
with t r ss and t si ze the tolerances over (discrete) residual and size, respectively.

Instance

Let (V, E , σ) be a PKN and let (V, H ) be the directed hypergraph expanded from it. Recall that with P (v) we denote the powerset of the signed predecessors of v ∈ V , namely, 2 P r ed (v) .

We represent the directed hypergraph (V, H ) using predicates node/2, hyper/3, and edge/3. The facts node(v,s P (v) ) map nodes v ∈ V to their corresponding sets of signed predecessors P (v), facts hyper(s P (v) ,s p ,l ) associate P (v) with its sets p ∈ P (v) where l denotes their cardinalities, facts edge(s p ,v,1) associate the set p with (v, 1) ∈ p, and facts edge(s p ,v,-1) associate the set p with (v, -1) ∈ p. Note that each s (•) stands for some arbitrary but unique name in its respective context here. Facts over predicates stimulus/1, inhibitor/1, and readout/1 denote nodes in V S , V K , and V R respectively. Next, let ξ = (C i , P C i ) be an experimental dataset over (V, E , σ) with i = 1, . . . , n. Recall that each C i is a clamping assignment over variables in V S ∪ V K . Then, we extend our representation of clamping assignments given in Chapter 2 in order to consider several experimental conditions simultaneously. Towards this end, we represent experimental conditions as facts over predicate clamped/3, namely

clamped(i ,v,C i (v)) for all v ∈ d om(C i ) and i = 1, . . . , n.
Finally, let k define the discretization scheme. We represent discretized experimental observations as facts over predicate obs/3, namely, obs(i ,v,10 k δ k (P C i (v))) for all v ∈ d om(P C i ) and i = 1, . . . , n. We use the predicate dfactor/1 to denote the discretization factor 10 k .

Using the discretization scheme provided by k = 1, Listing 3.1 shows the instance representation for our toy example. That is, the (signed) directed hypergraph in Figure 3.1b and the dataset given in (3.1).

Listing 3.1: Toy example input instance (toy.lp)

node (e ,1) . node (d ,2) . node (g ,3) . node (f ,4) . node (a ,5) . node (b ,6) . node (c ,7) .

hyper (1 ,1 ,1) . hyper (2 ,1 ,1) . hyper (1 ,8 ,2) . hyper (2 ,13 ,2) . hyper (1 ,2 ,1) . hyper (2 ,4 ,1) . hyper (1 ,9 ,2) . hyper (2 ,11 ,2) . hyper (1 ,3 ,1) . hyper (2 ,5 ,1) . hyper (1 ,10 ,2) . hyper (2 ,12 ,2) . hyper (3 ,5 ,1) . hyper (4 ,6 ,1) . hyper (3 ,14 ,2) . hyper (1 ,16 ,3) . hyper (3 ,6 ,1) . hyper (4 ,7 ,1) . hyper (4 ,15 ,2) . hyper (2 ,17 ,3) .

edge (1 ,b ,1) . edge (2 ,c ,1) . edge (3 ,g , -1) . edge (4 ,a ,1) . edge (5 ,c , -1) . edge (6 ,e ,1) . edge (7 ,d ,1) . edge (8 ,b ,1) . edge (8 ,c ,1) . edge (9 ,b ,1) . edge (9 ,g , -1) . edge (10 , c ,1 ) . edge (10 , g , -1) . edge (11 , a ,1) . edge (11 , b ,1) . edge (12 , a ,1) . edge (12 , c , -1) . edge (13 , b ,1) . edge (13 , c , -1) . edge (14 , e ,1) . edge (14 , c , -1) . edge (15 , d ,1) . edge (15 , e ,1) . edge (16 , b ,1) . edge (16 , c ,1) . edge (16 , g , -1) . edge (17 , a ,1) . edge (17 , b ,1) . edge (17 , c , -1) .

clamped (1 ,a ,1) . clamped (1 ,c ,1) .

obs (1 ,f ,9) . obs (1 ,g ,0) . clamped (2 ,a ,1) . clamped (2 ,c ,1) . clamped (2 ,d , -1) . obs (2 ,f ,1) . obs (2 ,g ,9 ) . clamped (3 ,a ,1) .

obs (3 ,f ,0) . obs (3 ,g ,1) . clamped (4 ,a ,1) . clamped (4 ,b ,1) .

obs (4 ,f ,10) . obs (4 ,g ,8) .

stimulus ( a ) . stimulus ( b ) . stimulus ( c ) . inhibitor ( d ) . readout ( f ) . readout ( g ) .

dfactor (10) .

Encoding

Next we describe our encoding for solving the learning of Boolean logic models as described in the previous section. Our ASP encoding is shown in Listing 3.2.

Listing 3.2: Logic program for learning Boolean logic models (learning.lp)

variable ( V ) : -node (V , _ ) . formula (V , I )
: -node (V , I ) ; hyper (I ,_ , _ ) . { dnf (I , J ) : hyper (I ,J , N ) } : -formula (V , I ) . clause (J ,V , S )

: -edge (J ,V , S ) ; dnf (_ , J ) .

path (U , V ) : -formula (V , I ) ; dnf (I , J ) ; edge (J ,U , _ ) . path (U , V ) : -path (U , W ) ; path (W , V ) . : -path (V , V ) . : -dnf (I , J ) ; edge (J ,V , _ ) ; not stimulus ( V ) ; not path (U , V ) : stimulus ( U ) . : -path (_ , V ) ; not readout ( V ) ; not path (V , U ) : readout ( U ) .

exp ( E ) : -clamped (E ,_ , _ ) . clamped (E ,V , -1) : -exp ( E ) ; stimulus ( V ) ; not clamped (E ,V ,1) . clamped (E , V ) : -clamped (E ,V , _ ) . free (E ,V , I ) : -formula (V , I ) ; dnf (I , _ ) ; exp ( E ) ; not clamped (E , V ) .

eval (E ,V , S ) : -clamped (E ,V , S ) . eval (E ,V , 1) : -free (E ,V , I ) ; eval (E ,W , T ) : edge (J ,W , T ) ; dnf (I , J ) . eval (E ,V , -1) : -not eval (E ,V ,1) ; exp ( E ) ; variable ( V ) .

rss (D ,V , 1 , (F -D ) **2) : -obs (E ,V , D ) ; dfactor ( F ) . rss (D ,V , -1 , D **2) : -obs (E ,V , D ) .
# minimize { L@1 , dnf ,I , J : dnf (I , J ) , hyper (I ,J , L ) }. # minimize { W@2 , rss ,E , V : obs (E ,V , D ) , eval (E ,V , S ) , rss (D ,V ,S , W ) }.

: -formula (V , I ) ; hyper (I , J1 , N ) ; hyper (I , J2 , M ) ; N < M , dnf (I , J1 ) ; dnf (I , J2 ) ; edge ( J2 ,U , S ) : edge ( J1 ,U , S ) .

: -formula (V , I ) ; dnf (I , J ) ; edge (J ,U , S ) ; edge (J ,U , -S ) .

# const maxsize = -1. # const maxrss = -1.

: -maxsize >= 0; maxsize + 1 # sum {L , dnf ,I , J : dnf (I , J ) , hyper (I ,J , L ) }.

: -maxrss >= 0; maxrss + 1 # sum {W , rss ,E , V : obs (E ,V , D ) , eval (E ,V , S ) , rss (D ,V ,S , W ) }.

# show formula /2. # show dnf /2. # show clause /3.

Guessing logical networks. Lines 1-4 define rules generating the representation of a logical network as described in Chapter 2. Line 1 simply projects node names to the predicate variable/1. In Line 2 every node v ∈ V having non-zero indegree is mapped to a formula φ(v). Next, in Line 3 each set of signed predecessors p ∈ P (v) is interpreted as an abducible conjunctive clause in φ(v). Then, if p ∈ P (v) has been abduced, in Line 4 predicates clause/3 are derived for every signed predecessor in p. 2 Let us illustrate this on our toy example. In order to describe the mappings e � → b ∨c and g � → e ∧¬c, one would generate a candidate answer set with atoms dnf(1,1), dnf(1,2) and dnf (3,14) (from Line 2 we derive formula(e,1) and formula(g,3)). Note that this also force to have atoms clause(1,b,1), clause(2,c,1), clause(14,e,1) and clause(14,c,-1). Lines 6-8 eliminate candidate answer sets describing logic models with feedback-loops. Paths from u to v are represented over predicate path/2 and derived recursively. Thus, the integrity constraint in Line 8 avoids self-reachability in the Boolean logic models. Next, the constraint in Line 9 ensures that for any variable u defined in φ all variables w ∈ φ(u) are reachable from some stimuli variable. Whereas the constraint in Line 10 guarantees that every variable u defined in φ reaches some readout variable. Notice that at this point, we have a representation of the search space of Boolean logic models M (V,E ,σ) .

Fixpoint, residuals, and optimization. Lines 12-19 elaborate on the rules Π 2.3 , Π 2.4 and Π 2.5 given in Chapter 2 in order to consider several clamping assignments simultaneously and compute the fixpoint for each of them accordingly. To be more precise, the response under each experimental condition is represented over predicates eval/3, namely eval(i ,v,s)

for experimental condition C i if variable v is assigned to s. In Lines 21-22 we compute the possible differences (square of residuals) between Boolean predictions and the corresponding experimental observations. We denote such differences over predicate rss/4, namely rss(o,v,t,r ) for a residual r with respect to the experimental observation o if the Boolean prediction for v ∈ V is the truth value t ∈ {1, -1}. Note that such predicates are independent from every candidate answer set, that is, they can be deduced during grouding. For our 3.3. Learning Boolean logic models with Answer Set Programming example, due to the experimental condition C 2 we have rss(1,f,1,81), rss(1,f,-1,1), rss(9,g,1,1) and rss(9,g,-1,81). Therefore, if the fixpoint for f under the experimental condition C 2 is 1, the residual would be 81, whereas if the fixpoint is -1, the residual is only 1.

Analogously, but in the opposite way the same holds for g . Next, we describe our lexicographic multi-objective optimization. In Line 24 we declare with lower priority (@1) the minimization over the size of logic models (Eq. (3.3)). Meanwhile, in Lines 25 we declare, with higher priority (@2), the minimization of the residual sum of squares between the Boolean predictions and experimental observations (Eq. (3.5)).

Symmetry breaking. Lines 27-30 define two relatively simple symmetry-breaking constraints which are particularly relevant during the enumeration of (nearly) optimal solutions. Essentially, these integrity constraints eliminate answer sets describing "trivially" equivalent Boolean logic models with respect to their logical input-output behavior. The constraint in Lines 27-28 eliminate solutions by checking inclusion between conjunctions. For example, for two variables v and w, the formula v ∨ (v ∧ w) is logically equivalent to v and hence, the latter is preferred. The constraint in Line 30 simply avoids solutions having mappings in the Boolean logic models of the form v ∧¬v. Recall that contradictory causal interactions can be present in the PKN yielding such a formula. Notably, other logical redundancies could be considered as well. However, a complete treatment of redundancies would lead to the NP-complete problem known as minimization of Boolean functions [START_REF] Mccluskey | Minimization of Boolean functions[END_REF] Enumeration. Lines 32-39 define a rather "standard" mechanism in order to enumerate solutions within given boundaries. Lines 32-33 simply define two constants describing the boundaries for each optimization criterion which are by default set to -1. Lines 35-36 define an integrity constraint in order to eliminate solutions describing Boolean logic models (V, φ)

if maxsize ≥ 0 and maxsize + 1 ≤ Θ si ze ((V, φ)). Analogously, Lines 37-39 define an integrity constraint in order to eliminate solutions describing Boolean logic models (V, φ) if maxrss ≥ 0 and maxrss + 1 ≤ Θ r ss k ((V, φ), ξ).

The following result shows the correctness of our ASP representation. We denote with τ((V, E , σ), ξ, k) the set of facts describing the instance as in Listing 3.1, and with Π 3.2 the set of rules given in Listing 3.2.

Proposition 3.3.2. Let (V, E , σ) be a PKN. Let ξ = (C i , P C i ) be an experimental dataset over (V, E , σ
) and let k define the discretization scheme.

Then, there is an answer set X of τ((V, E , σ), ξ, k) ∪ Π 3.2 such that

φ opt = � v � → � p∈P (v) � � (w,1)∈p w � ∧ � � (w,-1)∈p ¬w � � � � � � dnf(s P (v) , s p ) ∈ X , v ∈ V � if and only if (V, φ opt ) ∈ arg min (V,φ)∈M (V,E ,σ) (Θ r ss k ((V, φ), ξ), Θ si ze ((V, φ))).

Solving

Optimization. In Listing 3.3 we show the optimum answer set found for the toy instance described in Listing 3.1. 3 In this case, the optimum answer set is the thirteenth answer set inspected by the solver (Answer: 13). Such answer set describes the Boolean logic model given in Fig. 3.1c. Furthermore, the values for the optimization criteria are given ordered by their priorities (Optimization: 88 7). That is, 88 for the discretized residual sum of squares (Eq. (3.5)), and 7 for the model size (Eq. (3.3)).

Listing Enumeration. Next, the enumeration capabilities of an ASP solver like clasp [START_REF] Gebser | clasp: A conflict-driven answer set solver[END_REF] can be used to find not only one optimal model but all (nearly) optimal models as described earlier. Considering tolerance t r ss = 8 (∼ 10% of the optimum residual sum of squares) and size tolerance t si ze = 3, we enumerate all models such that

Θ r ss k ((V, φ), ξ) ≤ Θ r ss k ((V, φ opt ), ξ) + t r ss = 96 Θ si ze ((V, φ)) ≤ Θ si ze ((V, φ opt )) + t si ze = 10.
In this example, there are 5 (nearly) optimal Boolean logic models as we show in Listing 3.4. 4Interestingly, even for this small example, the symmetry-breaking constraints make a significant difference. We note that running the same program but without the symmetry-breaking constraints, yields 17 Boolean logic models instead of only 5. Notably as we show below, in real-world problem instances, exploiting these symmetries significantly reduces the number of solutions (without missing any input-output behavior) and hence, it facilitates their post processing and interpretation.

Finding input-output behaviors with Answer Set Programming

Once we have enumerated all (nearly) optimal Boolean logic models with respect to certain tolerances, we can use ASP in order to identify the logical input-output behaviors they describe. Towards this end, we have developed a simple algorithm that (using ASP) systematically compares all pairs of models looking for at least one experimental condition, i.e. a clamping assignment, generating a different response over the readouts nodes. If such an experimental condition exists, the solver will return SAT (the logic program is SATISFIABLE), meaning that the two models at hand have a different input-output behavior. Otherwise, the solver will return UNSAT (the logic program is UNSATISFIABLE), meaning that they have the same logical input-output behavior. In what follows we show the ASP representation and the developed algorithm.

Instance

The representation of the problem instance is a straightforward extension from the one described in Listing 2.1 in order to describe a pair of logical networks. To be more precise, instead of having facts over predicates formula/2, we consider facts over predicates formula/3 as follows. Let (V, φ j ), (V, φ j � ) be two (nearly) optimal Boolean logic models. The facts formula( j ,v,s φ j (v) ) (resp. formula( j � ,v,s φ j � (v) )) map variables v ∈ V to their corre- sponding formulas φ j (v) (resp. φ j � (v)). Meanwhile, facts over predicates variable/1, dnf/2 and clause/3 remain the same as in Listing 2.1.

Encoding

Next we describe our encoding for deciding whether given two Boolean logic models, there exists at least one experimental condition or clamping assignment generating a different response over the readout nodes. Our ASP encoding is shown in Listing 3.5.

Listing 3.5: Logic program for finding input-output behaviors (behaviors.lp)

{ clamped (V , 1) } : -stimulus ( V ) . { clamped (V , -1) } : -inhibitor ( V ) .

clamped (V , -1) : -stimulus ( V ) , not clamped (V ,1) .

model ( M )

: -formula (M ,_ , _ ) . clamped ( V ) : -clamped (V , _ ) . free (M ,V , I ) : -formula (M ,V , I ) ; not clamped ( V ) . eval (M ,V , S ) : -clamped (V , S ) ; model ( M ) . eval (M ,V , 1) : -free (M ,V , I ) ; eval (M ,W , T ) : clause (J ,W , T ) ; dnf (I , J ) . eval (M ,V , -1) : -not eval (M ,V ,1) ; model ( M ) ; variable ( V ) . diff : -eval ( M1 ,V , S ) ; eval ( M2 ,V , -S ) ; M1 < M2 ; readout ( V ) ; model ( M1 ; M2 ) .

: -not diff

Lines 1-3 generate (all) possible clamping assignments or experimental conditions. Next, analogously to what we have shown in Listing 3.2, Lines 5-11 elaborate on the the rules Π 2.3 , Π 2.4 and Π 2.5 given in Chapter 2 in order to consider several logical networks simultaneously and compute for each of them, the corresponding fixpoint under the abduced clamping assignment. To be more precise, the response under the abduced clamping assignment is represented over predicates eval/3, namely eval( j ,v,s) for the logical network j if variable v is assigned to s. Afterwards, Line 13 derives the constant predicate diff if there exists at least one readout v for which the fixpoints of each logical network do not agree. Notice the use of M1 < M2 instead of M1 != M2 in oder to avoid a duplicated (symmetric) constraint. Finally, we use an integrity constraint in Line 15 which forces the solver to exhaustively look for a clamping assignment allowing for the derivation of diff. See the following section for more details on how one should use this encoding and interpret its result.

The following result shows the correctness of our ASP representation. We denote with τ((V, φ j ), (V, φ j � )) the set of facts describing (V, φ j ) and (V, φ j � ) as detailed above, and with Π 3.5 the set of rules given in Listing 3.5. Proposition 3.4.1. Let (V, φ j ), (V, φ j � ) be two Boolean logic models.

Then, there is an answer set of τ((V, φ j ), (V,

φ j � )) ∪ Π 3.5 if and only if there exist C i ∈ C , v ∈ V R such that F j i (v) � = F j � i (v).

Solving

The idea for finding logical input-output behaviors is to compare Boolean logic models by pairs using the encoding in Listing 3.5. Then, the program given by τ((V, φ j ), (V, φ j � )) together with the rules in Listing 3.5, is SATISFIABLE if and only if the constant predicate diff can be derived, i.e., there exists at least one clamping assignment generating a different response over the readouts. Otherwise, the program is UNSATISFIABLE and hence, we can deduce that (V, φ j ) and (V, φ j � ) have the same logical input-output behavior. The developed algorithm (in pseudo-code) implementing this idea is shown in Algorithm 1. We assume an auxiliary Algorithm 1 Finding input-output behaviors over a set of M Boolean logic models for (V, φ j ) ∈ M do 4:

f ound ← F al se 5:

for (V,

φ j � ) ∈ B do 6: if GRINGO-CLASP((V , φ j ), (V, φ j � )) == U N S AT then 7:
f ound ← T r ue � j and j � have the same logical input-output behavior return B 16: end function procedure GRINGO-CLASP, such that GRINGO-CLASP( j , j � ) translates (V, φ j ) and (V, φ j � ) into the set of facts τ((V, φ j ), (V, φ j � )) and then it executes the grounder and solver combining τ((V, φ j ), (V, φ j � )) with the rules from Listing 3.5. 5 The algorithm keeps in the (initially empty) set B, one "representative" Boolean logic model for each of the input-output behaviors found.

Then, for every model (V, φ j ) in the set M of Boolean logic models, the algorithm calls GRINGO-CLASP((V , φ j ), (V, φ j � )) for (V, φ j � ) ∈ B (representative models of input-output behaviors found in previous iterations) until GRINGO-CLASP returns U N S AT or until all models in B have been considered. If for some (V, φ j � ), the call GRINGO-CLASP((V , φ j ), (V, φ j � )) returns U N S AT , we set f ound to T r ue and we break the loop. Next, in Line 11 we skip the if block and we continue with the next model (V, φ j ) ∈ M . On the other hand, if GRINGO-CLASP((V , φ j ), (V, φ j � )) returns

S AT for all (V, φ j � ) ∈ B , we enter in the if block of Line 11 and we add the model (V, φ j ) to the set representative Boolean logic models B. Following with our example from the previous section, over the 5 (nearly) optimal Boolean logic models enumerated in Listing 3.4, we found 3 logical input-output behaviors. Furthermore, with a slight modification to the given algorithm, one can also find that in this example, one behavior is described by exactly one model whereas the other two behaviors are described by two models each. As we show in our empirical evaluation, the number of Boolean logic models describing the same input-output behavior can vary significantly in real-world examples. In fact, this raise the question of whether certain logical input-output behaviors should be considered as more relevant than others due to the number of Boolean logic models describing them. 3.5 Empirical evaluation

Real-world problem instance

Prior knowledge network. We evaluate our approach using real-world signaling pathways in human liver cells. The (compressed) PKN (V, E , σ), shown in Figure 3.2, was introduced in [Saez- Rodriguez et al., 2009] and here we use a variation from [START_REF] Morris | Training signaling pathway maps to biochemical data with constrained fuzzy logic: quantitative analysis of liver cell responses to inflammatory stimuli[END_REF]. It contains 31 nodes (V ) describing biological species: 7 stimuli (V S ), 7 inhibitors (V K ), 15 readouts (V R ), and 6 neither controlled nor observed (V U ). Notice that

V K ∩ V R � = �, namely V K ∩ V R = {GSK 3, M E K 12, J N K 12, p38}.
Furthermore, 53 signed and directed edges (E ), describing activatory and inhibitory causal interactions, yield 130 possible (signed) directed hyperedges. Hence, considering each hyperedge as either present or absent, one should inspect 2 130 (∼ 1.3 × 10 39 ) possible Boolean logic models. Notice that after compression, all the outgoing edges from one stimulus, namely I F N g , have been removed since they did not lead to any readout node. Also, it is worth noting that another consequence of compression is the presence of both, a positive and a negative edge from T GF a to r as. For a detailed description of the compression method, we refer the interested reader to [START_REF] Saez-Rodriguez | Discrete logic modelling as a means to link protein signalling networks with functional analysis of mammalian signal transduction[END_REF].

Phospho-proteomics dataset. We consider a publicly available phospho-proteomics dataset ξ described in [START_REF] Alexopoulos | Networks inferred from biochemical data reveal profound differences in toll-like receptor and inflammatory signaling between normal and transformed hepatocytes[END_REF]. This dataset contains measurements in HepG2 liver cancer cells characterizing the immediate-early response over the 15 readouts under 64 experimental conditions combining single-stimulus/inhibitor perturbations. That is, ξ = ((C 1 , P C 1 ), . . . , (C 64 , P C 64 )) where the 64 experimental conditions C i result from considering all possible combinations of either 0 or 1 stimulus, combined with either 0 or 1 inhibitor.

Θ mse ((V, φ), ξ) = Θ r ss ((V, φ), ξ) N ξ Θ mse k ((V, φ), ξ) = Θ r ss k ((V, φ), ξ) 10 2k N ξ .
Notably, the range for both functions is the interval [0, 1] where lower values indicate a better fitness to the available data. Notice that Θ mse k can be computed "directly" from the output provided by the ASP solver whereas Θ mse has to be computed in a post-processing step, e.g. by using any standard scripting programming language.

Problem instance. Next, we consider the problem instance given by the PKN (V, E , σ) and the dataset ξ as described above. Also, we adopt the discretization scheme δ k provided by using the closest integer function and k = 2. That is, we approximate phosphorylation activities up to 1 10 2 , e.g. δ 2 (0.586) = 59. In what follows, we denote with the filename extliver.lp, the set of logic facts describing the problem instance as illustrated in Listing 3.1 for our toy example. We can identify all optimal Boolean logic models for our real-world case study as shown in Listing 3.6. The command-line option --opt-mode=optN asks the solver to find an optimum solution and then continue looking for all solutions with the same "costs" for each optimization criterion. In this case, the solver had found 16 Boolean logic models (Optimal: 16) in 0.08 seconds (in total 18 answer sets were inspected (Models: 18)). In fact, for this particular instance there is no significant difference between finding an optimum solution and finding all of them. Let us denote with (V, φ i ) with i = 1, . . . , 16 the corresponding 16 optimal Boolean logic models found. Then, from the solver's output (Optimization : 427905 28), we have that

Θ mse k ((V, φ i ), ξ) = 0.0499, i.e. 427905 × 10 -4 × N -1
ξ , and Θ si ze ((V, φ i )) = 28 for all i = 1, . . . , 16. Interestingly, in this case Θ mse ((V, φ i ), ξ) = 0.0499 as well. That is, either using the original observations (rational numbers) or using the discrete observations (integer numbers), both MSEs agree in this case. 63.5.3 Enumeration of (nearly) optimal Boolean logic models.

Next we evaluate the enumeration of (nearly) optimal Boolean logic models as described before. Let us denote with (V, φ opt ) any of the 16 optimal Boolean logic models (V, φ i ) with i = 1, . . . , 16. Our aim here (and more broadly in this thesis) is not to draw biological conclusions but to illustrate the potential of using the introduced framework based on the computational power of ASP and the available systems. Therefore, for the sake of such an illustration in the following we consider tolerances only with respect to the optimum RSS, i.e., Θ r ss k ((V, φ opt ), ξ) = 427905 whereas no tolerance is allowed with respect to the optimum size, i.e. Θ si ze ((V, φ opt )) = 28. To be more precise, we enumerate all Boolean logic models (V, φ) such that

Θ r ss k ((V, φ), ξ) ≤ Θ r ss k ((V, φ opt ), ξ) + t r ss Θ si ze ((V, φ)) ≤ Θ si ze ((V, φ opt ))
with t r ss equal to 0%, 2%, 4%, 6%, 8% or 10% of the optimum RSS, i.e. Θ r ss k ((V, φ opt ), ξ). Importantly, from the Proposition 3.3.1 we can verify that in this case, considering a tolerance of 10% with respect to the minimum of Θ r ss k is sufficient to guarantee that all models minimizing Θ r ss are found. Moreover, experimental error in phospho-protein measurements is often estimated to 10% [START_REF] Chen | Input-output behavior of ErbB signaling pathways as revealed by a mass action model trained against dynamic data[END_REF], Saez-Rodriguez et al., 2009]. Hence, all Boolean logic models found in such a range of tolerances could not be distinguished experimentally. Results are shown in Table 3.1. We also report the identification of logical input-output behaviors. Note the large difference on computation times for enumeration of Boolean logic models (t enum ), and for identification of logical input-output behaviors (t i n-out ). While the ASP solver can enumerate thousands of models in fractions of a second, identifying their input-output behaviors is still a rather demanding task as we increase the number of models. Notably, considering tolerances with respect to both criteria would imply an even larger number of models. This is not actually an issue for the enumeration but it is certainly an issue for the identification of logical inputoutput behaviors. Interestingly, the range of values for MSEs Θ mse k and Θ mse do not show any significant difference. Hence, together with the theoretical result from Proposition 3.3.1, this suggest that in practice, the information lost due to discretization is negligible. In fact, in this case the models minimizing Θ mse were already identified without considering tolerance. In Figure 3.3 we illustrate the distribution of Boolean logic models found for each tolerance according to their MSEs (Θ mse ). It is worth noting that as we increase the tolerance, more values for Θ mse appear but some are clearly more common than others. For example, when we consider 10% of tolerance, two values for Θ mse , viz. 0.0519 and 0.0542, gather 63% of the 5306 Boolean logic models.

Analyzing logical input-output behaviors.

In order to further characterize the multitude of Boolean logic models found, one can focus on their logical input-output behaviors. As an illustration, we concentrate on the 91 behaviors found when considering 10% of tolerance. In Figure 3.4 we show the 91 input-output behaviors ordered by MSE and the number of Boolean logic models they gather. Interestingly, among the 91 logical input-output behaviors, two behaviors are significantly more common than the rest. Such behaviors result from 20% and 16% of the models respectively whereas all the others result from at most 7%. Hence, one can argue that they are more relevant to describe the system's response. Nevertheless, such a claim requires further biological validation which is out of the scope for this thesis.

Next, in Figure 3.5 we show for each tolerance, the evolution of "core predictions" versus the number of input-output behaviors. By "core predictions" we refer to the percentage of experimental conditions leading to exactly the same response in every logical input-output behavior. Recall that the total number of experimental conditions is given by the experimental setup at hand. In our case, since we have 7 stimuli and 7 inhibitors in the PKN (Figure 3.2), one would consider 2 14 = 16348 possible experiments (all combinatorial perturbations). However, by inspecting the Boolean logic models found, it is easy to see that stimulation of I F N g or LP S, and inhibition of GSK 3, is not informative for the input-output analysis. Hence, with 5 stimuli and 6 inhibitors, the number of "relevant" experimental conditions is given by 2 11 = 2048. For 0% of tolerance there is only one behavior and hence, there is 100% of core predictions. Then, as we increase the tolerance, the number of behaviors increases whereas the core predictions decreases down to 31%. On the one hand, this approach may provide a way to extract robust insights despite the high variability. On the other hand, it also provides a metric to asses the level of uncertainty provided by a given set of logical input-output behaviors.

3.5.5 Comparing with a meta-heuristic approach.

In [START_REF] Guziolowski | Exhaustively characterizing feasible logic models of a signaling network using Answer Set Programming[END_REF] we compared our approach with CellNOpt [START_REF] Terfve | CellNOptR: a flexible toolkit to train protein signaling networks to data using multiple logic formalisms[END_REF], the existing tool to solve the same problem, but using a genetic algorithm. Stochastic search methods such as genetic algorithms, are intrinsically unable not just to provide a complete set of solutions, but also to guarantee that an optimal solution is found. Hence, typically one needs to combine solutions from multiple runs in order to increase the confidence. However, from multiple independent runs of CellNOpt (1000 runs with an average of 1000 seconds per run), only 20% of them have converged to Boolean logic models within the 10% of tolerance over the optimum, i.e. Θ mse ≤ 0.0549. Notably, the 16 optimal models (Θ mse = 0.0499) were found by CellNOpt. Nevertheless, the genetic algorithm has retrieved only 51 out of the 91 logical input-output behaviors with an evident bias towards the most common ones. Hence, those behaviors described only by a few logical networks are very unlikely to be found with such stochastic approaches. Therefore, these results underscore the importance of computational methods allowing for an exhaustive characterization of feasible models.

Conclusion

In this chapter we have addressed the problem consisting of learning from an interaction graph and phosphorylation activities at a pseudo-steady state, (Boolean) logical networks describing the immediate-early response of the system. This problem has been first described in [START_REF] Saez-Rodriguez | Discrete logic modelling as a means to link protein signalling networks with functional analysis of mammalian signal transduction[END_REF] and a genetic algorithm implementation was proposed to solve the underlying optimization problem. To overcome some of the shortcomings intrinsic to stochastic search methods, mathematical programming approaches were presented in [Mitsos et al., 2009, Sharan and[START_REF] Sharan | Reconstructing Boolean models of signaling[END_REF]. However, rather than looking for the optimum Boolean model, one is interested in finding (nearly) optimal models within certain tolerance. Importantly, previous methods, namely stochastic search and mathematical programming, are not able to cope with this question in an exhaustive manner. In this context, we have characterized the learning problem using the notions introduced in Chapter 2. Next, we have elaborated upon our basic ASP representation in order describe the underlying lexicographic multi-objective optimization. Furthermore, we illustrate the strengths of our approach using a real-world problem instance.

Notably, the efficient enumeration techniques provided by an ASP solver like clasp, allow us to explore exhaustively the space of feasible solutions in very short time. Therefore, in contrast with the usual approach of modeling a biological system by means of one Boolean network only, our work opens the way for exploring exhaustively the family of plausible networks explaining the available data equally well. Nevertheless, given the ability to enumerate a large number of Boolean models, the way to select among them arises in order to provide new insights to biologists. Towards this end, we have introduced the notion of logical behaviors which allows us to group logical networks regardless of their "internal wirings" and focus on their input-output predictions. In practice, this facilitates the analysis and interpretation of results whereas it provides a way to extract robust insights despite the high variability. At the same time, the existence of several input-output behaviors and the non-uniform distribution of logical networks among them, pose interesting questions for future work. For instance, in the next chapter we concentrate on the problem consisting of finding a set of experiments allowing to discriminate between every pair of logical input-output behaviors.

More generally, we need to develop a mathematical framework for modeling an ensemble of logical networks and/or their logical behaviors. For instance, all networks could be combined in order to define a single probabilistic Boolean network [START_REF] Shmulevich | Probabilistic Boolean networks: a rule-based uncertainty model for gene regulatory networks[END_REF]. Furthermore, a relatively simple approach would be to define output predictions as a (deterministic) function of predictions from all input-output behaviors considering the distribution of logical networks among them. Interestingly, preliminary results have shown that, such predictions fit the experimental data similarly to each individual input-output behavior. However, it has been shown recently that an ensemble of models often yields more robust predictions than each model in isolation [START_REF] Kuepfer | Ensemble modeling for analysis of cell signaling dynamics[END_REF][START_REF] Marbach | Wisdom of crowds for robust gene network inference[END_REF]. Hence, the presented approach in this chapter is a key contribution in order to achieve reliable and unbiased discoveries in the context of logic-based modeling of signaling networks.

Experimental design for discrimination of input-output behaviors

As we have shown in the previous chapter, if the inherent noise is considered during learning, there are multiple (possibly many) logical networks compatible with the experimental observations. Notably, this leads to several internal mechanisms for the system under study but more importantly, to several input-output behaviors as well. Hence, logical input-output predictions may suffer a significant level of uncertainty. This chapter introduces a method to suggest new experiments for discrimination of input-output behaviors and generate models providing more reliable predictions.

Introduction

Advances on high-throughput technologies have made possible the development of mathematical and computational models describing large-scale biological systems. Importantly, the development of such models allows biologists to test and validate hypotheses, as well as to predict non-observed behaviors. Nonetheless, it is often the case that several "rival" models explain the available experimental data equally well. Especially, in the context of reverse engineering where many (nearly) optimal models may result from an optimization procedure. For instance, as in the previous chapter where thousands of Boolean logic models fit the available dataset similarly well when we consider the experimental noise. Moreover, we have shown that such a large number of models is not only describing alternative mechanisms (internal wirings), but also different input-output behaviors. Therefore, predictions made with such models may suffer a significant level of uncertainty since for a given input, there are several possible system outputs. As mentioned earlier, we can consider several approaches in order to build an ensemble of models such that for a given input, only one output prediction is provided. Nonetheless, learning from experimentation is necessarily an iterative process. Hence, following the loop of hypotesis-driven research in biology [START_REF] Ideker | A new approach to decoding life: systems biology[END_REF][START_REF] Kitano | Systems biology: a brief overview[END_REF], we need to look for the next round of experiments in order to refine the models at hand.

Historically, experiments have been designed based on the experience and intuition from experimentalists. However, since experiments are usually expensive and time-consuming, we would like to know which experiments are more likely to bring new insights to the optimization process. Thus, a proper experimental design enables a maximum informative analysis of the experimental data. Towards this end, exploiting mathematical or computational models for designing the following experiments is a natural approach. We refer the reader to [START_REF] Kreutz | Systems biology: experimental design[END_REF] for a recent review on this subject. Therein, two kinds of "experimental designs" are described, namely, experimental design for parameter estimation and experimental design for model discrimination. In the following, we focus on a particular case of the latter.

Experimental design for discrimination of input-output behaviors. Motivated by our results from the previous chapter, we propose a method for experimental design in order to discriminate between several input-output behaviors. Broadly speaking, experimental design for model discrimination consists of finding an input that maximize the difference of the outputs of the rival models. Importantly, we restrict ourselves to the context of Boolean logic models of immediate-early response as described in Chapter 3. In this context, we aim at finding the minimum number of experimental conditions allowing us to discriminate between every pair of input-output behaviors. Moreover, we adopt a criterion proposed before in the context of mathematical modeling in [START_REF] Mélykúti | Discriminating between rival biochemical network models: three approaches to optimal experiment design[END_REF]. Therein, authors argue that in principle, maximizing the difference between the outputs of two different models would ensure that even a noisy measurement has a good chance of discriminating between them. Therefore, we adapt this idea to the context of our Boolean logic models and logical input-output behaviors. Also, we consider the minimization of the experiments' complexity in terms of the number of stimuli and inhibitions.

Most of the previous work on experimental design have been based on (semi-) quantitative modeling [START_REF] Kremling | A benchmark for methods in reverse engineering and model discrimination: problem formulation and solutions[END_REF][START_REF] Vatcheva | Experiment selection for the discrimination of semi-quantitative models of dynamical systems[END_REF][START_REF] Mélykúti | Discriminating between rival biochemical network models: three approaches to optimal experiment design[END_REF][START_REF] Stegmaier | Robust optimal design of experiments for model discrimination using an interactive software tool[END_REF][START_REF] Busetto | Near-optimal experimental design for model selection in systems biology[END_REF]. Thus, in the context of computational modeling, existing approaches to experimental design are less established. It is worth noting that, in general, computational models provide certain predictive power which can be used to generate testable hypotheses and drive the experiments. Nevertheless, herein we refer to the specific problem consisting of automatically propose new experiments allowing to discriminate models at hand. To date, such a question has been addressed under various modeling hypotheses and methods [START_REF] Ideker | Discovery of regulatory interactions through perturbation: inference and experimental design[END_REF][START_REF] Yeang | Validation and refinement of gene-regulatory pathways on a network of physical interactions[END_REF][START_REF] Barrett | Iterative reconstruction of transcriptional regulatory networks: an algorithmic approach[END_REF][START_REF] Szczurek | Elucidating regulatory mechanisms downstream of a signaling pathway using informative experiments[END_REF][START_REF] Sparkes | Towards robot scientists for autonomous scientific discovery[END_REF]]. Yet, their usefulness in practice remains an open question. Of special interest for us is the approach presented in [START_REF] Sharan | Reconstructing Boolean models of signaling[END_REF]. Therein, authors have addressed slight variations of the problem described in Chapter 3 by means of mathematical programming. In addition, they sketched an algorithm for finding the most informative experiment to discriminate rival Boolean models but no implementation was provided. Nonetheless, compared to all aforecited contributions, our work presents certain differences and similarities. Except for [START_REF] Szczurek | Elucidating regulatory mechanisms downstream of a signaling pathway using informative experiments[END_REF], previous approaches aim at selecting exactly one experiment at each iteration. Therefore, only after the proposed experiment has been carried out in the laboratory and models have been (partially) discriminated, another experiment can be designed. In contrast, but similarly to [START_REF] Szczurek | Elucidating regulatory mechanisms downstream of a signaling pathway using informative experiments[END_REF], we aim at finding the smallest

Problem

number of experiments to optimally discriminate all models at once. Furthermore, motivated by [START_REF] Mélykúti | Discriminating between rival biochemical network models: three approaches to optimal experiment design[END_REF], a distinct feature of our work is the criterion for optimality based on maximizing the sum of pairwise (output) differences. In general, previous methods have adopted an information-theoretic approach where the main design criterion is given by means of the so-called Shannon entropy [START_REF] Shannon | A mathematical theory of communication[END_REF]. Finally, on the theoretical side, results regarding the number and complexity of experiments required for the exact identification of a Boolean genetic network have been reported in [START_REF] Akutsu | Identification of genetic networks by strategic gene disruptions and gene overexpressions under a boolean model[END_REF]].

In the remainder of this chapter we provide a precise characterization of this problem using the notions introduced in Chapter 2 and adapting our Answer Set Programming representation accordingly. Furthermore, we validate our approach using realistic problem settings over the logical input-output behaviors learned in the previous chapter.

Problem

Logical input-output behaviors and search space of experiments

Logical input-output behaviors. In the following, we consider a given prior knowledge network (PKN) (V, E , σ) and an experimental dataset ξ as defined in Chapter 3. Then, we assume we can learn from (V, E , σ) and ξ, a finite family of (nearly) optimal Boolean logic models M = ((V, φ j )) j ∈J . Next, using the Algorithm 1 (Section 3.4.3) we can find the set of logical input-output behaviors B = BEHAVIORS(M ). That is, B contains (exactly) one "representative" Boolean logic model (V, φ j ) ∈ M for each input-output behavior found. Now, let us recall some notation already introduced in previous chapters. We denote with C the space of all possible clamping assignments or experimental conditions C i over (V, E , σ). Notice that in principle, i = 1, . . . , 2 |V S |+|V K | , i.e. all combinatorial perturbations of stimuli and knockouts. Furthermore, we use

F j i to describe the fixpoint of Ω (V,φ j | C i ) reachable from A f = {v � → f | v ∈ V }. Notably, since every (V, φ j ) ∈ B describes a different input-output behavior, it holds that � ∀(V, φ j ), (V, φ j � ) ∈ B, j � = j � :: ∃C i ∈ C , v ∈ V R :: F j i (v) � = F j � i (v) � .
In words, for every pairs of different models (V, φ j ), (V, φ j � ) ∈ B, there exists at least one experimental condition C i and one readout v such that, the corresponding responses in each model differ on v, i.e.

F j i (v) � = F j � i (v).
In practice this means that performing the experiment C i , one would be able to discriminate between (V, φ j ) and (V, φ j � ). Except in the case when the measurement on v is around 0.5 and hence, both Boolean predictions would explain the experimental observation similarly well.

Search space of experiments. As mentioned above, we denote with C the space of all possible clamping assignments or experimental conditions

C i over (V, E , σ). Recall that, if C i is an experimental condition and v ∈ d om(C i ) then, either v ∈ V S and C i (v) = t , or v ∈ V K and a b c d e ∨ ∨ f g 1 ∧ ∧ a b c d e ∨ ∨ f g 2 ∧ ∧ a b c d e ∨ f g 3 ∧ ∧ Figure 4
.1: Representative Boolean logic models (V, φ 1 ), (V, φ 2 ), and (V, φ 3 ) for 3 different logical input-output behaviors. The correspoinding mappings are:

φ 1 = {d � → a ∨ ¬c, e � → b ∨ c, f � → d ∧ e, g � → e∧¬c}, φ 2 = {d � → a∨b, e � → b∨c, f � → d ∧e, g � → e∧¬c}, and φ 3 = {d � → a, e � → b∨c, f � → d ∧e, g � → e∧¬c}.
C i (v) = f . In theory, all combinatorial perturbations of stimuli and knockouts are possible. Thus, one would consider i = 1, . . . , 2

| V S = |d om(C i ) ∩V S | and |C i | V K = |d om(C i ) ∩V K |.
Next, we consider a search space of experimental conditions parameterized by integers s and k in order to restrict ourselves to experiments having at most, s stimuli and k inhibitors, with 0 ≤ s ≤ |V S | and 0 ≤ k ≤ |V K |. To be more precise, the search space of experiments with at most, s stimuli and k inhibitors, is defined as

C (s, k) = � C i | C i ∈ C , |C i | V S ≤ s, |C i | V K ≤ k � .
Notably, the total number of experimental conditions or clamping assignments in C (s, k) is given by

s � i =0 � |V S | i � × k � i =0 � |V K | i � where � n m � denotes the binomial coefficient, i.e., n! m!(n-m)! .
Notice that for some pairs of inputoutput behaviors in B, there may not exist any experimental condition in C (s, k) yielding a different response between them. Especially, if either s or k are too small. Let us illustrate the concepts introduced above with our toy example from Chapter 3. As mentioned in Section 3.4.3, over the 5 (nearly) optimal Boolean logic models enumerated in Listing 3.4, we found 3 logical input-output behaviors. In fact, in Figure 4.1 we show one "representative" Boolean logic model for each behavior. Let us denote these models by (V, φ j ) with j = 1, 2, 3. Then, then corresponding mappings are defined as

φ 1 = {d � → a ∨ ¬c, e � → b ∨ c, f � → d ∧ e, g � → e ∧ ¬c} φ 2 = {d � → a ∨ b, e � → b ∨ c, f � → d ∧ e, g � → e ∧ ¬c} φ 3 = {d � → a, e � → b ∨ c, f � → d ∧ e, g � → e ∧ ¬c} .
Furthermore, let us consider two experimental conditions in C (2, 1), namely C 1 = {b � → t } and 4.2. Problem Table 4.1: Fixpoints F j i for Ω (V,φ j | C i ) reachable from A f with j = 1, 2, 3 and i = 1, 2. Logical networks (V, φ j ) are shown in Figure 4.1 whereas

C 1 = {b � → t } and C 2 = {b � → t , c � → t }. (V, φ j | C 1 ) (V, φ j | C 2 ) a b c d e f g a b c d e f g (V, φ 1 ) f t f t t t t f t t f t f f (V, φ 2 ) f t f t t t t f t t t t t f (V, φ 3 ) f t f f t f t f t t f t f f C 2 = {b � → t , c � → t }. That is, in C 1 only b is stimulated whereas in C 2 both b and c are stimulated.
In both experimental conditions, a is not stimulated and d is not inhibited. The corresponding fixpoints F j i for Ω (V,φ j | C i ) reachable from A f are shown in Table 4.1. We refrain from giving the detailed iterations for the sake of brevity. Nonetheless, one can verify that for each (V, φ j ) and C i , the assignments F j i given in Table 4.1 satisfy that, for all v ∈ d om(φ j ) it holds F j i (φ(v)) = F j i (v). Furthermore, using C 1 and C 2 one can discriminate between every pair of input-output behvaiors, namely, (1, 2), (1, 3) and (2,3). To be more precise, the output responses for (V, φ 1 ) and (V, φ 2 ) differ on species f under C 2 (F 1 2 ( f ) � = F 2 2 ( f )). Between (V, φ 1 ) and (V, φ 3 ), the corresponding fixpoints also differ on species f but under

C 1 (F 1 1 ( f ) � = F 3 1 ( f ))
. Finally, the output responses for (V, φ 2 ) and (V, φ 3 ) differ on f under both clamping assignments,

C 1 (F 2 1 ( f ) � = F 3 1 ( f )) and C 2 (F 2 2 ( f ) � = F 3 2 ( f )).

Experimental design

Discriminating among every pair of behaviors. Let B be a finite set of input-output behaviors represented by Boolean logic models ((V, φ j )) j ∈J . In most cases, it happens that several experimental conditions must be considered together in order to discriminate among every pair of behaviors. Clearly, in practice one would like to perform as few experiments as possible. Therefore, our first criterion for experimental design consists of finding the minimum number of experimental conditions C i ∈ C (s, k) with 0 ≤ s ≤ |V S | and 0 ≤ k ≤ |V K |, which allow us to discriminate among every pair of logical input-output behaviors. To be more precise, we aim at finding the smallest ε ≥ 0 such that there exist an ε-tuple

(C 1 , . . . ,C ε ) ∈ C 1 (s, k)ו • •×C ε (s, k) satisfying: � ∀(V, φ j ), (V, φ j � ) ∈ B, j � = j � :: � ∃C i ∈ {C 1 , . . . ,C ε }, v ∈ V R :: F j i (v) � = F j � i (v) �� . (4.1)
In what follows, we denote with C ε (s, k) the set of all ε-tuples (C 1 , . . . ,C ε ) satisfying (4.1).

Maximizing differences over readouts. Once we have identified that ε experimental conditions are sufficient in order to discriminate between all input-output behaviors, the next question is how to select among all possible (C 1 , . . . ,C ε ) ∈ C ε (s, k). Towards this end, let us denote the Boolean logic models in B by (V, φ 1 ), . . . , (V, φ n ). Then, we define the differences (Θ diff ) generated by the experimental conditions (C 1 , . . . ,C ε ) ∈ C ε (s, k) over the logical input-output behaviors in B as

Θ diff (B, (C 1 , . . . ,C ε )) = n-1 � j =1 n � j � = j +1 ε � i =1 � v∈V R    1 F j i (v) � = F j � i (v) 0 otherwise . (4.2)
Next, our second criterion for experimental design consists of finding ε-tuples

(C 1 , . . . ,C ε ) ∈ C ε (s, k) such that the function Θ diff is maximized, (C 1 , . . . ,C ε ) ∈ arg max (C 1 ,...,C ε )∈C ε (s,k) � Θ diff (B, (C 1 , . . . ,C ε )) � . (4.3)
Minimizing the complexity of experiments. Intuitively, the complexity or "cost" of an experimental condition C i over (V, E , σ) can be related to the number of stimuli

(|C i | V S ) and inhibitors (|C i | V K ), clamped in C i .
In fact, this intuition has been used before in [START_REF] Akutsu | Identification of genetic networks by strategic gene disruptions and gene overexpressions under a boolean model[END_REF] where it has been investigated the number and complexity of experiments required for the identification of a Boolean gene regulatory network. Moreover, we have already taken this notion of complexity into account when we restricted ourselves to experimental conditions in

C (s, k) = � C i | C i ∈ C , |C i | V S ≤ s, |C i | V K ≤ k � .
However, the selection of s and k aims at giving upper bounds to the number of stimuli and inhibitors. Now, we aim at finding the simplest experimental conditions among all ε-tuples (C 1 , . . . ,C ε ) maximizing Θ diff as in (4.3). Towards this end, we define two functions over ε-tuples of experimental conditions counting the number of stimuli (Θ V S ) and inhibitors (Θ V K ) respectively,

Θ V S ((C 1 , . . . ,C ε )) = ε � i =1 |C i | V S Θ V K ((C 1 , . . . ,C ε )) = ε � i =1 |C i | V K . (4.4)
Next, let us denote with Δ the set of all ε-tuples (C 1 , . . . ,C ε ) maximizing Θ diff as in (4.2). Finally, we consider two additional optimization criteria in lexicographic order aiming at the identification of the simplest (C 1 , . . . ,C ε ) ∈ Δ,

(C 1 , . . . ,C ε ) ∈ arg min (C 1 ,...,C ε )∈Δ � Θ V S ((C 1 , . . . ,C ε )) , Θ V K ((C 1 , . . . ,C ε )) � . (4.5)
Notice that we minimize first Θ V S and then, with lower priority Θ V K . But this is a rather arbitrary decision which can be revisited in practice. For instance, if for the system at hand, it is the case that combining several inhibitors is experimentally more complicated than combining several ligands. Alternatively, both functions could be combined into a single function, for example,

Θ V S ∪V K = Θ V S + Θ V K .
In fact, many other criteria could be taken into account. For example, we could assign a weight to every stimulus and inhibitor in order to describe its price. Thereafter, we can minimize the required budget for running the suggested experiments. Also, if certain stimuli and/or inhibitors are not compatible with each other, we could consider additional constraints in order to avoid such combinations. Nevertheless, these kinds of optimization criteria and constraints are related to very specific application settings such as, available technology, experimental tools (ligands, small-molecule drugs, antibodies, etc), budget, and clause (0 , " b " ,1) . clause (2 , " c " ,1) . clause (7 , " c " , -1) . clause (8 , " a " ,1) . clause (14 , " e " ,1) . clause (14 , " c " , -1) . clause (16 , " d " ,1) . clause (16 , " e " ,1) .

stimulus ( " a " ) . stimulus ( " c " ) . stimulus ( " b " ) . readout ( " g " ) . readout ( " f " ) . inhibitor ( " d " ) .

# const maxstimuli = 3. # const maxinhibitors = 1.

Encoding

Next we describe our encoding relying on incremental ASP [START_REF] Gebser | Engineering an incremental ASP solver[END_REF], for finding an optimal experimental design as described in the previous section. The idea is to consider one problem instance after another by gradually increasing the number of experimental conditions such that, if the program is satisfiable at the step ε, then there exists an ε-tuple (C 1 , . . . ,C ε ) satisfying (4.1). Our ASP encoding is shown in Listing 4.2.

Listing 4.2: Logic program for finding an optimal experimenal design (design.lp)

# include < iclingo >. # const imax = 20.
model ( M ) : -formula (M ,_ , _ ) .

# program cumulative ( k ) .

{ clamped (k ,V , 1) : clause (_ ,V , _ ) , stimulus ( V ) } maxstimuli . { clamped (k ,V , -1) : clause (_ ,V , _ ) , inhibitor ( V ) } maxinhibitors .

clamped (k ,V , -1) : -stimulus ( V ) ; not clamped (k ,V ,1) .

clamped (k , V ) : -clamped (k ,V , _ ) . free (k ,M ,V , I ) : -formula (M ,V , I ) ; not clamped (k , V ) .

eval (k ,M ,V , S ) : -clamped (k ,V , S ) ; model ( M ) . eval (k ,M ,V , 1) : -free (k ,M ,V , I ) ; eval (k ,M ,W , T ) : clause (J ,W , T ) ; dnf (I , J ) . eval (k ,M ,V , -1) : -not eval (k ,M ,V ,1) ; model ( M ) ; variable (V ) .

diff (k , M1 , M2 ) : -diff (k , M1 , M2 , _ ) . diff (k , M1 , M2 , V ) : -eval (k , M1 ,V , S ) ; eval (k , M2 ,V , -S ) ; M1 < M2 ; readout ( V ) ; model ( M1 ; M2 ) . # minimize {1 @1 , clamped ,k , V : clamped (k ,V , -1) , inhibitor ( V ) }. # minimize {1 @2 , clamped ,k , V : clamped (k ,V , 1) , stimulu s ( V) }. # maximize {1 @3 , diff ,k , M1 , M2 , V : diff (k , M1 , M2 , V ) }.

# program volatile ( k ) . # external query ( k ) .

: -not diff (K , M1 , M2 ) : K =1.. k ; model ( M1 ; M2 ) ; M1 < M2 ; query (k ) . 33 # show diff /4.

Preliminaries Line 1 declares the required inclusion in order to use incremental solving embedded in clingo 4. Importantly, the remainder of the encoding must follow a specific structure in order to work properly. More precisely, we need to define two "subprograms", namely, cumulative(k), and volatile(k). To this end, we use the directive #program with a name, e.g., cumulative, and an optional list of parameters, e.g., (k). Each subprogram comprise all rules up to the next such directive (or the end of file) and their grounding is controlled via the embedded script. Line 2 declares the constant imax which is used as the maximum number of incremental steps to be considered. Recall that, the number of incremental steps represents the number of experimental conditions. Thus, by default, we assign it to 20 but we can easily overwrite this value afterwards using the command-line option -c imax=e. Next, Line 4 defines auxiliary domain predicates model/1, namely, model( j ) for all Boolean logic model (V, φ j ) ∈ B.

Experimental conditions, fixpoints, differences, and optimization. Lines 6-25 define the subprogram cumulative(k). The purpose of this subprogram, is to declare all logic rules which have to be grounded at every incremental step k. As in Listing 3.2, we represent experimental conditions using predicates clamped/3. Thus, Lines 8-10 define rules in order to guess the experimental condition at step k. Note the usage of constants maxstimuli and maxinhibitors as upper bounds in the corresponding choice rules. Also, we restrict the choices to experimental conditions clamping a variable v ∈ V S ∪ V K only if v occurs in some clause. Otherwise, clamping the variable v does not make any "downstream" difference and hence, it is not useful in order to discriminate models. For instance, following our toy example, the experimental conditions C 1 = {b � → t } and C 2 = {b � → t , c � → t } are represented by predicates clamped(1,b,1), clamped(2,b,1), and clamped(2,c,1).1 Lines 12-17 elaborate on the rules Π 2.3 , Π 2.4 and Π 2.5 given in Chapter 2 in order to consider several clamping assignments and logical networks simultaneously, and compute the fixpoint for each of them accordingly. To be more precise, the response for each logical network under each experimental condition is represented over predicates eval/4, namely, eval(i ,j ,v,s) for a logical network (V, φ j ) and experimental condition C i , if the variable v is assigned to s, i.e. F j i (v) = s. Let us illustrate this with our example. The corresponding predicates eval/4 describing the response over variables f and g as in Table 4.1 are: eval(1,1,"f", 1) eval(1,1,"g",1) eval(2,1,"f",-1) eval(2,1,"g",-1) eval(1,2,"f", 1) eval(1,2,"g",1) eval(2,2,"f", 1) eval(2,2,"g",-1) eval(1,3,"f",-1) eval(1,3,"g",1) eval(2,3,"f",-1) eval(2,3,"g",-1)

Then, in Lines 19-21 we derive predicates diff/3 and diff/4 in order to represent differences among every pair of logical input-output behavior for the experimental conditions under consideration. That is, we derive diff(i ,j ,j � ,v) provided that for some models (V, φ j ), (V, φ j � ) with j < j � , we have that

F j i (v) � = F j � i (v), i.e.
, eval(i ,j ,v,s) and eval(i ,j � ,v,-s). For our example, we derive predicates diff(1,1,3,"f"), diff(1,2,3,"f"), diff(2,1,2,"f"), and diff(2,2,3,"f"). Hence, predicates diff/3, namely, diff(i ,j ,j � ) indicate the existence of at least one (output) difference between (V, φ j ) and (V, φ j � ) under experimental condition C i . Finally, Lines 23-25 declare the three optimization criteria in lexicographic order. Notably, when grounding and solving cumulative(k) for successive values of k, the solver's objective functions are gradually extended accordingly. Lines 23-24 declare the minimization of functions Θ V S and Θ V K , as defined in (4.4). Notice the corresponding priority levels, namely @1 and @2, meaning that as defined in (4.5), first we minimize Θ V S , and then with lower priority Θ V K . As discussed earlier, this is a rather arbitrary decision. However, in practice it can be revisited very easily thanks to the declarativeness of ASP. Finally, Line 25 declares with the greatest priority, namely, @3, the maximization of the function Θ diff as defined in (4.2).

Discriminating among every pair of input-output behaviors. Lines 27-33 define the subprogram volatile(k). The purpose of this subprogram, is to declare logic rules specific for each value of k. Typically, in the form of integrity constraints forcing the incremental solving to continue until such constraints are satisfied at a given step. Line 28 declares the external atoms query(k) for every incremental step k. Internally, the incremental solving embedded in clingo 4 assigns these atoms to either true or false in order to indicate the current step. Then, in Line 30 we define an integrity constraint in order to eliminate answer sets describing an ε-tuple (C 1 , . . . ,C ε ) such that (4.1) does not hold. In fact, the body of the integrity constraint is precisely the negation of the expression given in (4.1). Therefore, the incremental solving continues until its reach either the maximum number of steps imax, or the step ε such that there exists an ε-tuple satisfying (4.1).

The following result shows the correctness of our ASP representation. We denote with τ(B, s, k) the set of facts describing the instance as in Listing 4.1, and with Π 4.2 the set of rules given in Listing 4.2.

X of τ(B, s, k)∪Π 4.2 such that C i = {v � → t | v ∈ V S , clamped(i , v, 1) ∈ X } ∪ {v � → f | v ∈ V K , clamped(i , v, -1) ∈ X } with i = 1, . . . ,
) ∈ arg min (C 1 ,...,C ε )∈Δ � Θ V S ((C 1 , . . . ,C ε )) , Θ V K ((C 1 , . . . ,C ε )) � with Δ = arg max (C 1 ,...,C ε )∈C ε (s,k) � Θ diff (B, (C 1 , . . . ,C ε )) � and C ε (s, k) the set of all ε-tuples (C 1 , . . . ,C ε ) ∈ C 1 (s, k) × • • • × C ε (s, k) satisfying (4.1).

Solving

In Listing 4.3 we show the optimum answer set for the toy instance described in Listing 4.1. Such an answer set represents the experimental conditions

C 1 = {b � → t } and C 2 = {b � → t , c � → t }.
Notice that, we can see the number of steps in the incremental solving by looking at the number of calls (Calls: 2 or Solving... printed twice). Furthermore, the value for each optimization criterion is given in the corresponding order (Optimization 8 3 0). Actually, the grounder performs an internal transformation for maximize statements and hence, the reported value (8) for the first optimization criterion is not exactly as one would expect. In order to recover the optimum for Θ diff , we need to count the number of predicates diff/4 in the answer set. Thus, in this case, the optimum value for Θ diff is 4. On the other hand, minimization statements are treated without any transformation. Therefore, the optimum value for Θ V S is 3, whereas the optimum value for Θ V K is 0, as reported directly by the solver. (2 ,2 ,3 , " Logical input-output behaviors. In Chapter 3, using real-world signaling pathways in human liver cells and a publicly available phospho-proteomics dataset, we have shown how we can learn Boolean logic models and their corresponding logical input-output behaviors. In particular, in Table 3.1 we have reported, for various levels of tolerance over fitness, the number of Boolean logic models and the number of input-output behaviors they describe. Recall that, in regards of the available experimental observations and their intrinsic uncertainty, such behaviors explain the data equally well. Therefore, now we are interested in identifying an optimal experimental design, as described in Section 4.2, in order to discriminate among all input-output behaviors found for each tolerance, namely, 4 behaviors for 2% tolerance, 31 behaviors for 4% tolerance, 38 behaviors for 6% tolerance, 66 behaviors for 8% tolerance, and 91 behaviors for 10% tolerance.

clamped (1 , " a " , -1) clamped (1 , " c " , -1) clamped (1 , " b " ,1) \ clamped (2 , " a " , -1) clamped (2 , " c " ,1) clamped (2 , " b " ,1) \ diff (1 ,1 ,3 , " f " ) diff (1 ,2 ,3 , " f " ) diff (2 ,1 ,2 , " f " ) diff
Search space of experiments. The phospho-proteomics dataset used for learning contains 64 experimental conditions resulting from all possible combinations of either 0 or 1 stimulus, combined with either 0 or 1 inhibitor. Now, we consider the space of experimental conditions defined by C (3,2). That is, experiments having 0 to 3 stimuli, combined with 0 to 2 inhibitors. As explained earlier, on the one hand, this restriction reduces the size of the search space which is always convenient from the computational point of view. But also, on the other hand, considering experiments with more stimuli and/or inhibitors, does not appear to be very relevant in practice since it would not be possible to perform such experiments.

Problem instances. Next, we consider the problem instances given by each set of logical input-output behaviors listed in

Optimal experimental designs

In Listing 4.4 we show the solving for the problem instance behaviors-31.lp. In this case, we find that at least five experimental conditions are required in order to discriminate between every pair of behaviors. Furthermore, for this problem we exploit the multi-threading capacities of clingo [Gebser et al., 2012b] using 8 threads: --conf=many -t 8. It is worth noting that, each thread uses a different set of pre-configured parameters which allow to traverse the search space with different heuristics. Actually, for small problem instances, there is no significant difference in performance if we compare single-and multi-threading solving. Nonetheless, for larger problem instances, for example behaviors-66.lp and behaviors-91.lp, the proof of optimality for a candidate answer set is a very demanding task. Hence, using multi-threading is very convenient for such cases. Note that, when we use multiple threads, the solver reports the overall CPU time (931.380s) for all threads and the real time (119.240s) for solving. Notably, in practice and from the user point of view, the real time is more relevant. As already mentioned for the toy example, from the solver's output we can directly read the corresponding values for Θ V S and Θ V K , in this case, 12 and 7 respectively. However, the value for Θ diff has to be computed counting predicates diff/4 in the optimum answer set. We refrain to show the complete answer set in Listing 4.4 for the sake of brevity. In this case, the optimum value for Θ diff is 4412. That is, the designed experiments generate 4412 pairwise output differences over the 31 input-output behaviors.

In Table 4.2 we report results for all problem instances. As expected, as we consider larger sets of input-output behaviors, more experiments (ε) are required in order to discriminate all pairs. Interestingly, the computation time (t ε ) required to find such a minimum number of experiments is relatively small for all problem instances. Notice that, at that time the solver has found an answer set describing a candidate experimental design. Nevertheless, the computation time required to find an optimal experimental design increases several orders of magnitude for the largest instance. Approximately 18 hours of real time and 144 hours of CPU time summing all threads. Notably, for such an instance, the solver considers all possible sets of 7 experimental conditions among the search space C (3, 2), i.e., ∼ 3.8 × 10 15 . Thus, in practice, for even larger problem instances one should use a "reasonable" timeout and take the last answer set found as an approximation to the optimum. We also report the overall number of pairwise differences (Θ diff ), its mean (µ diff ) and standard deviation (σ diff ). For example, the optimal experimental design to discriminate between 38 behaviors, requires 5 experimental conditions which yield 5957 pairwise differences. Furthermore, the mean number of pairwise differences is 8.5 and the standard deviation is 4.9. It is worth noting that, in general, the standard deviation is relatively large. This indicates that certain pairs of behaviors would be "better" discriminated than others. In principle, if one aims at having a more uniform pairwise discrimination, an entropy-based design criterion would be more appropriate. However, such an approach requires numerical computations which are out of scope of our methods but also, they may compromise exhaustiveness and scalability. (3,2). We report for each set of input-output behaviors B m from Table 3.1, the minimum number of experimental conditions required to discriminate between every pair of behaviors (ε), the time for finding such a minimum (t ε ), the maximum number of pairwise differences (Θ diff ), the mean and standard deviation pairwise differences (µ diff and σ diff ), the minimum number of stimuli (Θ V S ), the minimum number of inhibitors (Θ V K ), and the time for finding an optimum experimental condition (t opt ). Also, in parentheses, we report overall CPU time for the 8 threads.

B m ε t ε Θ diff µ diff σ diff Θ V S Θ V K t

Analyzing experimental designs

Next, we provide a further analysis of the optimal experimental design found to discriminate between the 91 input-output behaviors. Analogously, the same analysis can be done considering the experimental design found for each set of behaviors. In Figure 4.2 we show the optimal experimental design (Figure 4.2a) and several views of the pairwise differences generated by each experimental condition (Figures 4.2b,4.2c,and 4.2d). Interestingly, all experimental conditions allow to discriminate between a large number of pairs of input-output behaviors (Figure 4.2b). Notice that, the total number of pairs among 91 behaviors is given by the binomial coefficient, � 91 2 � = 4095. Thus, each experimental condition in the optimal design discriminates between at least, 50% of the behaviors pairs. Next, we look at which specific readouts we generate differences (Figure 4.2c). On the one hand, for 2 readouts, viz., H SP 27 and p53, we generate pairwise differences with all experiments. On the other hand, for all other readouts, we generate pairwise differences with at most 5 out of the 7 experiments. Moreover, for 4 readouts, viz., AK T , p90RSK , M E K 12, and GSK 3, we generate pairwise differences with only 1 experimental condition. More precisely, only experiment #3 generates differences over AK T and GSK 3, and only experiment #1 generates differences for p90RSK and M E K 12. We note that, such correlations between readouts is explained by the fact that in all logic models (V, φ j ), AK T is the only regulator of GSK 3, i.e., φ j (GSK 3) = AK T , whereas M E K 12 is the only regulator of p90RSK , i.e., φ j (p90RSK ) = M E K 12. Finally, we look at the overall pairwise differences generated with each experimental condition (Figure 4.2d). Percentages are computed over the 47232 pairwise differences generated with all experiments.

Conclusion

In this chapter we have addressed the problem consisting of finding an optimal set of experiments in order to discriminate between several logical input-output behaviors. Various authors have considered the problem of model discrimination in the context of computational modeling [START_REF] Ideker | Discovery of regulatory interactions through perturbation: inference and experimental design[END_REF][START_REF] Yeang | Validation and refinement of gene-regulatory pathways on a network of physical interactions[END_REF][START_REF] Barrett | Iterative reconstruction of transcriptional regulatory networks: an algorithmic approach[END_REF][START_REF] Szczurek | Elucidating regulatory mechanisms downstream of a signaling pathway using informative experiments[END_REF][START_REF] Sparkes | Towards robot scientists for autonomous scientific discovery[END_REF][START_REF] Sharan | Reconstructing Boolean models of signaling[END_REF]. Nevertheless, their usefulness in practice remains an open question. In contrast to the relatively popular entropy-based approach, and motivated by [START_REF] Mélykúti | Discriminating between rival biochemical network models: three approaches to optimal experiment design[END_REF], our main design criterion aims at maximizing the number of pairwise (output) differences between rival logical behaviors. Thus, in principle, our work is complementary to previous approaches to experimental design in the context of logical models [Ideker et al., 2000, Sharan and[START_REF] Sharan | Reconstructing Boolean models of signaling[END_REF]. Therein, the aim is to suggest the most informative experiment to discriminate among a set of previously inferred Boolean networks. Instead, we aim at finding the least set of experiments allowing to discriminate every pair of logical behaviors. Notably, both approaches share the vision of an iterative process combining modeling and experimentation for learning accurate logical models. solver. This emphasizes the flexibility of ASP as a powerful and general-purpose framework for problem solving. Furthermore, we illustrated the usage of our approach with the sets of input-output behaviors learned in Chapter 3 and suggested optimal experiments towards more accurate logical models of immediate-early response.

Several questions can be investigated in the future. Firstly, we need to develop proper artificial benchmarks in order to evaluate optimal experimental designs. In fact, the generation of biologically meaningful networks and datasets, is a key step towards realistic performance assessment of reverse engineering methods [START_REF] Marbach | Generating realistic in silico gene networks for performance assessment of reverse engineering methods[END_REF]. Secondly, additional knowledge could be considered. For instance, the number of Boolean logic models for each input-output behavior was not taken into account. Also, information about preferences or incompatibilities among stimuli and/or inhibitors could help to prune the search space. Thirdly, in an iterative process of learning and experimentation, it is not clear which strategy may yield more predictive models after a few iterations. On the one hand, we could adopt a "cautious" strategy where we start by identifying a few input-output behaviors for a small tolerance, e.g. 2%, and in the following iterations, we increase the tolerance as we also increase the confidence in learned behaviors. On the other hand, with a "brave" strategy, at every iteration, we should aim at identifying input-output behaviors for a large tolerance, e.g. 10%, and look for experiments to discriminate among possibly many behaviors. Moreover, yet another factor to consider is to take into account certain tolerance over model size during learning which often leads to more input-output behaviors. Altogether, the work presented in this chapter contributes to the loop of hypothesis-driven research in biology [START_REF] Ideker | A new approach to decoding life: systems biology[END_REF][START_REF] Kitano | Systems biology: a brief overview[END_REF] in the context of logic-based modeling.

Minimal intervention strategies

In previous chapters we have shown how can we iteratively learn and refine an ensemble of logical networks describing the cellular response. Next, a major challenge is how to control it by means of therapeutic interventions. Importantly, progress in this area may have a crucial impact on bio-medical research, drug target identification and diagnosis. This chapter addresses the problem consisting of finding minimal intervention strategies in logical signaling networks. That is, inclusion-minimal sets of activations and inhibitions forcing a set of target species into a desired steady state under various scenarios.

Introduction

As mentioned in the seminal paper for systems biology [START_REF] Kitano | Systems biology: a brief overview[END_REF], a major challenge in this field is how to systematically control the state of the cell. From an application viewpoint, this means selecting appropriate drugs in order to force the system to reach a state with properties that were specified a priori. In previous chapters we have shown how can we iteratively learn and refine an ensemble of logical networks describing the cellular response. In principle, iterating over such a loop of modeling and experimentation will yield more accurate logical models. Yet, there may be several networks which cannot be discriminated using the available experimental capacities. In which case, instead of selecting a single logical network, in this chapter we aim at reasoning over all of them.

Based on earlier work [START_REF] Klamt | Generalized concept of minimal cut sets in biochemical networks[END_REF] on metabolic networks, the notion of minimal intervention sets for signaling networks was introduced in [START_REF] Samaga | Computing combinatorial intervention strategies and failure modes in signaling networks[END_REF] and dedicated algorithms were developed to compute them. Intuitively, an "intervention set" represents a set of knockins and knock-outs.1 Examples for knock-ins are mutations leading to constitutively activated species or a continuous stimulation with external signals, whereas knock-outs may correspond to gene knock-outs or inhibition of certain species by various experimental tools such as smallmolecule drugs, antibodies, or RNAi. Then, authors in [START_REF] Samaga | Computing combinatorial intervention strategies and failure modes in signaling networks[END_REF], were particularly interested in enumerating all minimal intervention sets leading to a specific steady state in a given logical signaling network. Notably, advances on this subject may have a crucial impact on bio-medical research, drug target identification and diagnosis. For instance, one could ask for possible therapeutic interventions which would induce apoptosis (cell death) in cancer cells [START_REF] Layek | Cancer therapy design based on pathway logic[END_REF]. Furthermore, for some human diseases, including cancer, a single gene does not cause the disorder but instead, the disease may result from the abnormal behavior of several molecules in different pathways [START_REF] Abdi | Fault diagnosis engineering of digital circuits can identify vulnerable molecules in complex cellular pathways[END_REF]. Thus, the method presented in this chapter can also be used as a diagnostic tool to identify causes (mutations) leading to observed cellular responses.

Finding robust minimal intervention strategies. Unfortunately, dedicated algorithms introduced in [START_REF] Samaga | Computing combinatorial intervention strategies and failure modes in signaling networks[END_REF] are computationally demanding due to the highly combinatorial mechanisms in logical networks. Therefore, they are limited to compute small intervention sets and fail to scale over large-scale networks. Importantly, in general, multiple interventions (or mutations) are necessary to cope with robustness and cellular complexity [START_REF] Stelling | Robustness of cellular functions[END_REF]. Moreover, as we have shown in Chapter 3, if the inherent experimental noise is considered there are many logical networks compatible with a given dataset of experimental observations. Thus, identified interventions should fulfill the desired goals in every feasible logical network. Concretely, the aforementioned limitations make it hard to prove that the identified solutions are biologically robust to small variations of the system or its environment. Therefore, by reasoning over several sets of feasible logical networks we expect to find small yet robust intervention strategies.

More broadly, the problem of identifying "key-players" in logical signaling networks has been recently addressed in [START_REF] Li | Predicting essential components of signal transduction networks: A dynamic model of guard cell abscisic acid signaling[END_REF][START_REF] Abdi | Fault diagnosis engineering of digital circuits can identify vulnerable molecules in complex cellular pathways[END_REF], Wang and Albert, 2011[START_REF] Layek | Cancer therapy design based on pathway logic[END_REF]. In contrast to our work, these contributions have rather focused on predicting what would happen if certain molecules fail. To that end, authors in [START_REF] Li | Predicting essential components of signal transduction networks: A dynamic model of guard cell abscisic acid signaling[END_REF][START_REF] Abdi | Fault diagnosis engineering of digital circuits can identify vulnerable molecules in complex cellular pathways[END_REF][START_REF] Layek | Cancer therapy design based on pathway logic[END_REF] rely on digital circuits fault diagnosis engineering to identify the vulnerable molecules that play crucial roles in the dysfunction of signaling networks. In that context, a high vulnerability suggests that with high probability, the signaling network does not operate correctly if that particular molecule is dysfunctional ("stuck-at-0" or "stuck-at-1" in digital circuits terminology). It is worth noting that, due to computational limitations, in general authors have restricted their studies to small number of simultaneous faults. The approach presented in [START_REF] Wang | Elementary signaling modes predict the essentiality of signal transduction network components[END_REF] does not relies on digital circuits but rather on standard graph theory. Therein, authors proposed two connectivity measures based either on the shortest paths, or on the so-called "elementary signaling modes". Then, using such measures their method provides a ranking of the nodes by the effects of their loss on the connectivity between the network's inputs and outputs. Importantly, despite the specific problem settings and computational approaches in these contributions, all of them have considered a single logical network describing the system.

In the remaining of this chapter, first we revisit the problem defined in [START_REF] Samaga | Computing combinatorial intervention strategies and failure modes in signaling networks[END_REF]

5.2. Problem a b c d e ∨ ∨ f g 1 ∧ ∧ a b c d e ∨ ∨ f g 2 ∧ ∧ ∧ a b c d e ∨ f g 3 ∧ ∧ a b c d e ∨ ∨ f g 4 ∧ ∧ a b c d e ∨ ∨ ∨ f g 5 ∧ ∧
Figure 5.1: Alternative logical networks (V, φ 1 ), (V, φ 2 ), (V, φ 3 ), (V, φ 4 ), and (V, φ 5 ) describing a given system equally well. The correspoinding mappings are:

φ 1 = {d � → a ∨ ¬c, e � → b ∨ c, f � → d ∧ e, g � → e ∧ ¬c}, φ 2 = {d � → a ∨(b ∧¬c), e � → b ∨c, f � → d ∧e, g � → e ∧¬c}, φ 3 = {d � → a, e � → b ∨c, f � → d ∧e, g � → e ∧¬c}, φ 4 = {d � → a∨b, e � → b∨c, f � → d ∧e, g � → e∧¬c}, and φ 5 = {d � → a∨b∨¬c, e � → b∨c, f � → d ∧e, g � → e∧¬c}.
using the notions introduced in Chapter 2. Then, we adapt our Answer Set Programming (ASP) representation accordingly. Of special interest is here ASP's expressive power to address problems of elevated complexity, in particular, for computing all inclusion-minimal solutions. Finally, we illustrate our approach using the families of (nearly) optimal logic models learned in Chapter 3.

Problem

Intervention scenarios and strategies

Intervention sets, side constraints and goals. Given a logical signaling network, the aim of an intervention strategy is to identify a set of therapeutic interventions that leads to a steady state satisfying a given goal under some side constraints. In fact, the concepts of an intervention (I ), goal (G), and side constraints (C ) can be captured as partial two-valued assignments. Moreover, both intervention sets and side constraints are considered clamping assignments as defined in Section 2. To be more precise, given a logical network (V, φ), an intervention scenario is a pair (G,C ) of partial two-value assignments over V where C is considered also as a clamping assignment, and an intervention set is a clamping assignment I over a set of intervention variables X ⊆ V .

Intervention strategies. Let (V, φ) be a logical network, let (G,C ) be an intervention scenario, and X ⊆ V be a set of intervention variables. An intervention set I over X is an intervention strategy for (G,C ) with respect to (V, φ), if for some j ≥ 0, we have that

Ω j (V,φ| C •I ) (A u ) = Ω j +1 (V,φ| C •I ) (A u ) G ⊆ Ω j (V,φ| C •I ) (A u ) with A u = {v � → u | v ∈ V }. In words, Ω j (V,φ| C •I ) (A u
) is a steady state of the clamped network (V, φ| C •I ) satisfying the goal conditions in G. Notice the composition of C • I indicating that clampings in the intervention set I overwrite clampings in the side constraints C . Recall that for two-valued truth assignments A, B we defined the composition of assignments

A • B = (A \ B ) ∪ B where B = {v � → s | v � → s ∈ B } and t = f , f = t .
Finally, the intervention set problem consists in deciding whether there is an intervention strategy for an intervention scenario (G,C ) with respect to a logical network (V, φ).

For illustration, let us consider the toy logical network (V, φ 1 ) in Figure 5.1 along with the intervention scenario (G,C ) = ({d � → f , g � → f }, {e � → t }). In this example, the intervention scenario requires the inhibition of d and g , given that e is stimulated. Next, the intervention set I = {a � → f , c � → t } where a is inhibited and c is stimulated, satisfies the scenario yielding the steady state {a

� → f , b � → u, c � → t , d � → f , e � → t , f � → f , g � → f }.
Therefore, I is an intervention strategy for (G,C ) with respect to (V, φ 1 ). In fact, I is also an intervention strategy for (G,C ) with respect to (V, φ 2 ) and (V, φ 3 ) in Figure 5.1 as well. But now, if we consider the toy logical network (V, φ 4 ) in Figure 5.1 along with the same intervention scenario. The previous intervention set I yields the steady state {a

� → f , b � → u, c � → t , d � → u, e � → t , f � → f , g � → f }. Notably, since φ 4 (d ) = a ∨ b,
and b is neither constrained nor intervened, d remains undefined in this case (see Table 2.2). Similarly, the same happens with respect to (V, φ 5 ). Therefore, while the intervention set I = {a � → f , c � → t } is an intervention strategy for (V, φ 1 ), (V, φ 2 ), and (V, φ 3 ), when we consider either (V, φ 4 ) or (V, φ 5 ), the inhibition of d in our intervention goal is not fulfilled. In this toy example, it is relatively easy to see that the intervention set

I � = {a � → f , b � → f , c � → t }
is an intervention strategy for (G,C ) with respect to all logical networks (V, φ i ) with i = 1, . . . , 5. Clearly, the same analysis for several intervention scenarios with respect to thousands of large-scale logical networks is out of reach to do it by hand.

Enumeration of minimal (bounded) intervention strategies

Authors in [START_REF] Samaga | Computing combinatorial intervention strategies and failure modes in signaling networks[END_REF], were particularly interested in enumerating all minimal (bounded) intervention strategies with respect to a single logical network. However, as we illustrate in this thesis, and other authors have shown by considering real-world networks and data [START_REF] Saez-Rodriguez | Discrete logic modelling as a means to link protein signalling networks with functional analysis of mammalian signal transduction[END_REF][START_REF] Chen | Input-output behavior of ErbB signaling pathways as revealed by a mass action model trained against dynamic data[END_REF], it often happens that the model is non-identifiable. Therefore, as several logical networks can describe a given biological system equally or similarly well, identified intervention strategies should fulfill all intervention scenarios in every possible logical network. Importantly, as we have shown with the toy example above, intervention strategies with respect to a logical network are very likely to fail in another network which may describe the system similarly well. Notably, this may have a strong impact on the robustness of identified solutions. In order to overcome this issue, we extend the problem settings in order to consider an ensemble of logical networks, e.g. resulting from the enumeration of (nearly) optimal Boolean logic models described in Chapter 3. This way, we are able to reason over all possible networks without any a priori bias and towards more robust insights. Now, let us define further intervention strategies relying on a finite family (V, φ i ) i ∈N of logical networks, a finite family (G j ,C j ) j ∈J of intervention scenarios and k some positive integer.

• A multi-scenario intervention strategy for (G j ,C j ) j ∈J wrt (V, φ i ) i ∈N is an intervention strategy for each (G j ,C j ) wrt (V, φ i ) for each j ∈ J and i ∈ N .

• A bounded intervention strategy for (G j ,C j ) j ∈J wrt (V,

φ i ) i ∈N and k is a multi-scenario intervention strategy for (G j ,C j ) j ∈J wrt (V, φ i ) i ∈N of cardinality k � ≤ k. • A minimal bounded intervention strategy for (G j ,C j ) j ∈J wrt (V, φ i ) i ∈N and k is a ⊆- minimal multi-scenario intervention strategy for (G j ,C j ) j ∈J wrt (V, φ i ) i ∈N of cardinality k � ≤ k.
In what follows, we focus on the enumeration of all minimal (bounded) intervention strategies for given families of intervention scenarios (G j ,C j ) j ∈J and logical networks (V, φ i ) i ∈N .

Minimal intervention strategies with Answer Set Programming

Instance

Once again, the representation of the problem instance is an extension from the one described in Listing 2.1 in order to describe a finite family of logical networks and clamping assignments.

To be more precise, instead of having facts over predicates formula/2, we consider facts over predicates formula/3 as in Chapter 4. Let (V, φ i ) i ∈N be a finite family of logical networks.

The facts formula(i ,v,s φ i (v) ) map variables v ∈ V to their corresponding formulas φ i (v) for each i ∈ N . Meanwhile, facts over predicates variable/1, dnf/2 and clause/3 remain the same as in Listing 2.1. We use facts over predicate candidate/1 to denote the intervention variables that can be part of an intervention set. This allows us to control on which variables interventions are permitted, for example one can exclude interventions over constrained or goal variables. Next, we represent the family of intervention scenarios (G j ,C j ) j ∈J using predicates scenario/1, goal/3, and constrained/3. The facts scenario( j ) denote the scenarios to consider. The facts goal( j ,v,s)

with s = 1 (resp. s = -1) if G j (v) = t (resp. G j (v) = f ) and constrained( j ,v,s) with s = 1 (resp. s = -1) if C j (v) = t (resp. C j (v) = f )
denote the respective intervention goals and side constraints in each scenario (G j ,C j ). Notice that both predicates, goal/3 and constrained/3 are a straightforward elaboration upon predicates clamped/2 given in Listing 2.2.

Listing 5.1 shows the instance representation of our toy example. That is, the five logical networks in Figure 5.1 together with the intervention scenario (G 1 ,C 1 )

= ({d � → f , g � → f }, {e � → t }).
Notably, for the sake of understanding, we consider a toy example with a single intervention scenario. But in general, this instance representation and the logic program given below, support several scenarios.

Listing 5.1: Toy example problem instance (toy.lp) variable ( a ) . variable ( b ) . variable ( c ) . variable ( d ) .

variable ( e ) . variable ( f ) . variable ( g ) .

formula (1 ,d ,7) . formula (1 ,e ,0) . formula (1 ,f ,3) . formula (1 ,g ,2) . formula (2 ,d ,4) . formula (2 ,e ,0) . formula (2 ,f ,3) . formula (2 ,g ,2) . formula (3 ,d ,5) . formula (3 ,e ,0) . formula (3 ,f ,3) . formula (3 ,g ,2) . formula (4 ,d ,1) . formula (4 ,e ,0) . formula (4 ,f ,3) . formula (4 ,g ,2) . formula (5 ,d ,6) . formula (5 ,e ,0) . formula (5 ,f ,3) . formula (5 ,g ,2) .

dnf (5 ,8) . dnf (6 ,8) . dnf (2 ,14) . dnf (0 ,2) . dnf (0 ,0) . dnf (6 ,7) . dnf (4 ,9) . dnf (7 ,8) . dnf (6 ,0) . dnf (1 ,8) . dnf (1 ,0) . dnf (4 ,8) . dnf (3 ,16) . dnf (7 ,7) .

clause (16 , d ,1) . clause (0 ,b ,1) . clause (14 , e ,1) . clause (16 , e ,1) . clause (9 ,c , -1) . clause (8 ,a ,1) . clause (9 ,b ,1) . clause (2 ,c ,1) . clause (7 ,c , -1) . clause (14 , c , -1) .

scenario (1) . constrained (1 ,e ,1) . goal (1 ,d , -1) . goal (1 ,g , -1) . candidate ( a ) . candidate ( b ) . candidate ( c ) . candidate ( f ).

Encoding

Next we describe our encoding for solving the minimal intervention set problem as described earlier. Our ASP encoding is shown in Listing 5.2.

Listing 5.2: Logic program for finding intervention strategies (control.lp)

goal (T , S ) : -goal (_ ,T , S ) . goal ( T ) : -goal (T , _ ) . constrained (Z , E ) : -constrained (Z ,E , _ ) . constrained ( E ) : -constrained (_ , E ) . model ( M ) : -formula (M ,_ , _ ) .
satisfy (M ,V ,W , S ) : -formula (M ,W , D ) ; dnf (D , C ) ; clause (C ,V , S ) . closure (M ,V , T ) : -model ( M ) ; goal (V , T ) . closure (M ,V , S * T ) : -closure (M ,W , T ) ; satisfy (M ,V ,W , S ) ; not goal (V , -S * T ) . closure (V , T ) : -closure (_ ,V , T ) .

{ intervention (V , S ) : closure (V , S ) , candidate ( V ) }. : -intervention (V ,1) ; intervention (V , -1) . intervention ( V ) : -intervention (V , S ) .

eval (M ,Z ,V , S ) : -scenario ( Z ) ; intervention (V , S ) ; model (M ) . eval (M ,Z ,E , S ) : -model ( M ) ; constrained (Z ,E , S ) ; not intervention ( E ) . free (M ,Z ,V , D ) : -formula (M ,V , D ) ; scenario ( Z ) ; not constrained (Z , V ) ; not intervention ( V ) . eval_clause (M ,Z ,C , -1) : -clause (C ,V , S ) ; eval (M ,Z ,V , -S ); model ( M ) . eval (M ,Z ,V , 1) : -free (M ,Z ,V , D ) ; dnf (D , C ) ; eval (M ,Z ,W , T ) : clause (C ,W , T ) . eval (M ,Z ,V , -1) : -free (M ,Z ,V , D ) ; eval_clause (M ,Z ,C , -1) : dnf (D , C ) .

: -goal (Z ,T , S ) ; model ( M ) ; not eval (M ,Z ,T , S ) .

# const maxsize =0. : -maxsize >0; maxsize + 1 { intervention ( X ) }.

# show intervention /2.

Guessing an intervention set. In Lines 1-5 we define auxiliary domain predicates used in the remainder of the encoding. Lines 7-10 deserve closer attention since they allow us to reduce significantly the search space of candidate solutions. Note that, each candidate variable could be intervened positively, negatively, or not intervened. Then, if n is the number of candidate variables for interventions, this leads to 3 n possible intervention sets. We incorporate a preprocessing step introduced in [START_REF] Samaga | Computing combinatorial intervention strategies and failure modes in signaling networks[END_REF] that prunes variable assignments that can never be part of an intervention strategy. The idea is to inductively collect all assignments that, in principle, could be used to support a goal. First we gather all assignments that make a literal in a clause true and associate it with variable of the associated DNF (Line 7). Starting from the assignments that can satisfy a goal literal directly (Line 8), we inductively consider variable assignments (Line 9) that can support the assignments collected so far. Finally, in Line 10 we project all "relevant" interventions regardless of the logical network.

Let us illustrate this with our toy example. In order to satisfy goal( 1,d,) with respect to (V, φ 1 ), one would never consider to intervene the variable b. Since b does not reach d in (V, φ 1 ), an intervention on b is meaningless in order to inactivate d . However, when we look at (V, φ 2 ), (V, φ 4 ), and (V, φ 5 ), the variable b reaches d positively in those networks.

Hence, a negative intervention on b could help to satisfy goal(1,d,-1) in such cases. Next, we use a choice rule in Line 12 to generate candidate solutions. For example, one could generate the intervention set consisting of intervention(a,-1), intervention(b,-1), and intervention(c,1). We only choose interventions collected in the preprocessing step above.

It is worth noting that, even for such a small problem instance, the search space is reduced significantly. In our example, we have only 4 candidate variables for interventions, namely, a, b, c, and f . On the one hand, without pruning, we should evaluate 3 4 = 81 intervention sets. On the other hand, with the preprocessing, we are able to detect (at grounding time) that only interventions on a, b, and c are relevant since f does not reach any goal. Moreover, only a negative intervention is relevant for both a and b. Notably, this leads to 2 2 × 3 1 = 12 intervention sets to be evaluated. Next, the integrity constraint in Line 13 eliminates contradictory interventions, e.g. intervention(c,1) and intervention(c,-1). Whereas Line 14 simply projects the intervention set to the intervened variables regardless of their signature.

Fixpoint per logical network and intervention scenario. Lines 16-26 elaborate on the rules from Listings 2.3, 2.4 and 2.6 given in Section 2 in order to consider several logical networks simultaneously and compute the fixpoint for each of them accordingly. To be more precise, we need to describe which variables are clamped (in all networks) according to the side constraints C j in each scenario j and the intervention set I , namely, (V, φ i | C j •I ). Towards this end, we use the predicate eval/4, namely eval(i ,j ,v,s) to represent that in the network (V, φ i ) and intervention scenario (G j ,C j ), the variable v is clamped to value s. Following the previous example, this will generate predicates eval(i ,1,e,1), eval(i ,1,a,-1), eval(i ,1,b,-1), and eval(i ,1,c,1) with i = 1, . . . , 5. The remaining rules are adapted accordingly in order to compute for each logical network (V, φ i ) and intervention scenario (G j ,C j ), the corresponding fixpoint of Ω (V,φ i | C j •I ) . For our example, we can see how the positive intervention over c is propagated as follows. Since the variable d is not intervened, its formula is "free" in all scenarios and logical networks, namely, free(1,1,d,7), free (2,1,d,4), free (3,1,d,5), free (4,1,d,1), and free (5,1,d,6). Furthermore, let us illustrate the case for the logical network (V, φ 5 ). In such a network, we have φ 5 (d ) = a ∨ b ∨ ¬c, which in turn is represented by predicates dnf (6,8), dnf(6,0), dnf (6,7), clause(8,a,1), clause(0,b,1), and clause(7,c,-1). Then, from the rule in Line 22 we derive for i = 1, . . . , 5, predicates eval_clause(i ,1,8,-1), eval_clause(i ,1,0,-1), and eval_clause(i ,1,7,-1). Finally, in Line 26 we can derive predicates eval(i ,1,d,-1) with i = 1, . . . , 5.

Goals satisfaction. Line 28 declares an integrity constraint in order to eliminate answer sets describing intervention sets that do not satisfy all goals in every logical network and intervention scenario. Notably, following with our example, goal( 1,d,) is satisfied with respect to all logical networks. Similarly, goal(1,g,-1) is satisfied as well. Therefore, the intervention set described by predicates intervention(a,-1), intervention(b,-1), and intervention(c,1), is an intervention strategy with respect to all networks and interventions scenarios. Finally, the statements in Line 30 and 31 allows us to optionally bound the problem by considering only intervention sets up to a given size.

The following result shows the correctness of our ASP representation. We denote with τ((V, φ i ) i ∈N , (G j ,C j ) j ∈J , k) the set of facts describing the instance as in Listing 5.1, and with (see Table 3.1). Importantly, in regards of the available experimental observations and their intrinsic uncertainty, such logical networks explain the data equally well. Thus, in Chapter 4, we have presented a method in order to find an optimal experimental design to discriminate all models at hand. In principle, iterating over this loop of modeling and experimentation will yield more accurate logical models. Nevertheless, there may be several models which cannot be discriminated using the available experimental capacities. Therefore, instead of selecting a single model, now we are interested in reasoning over all networks, as described in Section 5.2, in order to find all minimal intervention strategies for each tolerance, namely, 16 networks for 0% tolerance, 144 networks for 2% tolerance, 2150 networks for 4%, 2306 networks for 4%, 3524 networks for 8% tolerance, and 5306 networks for 10% tolerance.

Intervention scenario. Recall that we have learned Boolean logic models from the prior knowledge network in Figure 3.2 describing signaling pathways in human liver cells. In principle, one could consider as intervention scenarios, any combination of goals and side constraints over all species in the network. However, in practice we are interested in finding intervention strategies for biologically relevant scenarios. In this case, we consider a single intervention scenario given by (G,C )

= ({c JU N � → f ,C RE B � → f }, �).
That is, we require to inactivate both species c JU N and C RE B without any side constraints. Note that we choose this intervention scenario for illustration purpose but at the same time, it is motivated by biological knowledge about the role these two species play in the signaling pathways under consideration.

Problem instances. Next, we consider the problem instances given by the intervention scenario (G,C ) = ({c JU N � → f ,C RE B � → f }, �) with respect to each set of logical networks listed in Table 3.1. Let us denote with M i the corresponding set of i logical networks, namely, M 16 , M 144 , M 2150 , M 2306 , M 3524 , and M 5306 . Then, in what follows, we denote with the filename networks-i.lp, the set of logic facts describing each problem instance as illustrated in Listing 5.1. Furthermore, we assume all variables or species, except for c JU N and C RE B , as candidates to be part of an intervention strategy. Eventually, we could restrict ourselves to more specific set of candidate variables which would reduce the search space. Finally, for each problem instance, we consider the enumeration of all inclusion-minimal intervention strategies, either bounded by the set cardinality k with k = 2, 3, 4, 5, or unbounded. In this case, we find 78 inclusion-minimal intervention strategies satisfying our scenario with respect to the 2306 logical networks in M 2306 . It is worth noting the different computation times reported by the solver in this case. Recall that the process for problem solving with ASP is divided into grounding and solving. In fact, for these instances, the search space of possible intervention sets is relatively small compared to other instances reported in the next section. In this cases, the number of candidate variables to be intervened is only 29. This would require to evaluate 3 29 =∼ 6.8 × 10 13 possible intervention sets. However as explained above, during grounding we can reduce this number significantly. The precise reduction depends on each set of logical networks but ranges from 2048 to ∼ 10 6 . Notably, these are rather small instances compared to other cases where the number of possible intervention sets is ∼ 6 × 10 47 . However, the fact that we consider many logical networks simultaneously, leads to a more demanding grounding. Therefore, for these cases, most of the computation time is actually during grounding rather than solving. For example, in Listing 5.4 the CPU time is around 10.5 seconds, whereas only 2 seconds are strictly during search.

Minimal intervention strategies

Next, in Table 5.1 we report results for all problem instances. For each set of logical networks, namely, M 16 , M 144 , M 2150 , M 2306 , M 3524 , and M 5306 , we report the number of inclusionminimal intervention strategies up to a given size k = 2, 3, 4, 5, or unbounded (∞). Also, in order to emphasize the computation time during grounding or solving, we show the total CPU time reported by clingo but also, in parentheses, the time strictly during solving. As expected, both grow as we increase the number of logical networks. However, for the largest set of logical networks, that is M 5306 , total CPU time is only 27.37 seconds, whereas around 6 seconds are needed for solving. Interestingly, we have found exactly the same intervention strategies for M 16 and M 144 , for M 2150 and M 2306 , and for M 3524 and M 5306 . This is supported by results Table 5.1: Enumeration of all inclusion-minimal intervention strategies up to a given size k = 2, 3, 4, 5, or unbounded (∞). For each set of logical networks (M i ), we report the number of intervention strategies (I ) and the CPU time (t enum ). Also, in parentheses, we report the time strictly during solving.

≤ 2 ≤ 3 ≤ 4 ≤ 5 ∞ M i I
t enum I t enum I t enum I t enum I t enum 16 7 0.04s (0.001s) 14 0.04s (0.001s) 14 0.03s (0.001s) 14 0.03s (0.001s) 14 0.04s (0.001s) 144 7 0.36s (0.005s) 14 0.36s (0.008s) 14 0.36s (0.008s) 14 0.36s (0.008s) 14 0.36s (0.008s) 2150 1 8.39s (0.239s) 18 9.1s (0.806s) 70 9.86s (1.624s) 78 9.82s (1.648s) 78 9.93s (1.771s) 2306 1 9.44s (0.326s) 18 9.87s (0.945s) 70 10.55s (1.713s) 78 10.54s (1.716s) 78 10.68s (1.884s) 3524 1 14.19s (0.355s) reported in Chapter 3 where such pairs of families shown similar number of input-output behaviors (Table 3.1) and MSEs distributions (Figure 3.3). Now, in order to have a closer look at what interventions are found for each case, in Figure 5.2 we show the frequency of each single intervention among all strategies for the unbounded case (∞ column in Table 5.1). We note that, all single interventions occur in less than 50% of the strategies. This suggests that, there is no evident species in order to control the system, but instead, several combinatorial mechanisms require to combine multiple interventions together. Nonetheless, some interventions are clearly more frequent than others. But still, while a given intervention, e.g., M E K 12 � → f , occurs in almost half of the strategies with respect to M 16 and M 144 , with respect to larger sets of networks, its frequency drops to 10%.

m k k 4 = -1 p 3 8 = -1 m a p 3 k 1 = -1 T G F a = -1 r a s = -1 p 9 0 R S K = -1 J N K 1 2 = -1 I L 1 a = -1 t r a f 6 = -1 m s k 1 2 = -1 M E K 1 2 = -1 P I 3 K = -1 T G F a = 1 I G F 1 = -1 A K T = 1 I G F 1 = 1 P I 3 K = 1 m a p 3 k 7 = -1 T N F a = -
Analogously, but in the opposite way, the same happens with r as � → f . Notably, interventions over certain species are found only when we consider larger sets of logical networks (red and green bars). In fact, as shown in Table 5.1, while only 14 intervention strategies are found with respect to M 16 and M 144 , if we consider either M 3524 or M 5306 , we found up to 104 inclusionminimal intervention strategies. Therefore, reasoning over a large family of feasible logical networks allows us to identify alternative intervention strategies. Furthermore, this poses the question of whether certain strategies are more robust than others and how to identify them.

Towards small yet robust intervention strategies

Nowadays, in signaling networks, more than four or five interventions combining different stimuli and inhibitors can be considered as a long-term technological perspective. Therefore, in practice, small intervention strategies are preferred in terms of experimental feasibility. However, too small strategies are very likely to fail due to robustness and cellular complexity [START_REF] Stelling | Robustness of cellular functions[END_REF]. Hence, we need to find a balance between small (and feasible) yet robust intervention strategies to control the cell. Our approach to achieve such a challenge is by reasoning over all feasible logical networks. In Figure 5.3 we show the 14 intervention strategies found with respect to M 16 and M 144 . Each path from the node "SCENARIOS CON-STRAINTS" to the node "SCENARIOS GOALS", describes a different strategy where species are intervened according to their coloring: red for inhibitions and green for activations. Nonetheless, in this case all strategies consist only of inhibitions. For instance, {M

E K 12 � → f , I L1a � → f } and {M E K 12 � → f , J N K 12 � → f , msk12 � → f },
are two different intervention strategies of size 2 and 3 respectively. Now, if we restrict ourselves to logical networks in M 16 or M 144 , these 14 intervention strategies are, in principle, all equally valid. But, if we consider a larger set of feasible networks, e.g., M 5306 , we can rule out more than half of these strategies before going to the laboratory. More precisely, out of the 14 strategies shown in Figure 5.3, only 6, the ones highlighted with stronger red, are conserved among all logical networks in M 5306 . That is, the intervention strategies valid with respect to all M i are:

                     {M E K 12 � → f , map3k1 � → f } {M E K 12 � → f , J N K 12 � → f , msk12 � → f } {M E K 12 � → f , J N K 12 � → f , p38 � → f } {M E K 12 � → f , J N K 12 � → f , mkk4 � → f } {p90RSK � → f , J N K 12 � → f , msk12 � → f } {p90RSK � → f , map3k1 � → f , msk12 � → f }                     
Intuitively, this way we are able to detect earlier those intervention strategies that are too specific and do not take into account alternative pathways. Therefore, by reasoning over several sets of feasible logical networks we may find small yet robust intervention strategies. Also, it is worth noting that, species msk12, mkk4, and map3k1 are neither measured, nor manipulated in the dataset used for learning each set of logical networks. Hence, the fact that we found strategies involving such species suggests the necessity of further experimentations in order to elucidate their role in the biological system at hand.

Comparing with a dedicated algorithm

In [START_REF] Kaminski | Minimal Intervention Strategies in Logical Signaling Networks with Answer Set Programming[END_REF] we have evaluated the performance and scalability of our ASP-based solution over four real-world and biologically relevant benchmarks. Three of them were used in [START_REF] Samaga | Computing combinatorial intervention strategies and failure modes in signaling networks[END_REF] and their corresponding (manually curated) logical networks were recently published [START_REF] Saez-Rodriguez | A logical model provides insights into t cell receptor signaling[END_REF], Samaga et al., 2009]. Further, the fourth benchmark consisted of an unpublished logical network provided by Axel von Kamp and Steffen Klamt. While the authors in [START_REF] Samaga | Computing combinatorial intervention strategies and failure modes in signaling networks[END_REF] restricted their study to a maximum cardinality of 3, we extended this limitation to a maximum cardinality of 10 or no limit at all. Importantly, the search space for these problem instances is significantly larger than the ones Figure 5.3: Robust intervention strategies. We plot the 14 intervention strategies found with respect to M 16 and M 144 . Each path from the node "SCENARIOS CONSTRAINTS" to the node "SCENARIOS GOALS", describes a different strategy where species are intervened according the their coloring: red for inhibitions and green for activations. Out of the 14 strategies only 6, the ones highlighted with stronger red, are conserved among all logical networks in M 5306 .

shown above. More precisely, the number of candidate intervention sets to be considered by the solver range from 10 11 to 10 47 . Nonetheless, experiments have shown that our approach outperforms the dedicated algorithm in up to four orders of magnitude (for small strategies still feasible for the algorithm). This was not very surprising since such an algorithm is based on a standard breadth-first search using additional techniques for search space reduction. More importantly, using ASP we were able to search for significantly larger intervention strategies or even solve the unbounded problem despite the very large search space. Similarly to what we have shown above, if we consider a small number of interventions, the number of solutions is in the order of tens. But, if a larger number of interventions is allowed, we found hundreds or even thousands of feasible solutions. Note that, all benchmarks we evaluated in [START_REF] Kaminski | Minimal Intervention Strategies in Logical Signaling Networks with Answer Set Programming[END_REF] consisted of a single and manually curated logical network. Hence, we expect that our approach for reasoning over several alternative logical networks (as they become available) can help to rule out solutions and identify robust strategies satisfying intervention scenarios with respect to all networks.

Conclusion

In this chapter we have addressed the problem consisting of finding intervention strategies in logical signaling networks. That is, inclusion-minimal sets of activations and inhibitions forcing a set of target species into a desired steady state under various scenarios. The identified interventions can be exploited to control the biological system or interpreted as causes for an abnormal cellular response (diagnosis).

In this context, dealing with large-scale and (possibly many) alternative networks describing the same biological system, leads to challenging combinatorial problems that require advanced solving technologies. In fact, previous work on this subject consists of dedicated algorithms and special purpose search space reduction techniques for coping with combinatorial explosion [START_REF] Samaga | Computing combinatorial intervention strategies and failure modes in signaling networks[END_REF]. More broadly, other authors have elaborated upon concepts of electronic circuit fault diagnosis engineering [START_REF] Li | Predicting essential components of signal transduction networks: A dynamic model of guard cell abscisic acid signaling[END_REF][START_REF] Abdi | Fault diagnosis engineering of digital circuits can identify vulnerable molecules in complex cellular pathways[END_REF][START_REF] Layek | Cancer therapy design based on pathway logic[END_REF] and standard graph theory [START_REF] Wang | Elementary signaling modes predict the essentiality of signal transduction network components[END_REF], for the identification of essential components in the network. Importantly, despite the specific problem settings and computational approaches in these contributions, all of them have considered a single logic network describing the system. However, as we illustrate in this thesis, due to limited observability or the uncertainty in experimental measurements, it often happens that a single model is non-identifiable when we use reverse engineering methods. Thus, identified interventions (or essential components) should fulfill the desired goals in every feasible logical network.

Notably, this may lead to more complex but also more robust solutions. As mentioned earlier, large-scale (e.g. > 10) interventions combining different stimuli and inhibitors, can be considered as a long-term technological perspective. Nevertheless, in general, we did not find intervention strategies of size bigger than 10. On the one hand, this suggests that extending the set of interventions may not be interesting for the systems we have considered in our benchmarks. On the other hand, knowing that a large number of interventions are required to reach certain state could help to understand (at least theoretically) systems' robustness and complexity. Hence, being able to compute both small and large admissible intervention strategies over an ensemble of feasible logical networks, appears as an interesting and distinct feature of our approach.

Both computational and biological perspective tracks are open. On the computational side, despite the successful performance in all benchmarks, a precise estimation of the empirical complexity appears to be non trivial and very specific to each case. Given a problem instance, the number of candidate solutions to be considered by the solver can be computed analytically. However, experiments have shown that this is not the only parameter determining the empirical complexity. The number of goal variables and their location in the networks, the number of intervention scenarios, and the number of networks and their structural properties may have a strong impact on the computational efforts required in practice. On the biological side, in the light of such a large number of solutions, the way to select among them arises. In fact, we expect that our approach introduced in [START_REF] Kaminski | Minimal Intervention Strategies in Logical Signaling Networks with Answer Set Programming[END_REF] and extended here for reasoning over several alternative logical networks, will help to rule out solutions and identify small yet robust intervention strategies. Therefore, the work presented in this chapter is a key methodological contribution allowing systems biologists to draw robust insights even under uncertainty.

6 Software toolbox: caspo

In practice, problem solving using ASP involves three main steps. First, certain input data must be converted to logic facts describing the corresponding problem instance. Second, the problem instance needs to be combined with the specific set of logic rules encoding the problem to be solved. Third, answer sets returned by the ASP solver must be interpreted according to the representation used in the encoding. Hence, a software package providing an interface to the ASP-based solutions detailed in previous chapters would ease the accessibility for end-users, as well as the integration with available tools for simulation and analysis of logical models. This chapter presents such a software tool and illustrates its main features.

Introduction

In practice, interactions graphs, experimental datasets, logical networks, and similar knowledge in systems biology is often (publicly) available in different kinds of formats. Clearly, converting such a knowledge from their corresponding format to a set of logic facts, e.g., Listing 3.1, Listing 4.1, or Listing 5.1, is a tedious and error-prone task if do it by hand. In fact, this can be easily automated by using any popular scripting language, e.g. python.1 Analogously, the resulting answer sets from the ASP solver can be converted back to "standard" formats for subsequent analysis with available tools or even visualized in order to facilitate their interpretations. Notably, over the last few years, many simulation and analysis software tools for logical models have been developed, among them, ADAM [START_REF] Hinkelmann | ADAM: analysis of discrete models of biological systems using computer algebra[END_REF], BoolNet [START_REF] Mussel | BoolNet-an R package for generation, reconstruction and analysis of Boolean networks[END_REF], BooleanNet [START_REF] Albert | Boolean network simulations for life scientists[END_REF], Cell Collective [START_REF] Helikar | The Cell Collective: toward an open and collaborative approach to systems biology[END_REF], CellNetAnalyzer [Klamt et al., 2006a], CellNOpt [START_REF] Terfve | CellNOptR: a flexible toolkit to train protein signaling networks to data using multiple logic formalisms[END_REF], ChemChains [START_REF] Helikar | ChemChains: a platform for simulation and analysis of biochemical networks aimed to laboratory scientists[END_REF], GNA [START_REF] Batt | Genetic network analyzer: a tool for the qualitative modeling and simulation of bacterial regulatory networks[END_REF], GINsim [START_REF] Naldi | Logical modelling of regulatory networks with GINsim 2.3[END_REF], SimBoolNet [START_REF] Zheng | SimBoolNet-a Cytoscape plugin for dynamic simulation of signaling networks[END_REF]SQUAD [Cara et al., 2006]. The underlying methods of these tools are very heterogeneous, including, ad hoc algorithms, metaheuristics, and symbolic model checking by means of temporal logic and specialized tools, such as NuSMV [START_REF] Cimatti | NuSMV 2: An OpenSource Tool for Symbolic Model Checking[END_REF]. Moreover, in general, users and developers of such tools, do not have the expertise to deal with ASP Figure 6.1: Pipeline for reasoning on the response of logical signaling networks using caspo.

At first, all (nearly) optimal Boolean logic models are learned by confronting prior knowledge on causal interactions with a phosphorylation dataset. Then, supported by insights from experts and various validation methods, we can decide if the ensemble of Boolean models needs further refinements. In such a case, optimal experiments can be designed in order to discriminate the set of behaviors at hand. By combining the previous dataset with the new observations, the learning is performed again yielding a new ensemble of models. After several iterations, the "high-quality" ensemble of logical networks can be used to find (robust) intervention strategies and generate novel hypotheses.

encodings and systems. Thus, a software package providing an interface to the ASP-based solutions detailed in previous chapters would ease the accessibility for end-users, as well as the integration with available tools for simulation and analysis of logical models.

Software toolbox: caspo. In order to encapsulate our ASP-based solutions, we have implemented the python package caspo which is freely available for download. 2 More broadly, caspo is part of BioASP, a collection of python packages leveraging the computational power of ASP for systems biology. 3 The aim of caspo is to implement a pipeline for automated reasoning on logical signaling networks providing a powerful and easy-to-use software tool for systems biologists. In Figure 6.1 we show a schematic view of such a pipeline. At first, all (nearly) optimal Boolean logic models and their corresponding logical input-output behaviors, are learned as shown in Chapter 3. Then, supported by insights from experts and various validation methods, we can decide if the ensemble of Boolean models needs further refinements. If this is the case, we look for an optimal experimental design in order to discriminate the set of input-output behaviors as presented in Chapter 4. By combining the initial dataset with the new experimental observations, the learning is performed again yielding a new ensemble of models. After several iterations of this cycle, a "high-quality" ensemble of logical networks can be used to find intervention strategies as shown in Chapter 5. Each section of this pipeline is implemented in caspo by means of subcommands, namely, learn, analyze, design, and control. Notably, this in line with the loop of hypotesis-driven research in biology [START_REF] Ideker | A new approach to decoding life: systems biology[END_REF][START_REF] Kitano | Systems biology: a brief overview[END_REF]. Moreover, this iterative process could be automatized allowing an autonomous scientific discovery [START_REF] Sparkes | Towards robot scientists for autonomous scientific discovery[END_REF].

Except for CellNOpt and BoolNet, all tools mentioned above are mainly focused on the characterization of dynamical properties emerging from the simulation of a single logical model provided by the user. In the case of CellNOpt, the focus is on the training of logical models by using metaheuristics, whereas BoolNet includes two algorithms, namely, Best-Fit Extension [START_REF] Lähdesmäki | On learning gene regulatory networks under the Boolean network model[END_REF] and REVEAL [START_REF] Liang | REVEAL, a general reverse engineering algorithm for inference of genetic network architectures[END_REF], for the reconstruction of gene regulatory Boolean networks from time-series gene expression profiles. In addition, various simulation analyses are provided by both packages as well. The tool CellNetAnalyzer implements the identification of intervention strategies as described in Chapter 5 but with respect to a single logical network and limited to small strategies (less than 4 interventions). Furthermore, several tools allow the user to introduce artificial perturbations and simulate the system's response. Nevertheless, all tools aim at modeling a given biological system by means of one logical network only. Next, dynamical and structural analysis (often computationally demanding) are conducted over the model. In this context, a distinct feature of caspo is the fact that it aims at having an exhaustive characterization of feasible models. Either via automated learning, or directly provided by the user. Afterwards, instead of selecting a single model, the goal is to provide automated reasoning over the ensemble of models at hand. First to find optimal experimental designs for models discrimination, and second for finding minimal intervention strategies valid in all networks. Notably, towards this end, caspo strongly relies on ASP which is another distinct feature from the methodological point of view.

In the remainder of this chapter we present the software tool caspo describing its high-level design and main features. Furthermore, we illustrate how end-users can easily go through the pipeline shown in Figure 6.1 by using each of the provided subcommands.

6.2 Software design 6.2.1 High-level software design Internal modules. The architecture of caspo is shown in Figure 6.2. The design comprises three different layers of internal modules. A first layer providing the interface with end-users of the software. Currently this layer has only the console module which implements the entrypoints for caspo subcommands from the command-line. In the future, this layer could be extended with a module for a graphical user interface. A middle layer comprises various modules, namely, learn, design, control, analyze, and visualize, each of them implementing functionalities for the corresponding subcommand. The module learn implements the learning of Boolean logic models of immediate-early response as described in Chapter 3. The module design implements the experimental design to discriminate input-output behaviors as described in Chapter 4. The module control implements the identification of intervention strategies as described in Chapter 5. The module analyze implements the search of logical input-output behaviors among a family of Boolean logic models as described in Chapter 3. Furthermore, relatively simple statistical analysis is provided in this module as well. Finally, the module visualize implements basic visualization features for logical networks and inter- vention strategies. Interestingly, all features implemented by the aforementioned modules are independent from the command-line usage of caspo. This way, we aim at providing not only a software for end-users, but also a powerful toolbox to be used by other developers to build their own software. A third layer, namely, core, implements "low-level" functionalities common to all other modules in caspo.

External dependencies. In Figure 6.2 we also shown the main external dependencies of caspo. On the one hand, to build caspo, we rely on relatively standard python packages, such as, pyparsing4 , numpy5 , networkx 6 , and pydot 7 . Notably, all of them are open-source projects under different free software licenses. For more details on each package, we refer the reader to the corresponding website. On the other hand, we highlight the external dependency on the python package pyzcasp8 . In fact, pyzcasp was developed within this thesis in order to build caspo on top of it. However, it was developed in such a way to provide a general purpose framework to build on top of ASP tools. Therefore, it is not only of interest for caspo or biological applications, but for any other project aiming at the integration of python and ASP. Broadly speaking, the goal of pyzcasp is to provide an abstraction layer over ASP systems. Notably, such an abstraction allows us to have a clear separation of responsibilities, whereas it facilitates the maintenance of both, the application, in our case, caspo, and the communication with third-party ASP tools. In practice, problem solving using ASP involves three main steps. At first, certain input data, normally stored in different files with different formats, need to be converted to logic facts describing the corresponding problem instance. Second, the problem instance needs to be combined with the specific set of logic rules encoding the problem to be solved. It is worth noting that, sometimes the same problem can be addressed with different ASP tools which in turn, may accept different input languages and options. Hence, in such cases, we may need to select, among several encodings for the same problem, the appropriate encoding for a specific ASP tool. Next, the corresponding ASP tools are executed with the problem instance and encoding as input. Third, answer sets returned by the ASP solver must be interpreted according to the representation used in the encoding. Essentially, the package pyzcasp provides a framework for dealing with these three steps in a robust way within a python environment. Currently, it supports the usage of most common tools from Potassco: the Potsdam Answer Set Solving Collection.9 Nevertheless, support for other ASP tools is planned in the future.

Generic workflow for subcommands

The workflow for main caspo subcommands, namely, learn, analyze, design, and control, is shown in Figure 6.3. Essentially, each of these subcommands is a particular use case of the more general workflow for problem solving using ASP as detailed earlier. In all cases, some input data is provided by the user in one or more files. In general, each subcommand deals with different file formats, but all of them need to convert the input data to logic facts describing the corresponding problem instance. Next, the problem instance together with the specific problem encoding are given to the corresponding ASP tools for solving. Furthermore, in some cases, very specific parameters are given to the solver in order to obtain right solutions or improve performance. For instance, in order to enumerate all inclusion-minimal answer sets as we do it when looking for intervention strategies, the ASP solver clasp must be executed with parameters --dom-pref=32 --dom-mod=6 --heu=domain -n0 (see Listing 5.3). Once the ASP solving has finished, the resulting answer sets are loaded into memory as python objects for further analysis. In the simplest case, solutions are written to output files in standard formats. However, in some cases, additional "business logic" is implemented for each subcommand.

For instance, the identification of input-output behaviors using Algorithm 1 (Section 3.4.3), or first find the optimum and then, with a second solver call, enumerate all solutions within Figure 6.3: Workflow for caspo subcommands. For clarity, we distinguish three execution levels.

First, the command-line (end-user) level where input and output files are handled. Second, the subcommands (application) level where input data is converted to logic facts, combined with a specific logic program, and given to the next level for launching ASP tools. Normally, some kind of "business logic" is implemented at this level, for instance, the identification of input-output behaviors using Algorithm 1 (Section 3.4.3), or first find the optimum and then enumerate solutions within certain tolerance. Third, the ASP solving (external) level where ASP tools are executed using system calls and the resulting answer sets are loaded into memory as python objects, which in turn are provided to the application level for further analysis.

certain tolerance. Altogether, caspo subcommands provide high-level automated reasoning on logical signaling networks by leveraging the computational power and reasoning modes of ASP systems.

Usage

Usage for end-users

In what follows we illustrate how end-users can easily go through the pipeline shown in Figure 6.1 by using each of the subcommands provided by caspo. To start with, in Listing 6.1 we show how to ask for help on the usage of caspo from the command-line.

Listing 6.1: Help message for caspo. Learning (nearly) optimal Boolean logic models. The learning of Boolean logic models as described in Chapter 3 is provided by the subcommand learn. In Listing 6.2 we show the corresponding help message for this subcommand. In this case, there are three required arguments, namely, the prior knowledge network (PKN), the phospho-proteomics dataset, and the characteristic time-point for the immediate-early response. The PKN must given in the so-called simple interaction format (SIF).10 Typically, lines in a SIF file specify a source node, an interaction type, and one or more target nodes. In our context, we restrict ourselves to SIF files where the interaction type is either 1 or -1, and there is only one target node. Hence, this way we can easily represent the interaction graph describing the PKN at hand. Note that the SIF file does not provide information about which nodes are stimuli, inhibitors or readouts. Currently, such information must be extracted from the dataset file which we describe next.

The phospho-proteomics dataset must given in the so-called minimum information for data analysis in systems biology (MIDAS) format. 11 For more details on this file format we refer the reader to [START_REF] Saez-Rodriguez | Flexible informatics for linking experimental data to mathematical models via DataRail[END_REF]. In essence, a MIDAS file is a comma-separated values (CSV) file with a simple naming convention in order to identify columns as: (1) experimental perturbations, (2) time points for data acquisition, or (3) phosphorylation activities describing the response of the system. Then, each row in the file describes an experimental condition together with the phosphorylation activities at a certain time-point. Finally, the third required argument is the characteristic time-point for the immediate-early response. Clearly, the given time point must be present in the MIDAS file or an exception is raised otherwise. In addition to the three required arguments, several optional arguments can be provided as shown in Listing 6.2. Next, in Listing 6.3 we show the execution of the learn subcommand for our toy example. In this case, we use --fit 0.1 --size 5 in order to enumerate all (nearly) optimal Boolean logic models with a tolerance of 10% over the fitness and 5 over the size. The only output in this case is a CSV file, namely, networks.csv describing all logical networks found during enumeration with ASP. The first row or header of this file contains all possible (signed) directed hyperedges for the given PKN. It is worth recalling that, we interpret a (signed) directed hyperedge as the conjunction of its source (signed) nodes acting over the target node. Furthermore, we interpret several hyperedges with the same target node as the disjunction of the corresponding conjunctions of their sources nodes. Identifying logical input-output behaviors. The identification of logical input-output behaviors as described in Chapter 3 is provided by the subcommand analyze. Actually, as we show below, this subcommand implements various additional features apart from the identification of input-output behaviors. In this case, there are no required arguments but instead, caspo performs all available computations for the given inputs. In particular, in order to identify logical input-output behaviors among a family Boolean logic models we need to provide two inputs. Of course, the family of logical networks is required. But also, we need to provide again the dataset and time point used during learning. There are two reasons for this. First, as with the SIF file for the PKN, the information about inputs, i.e., stimuli or inhibitors, and outputs, i.e., readouts, is not given in the networks file. Thus, we use the MIDAS file to extract such information. Second, some of the additional computations use the experimental observations in the dataset, e.g., computing MSEs for every logical network. In Listing 6.4 we show the corresponding help message for this subcommand. • networks-stats.csv: frequency of each logical interaction and mutually exclusive/in- clusive pairs.

• networks-mse-len.csv: two additional columns to the input file networks.csv with the corresponding MSE and size for each network.

• behaviors.csv: exactly one representative logical network for each behavior found.

• behaviors-mse-len.csv: two additional columns to the file behaviors.csv with the corresponding MSE and number of Boolean logic models for each input-output behavior.

• variances.csv: the variance for each output prediction over all behaviors.

• core.csv: experimental conditions for which all behaviors agree on the given response.

• summary.txt: a summary as printed in the terminal. Next, in Listing 6.7 we show the execution of the design subcommand for our toy example. In this case, we use --stimuli 3 --inhibitors 2 in order to restrict the experimental design to experiments having at most, 3 stimuli and 2 inhibitors. The only output in this case is a CSV file, namely, opt-design-0.csv describing all experimental conditions in the optimal experimenal design found with ASP. Columns represent either stimuli or inhibitors, and rows or lines specify whether the corresponding species is clamped (1) or not (0) in that experimental condition. Once all suggested experiments are carried out in the laboratory, new experimental observations are added to the existing dataset. Next, the subcommands learn and analyze introduced earlier, can be used again for learning a refined family of Boolean logic models and its corresponding logical input-output behaviors. Notably, this loop can continue until we find an unique input-output behavior, or we consider that the current ensemble of logic models is accurate enough. Listing 6.7: Running design subcommand $ caspo design out / behaviors . csv dataset . csv --stimuli 3 --i nhibitors 2 Running caspo design ... Wrote out / opt -design -0. csv Enumerating minimal intervention strategies. The enumeration of all minimal intervention strategies as described in Chapter 5 is provided by the subcommand control. In Listing 6.8 we show the corresponding help message for this subcommand. In this case there are two required arguments, namely, the family logical networks and the intervention scenarios. The family of logical networks must be given in a CSV file as already described, e.g. the output file networks.csv from the learn subcommand. The intervention scenarios must also be given in a CSV file. As with the MIDAS file, we adopt a simple naming convention in order to identify columns as side constraints or goals. Then, each row specifies whether the corresponding species is clamped positively (1), negatively (-1), or not clamped (0) in that intervention scenario. Listing 6.8: Help message for control subcommand Next, in Listing 6.9 we show the execution of the control subcommand for our toy example.

$ caspo control --help usage : caspo control [ -h ] [ --size M ] [ --allow -constraints ] [ --allow -goals ] [ --gringo G ] [ --clasp C ]
The only output in this case is a CSV file, namely, strategies.csv describing all inclusionminimal intervention strategies found with ASP. Recall that each intervention strategy guarantees that all scenarios are satisfied in every logical network. The format of this output file is very simple. Columns represent all variables in the logical networks and rows specify whether the corresponding species is clamped positively (1), negatively (-1), or not clamped (0) in that intervention strategy. Listing 6.9: Running control subcommand Next, in Listing 6.12 we show the execution of the visualyze subcommand for our toy example. Let us briefly describe the output files from this subcommand which we also shown in Figure 6.4.

• pkn.dot: PKN with the corresponding experimental setup (Figure 6.4a).

• network-i .dot: every logical network (V, φ i ) (Figure 6.4d). • networks-union.dot: union (overlapping) of all logical networks (Figure 6.4b).

• strategies.dot: all intervention strategies (Figure 6.4c).

Listing 6.12: Running visualize subcommand $ caspo visualize --pkn pkn . sif --midas dataset . csv \ --networks out / networks . csv --union \ --strategies out / strategies . csv Wrote out / pkn . dot Wrote out / network -1. dot to out / network -5. dot Wrote out / networks -union . dot Wrote out / strategies . dot

Usage for developers

In the previous section we have detailed how end-users can use caspo without any programming expertise but only by using the available subcommands. Notably, such a level of usability is fundamental in order to allow (systems) biologists to profit from our software in their daily research. Nevertheless, it may be the case that one needs to integrate different software tools in a larger framework. Towards this end, we have developed caspo in such a way that other developers can access to all its features programmatically. For the sake of brevity, we refrain from giving a detailed description of all classes and methods available and refer the interested reader to the publicly available repository where caspo is maintained. 13 It is worth noting that, this allows other software tools to take advantage of the computational power of ASP at a higher level of abstraction and looking at the solving process as a black-box procedure managed by caspo. Moreover, the component-based design of caspo aims at providing a seamless interface with third-party software. More precisely, it is not only possible to use caspo programmatically, but also, developers can plug their own components and overwrite default implementations. Altogether, apart from being an easy-to-use software tool for endusers, caspo can be used by developers as a toolbox by leveraging the computational power of ASP for building their own software.

Conclusion

In this chapter we have presented a software toolbox providing an interface to the ASP-based solutions detailed in previous chapters. Altogether, our software implements a complete pipeline for automated reasoning on logical signaling networks providing a powerful and easy-to-use software tool for systems biologists. Each section of this pipeline is implemented by means of subcommands, namely, learn, analyze, design, control, and visualize. In fact, using a toy example, we have illustrated how end-users can easily go through the pipeline using such subcommands. Moreover, the component-based design of caspo aims at providing a seamless interface with third-party software. Therefore, apart from being an easy-to-use software for end-users, caspo can be used by developers as a toolbox by leveraging the computational power of ASP for their own software.

In this context, the development of standard formats would ease the integration of different tools by taking advantage of complementary features from each software. Typically, such tools are developed independently by different research groups around the world. Hence, it is rather hard to converge towards standards and common practices. In fact, an extension to the popular systems biology markup language (SMBL) [START_REF] Hucka | The systems biology markup language (SBML): a medium for representation and exchange of biochemical network models[END_REF] has been recently proposed as a more appropriate and specific standard for describing logic-based models, the so-called SBML Qualitative Models (SBML qual) [START_REF] Chaouiya | SBML qualitative models: a model representation format and infrastructure to foster interactions between qualitative modelling formalisms and tools[END_REF]. Therefore, in the future we plan to support both import and export features via SBML qual in caspo. Also, given the active research and development in the ASP community, we expect to extend and enrich the implemented pipeline for automated reasoning as soon as new developments come to light. It is worth noting that, compared to other available software tools, caspo is still in its infancy. Thus, based on the feedback from users, developers and research community in general, we hope to continue improving the presented software in order to make it an atractive and useful alternative for systems biologists in the near future.

terms of fixpoint semantics. Next, we have benefited from the elaboration tolerance of ASP in order to adapt such a representation, with relatively little effort, to each specific problem in subsequent chapters. Interestingly, the computational performance is significantly improved with respect to state-of-the-art algorithms to solve the same problems. But more importantly, the exhaustive nature of ASP have allowed us to find feasible solutions that were missing when using existing methods. Notably, this poses new challenges related to the analysis and interpretation of possibly many solutions. For instance, in Chapter 3, in the light of a large number of feasible logical networks, we have introduced the concept of logical input-output behaviors which allows us to focus on predictions rather than alternative mechanisms. In fact, the proposal of experimental design presented in Chapter 4 was motivated by the existence of several input-output behaviors and the necessity to discriminate among them. Yet, there may be several models which cannot be discriminated using the available experimental settings. Thus, instead of selecting a single model, in Chapter 5 we aimed at reasoning over all of them in order to find more robust interventions strategies. Altogether, this thesis illustrates the potential of ASP to address hard combinatorial search and optimization problems related to qualitative modeling of biological systems. In fact, our work contributes to a growing list of ASP applications in systems biology which show its increasing impact on the field.

On the implementation side, in Chapter 6 we have presented a software toolbox providing an interface to the ASP-based solutions for each of the discussed problems. Essentially, the goal of such a software is to encapsulate the workflow for problem solving with ASP in our specific context. To this end, we have used a popular and high-level scripting language such as python.

Notably, this will ease the accessibility for end-users, as well as the integration with available tools for simulation and analysis of logical models. Altogether, our software implements a complete pipeline for automated reasoning on logical signaling networks providing a powerful and easy-to-use software tool for systems biologists.

Discussion and prospective

Introduced by Stuart Kauffman 45 years ago, Boolean networks are a particular case of dynamical systems used for modeling biology. Notably, due to their binary states and synchronous updates, Boolean networks are among the simplest and more abstract dynamical systems. On the one hand, such a crude simplification of biological reality is a limitation in terms of the kinds of systems we can describe. On the other hand, is precisely because of their simplicity that Boolean networks are attractive for systems biologists. Typically, in the biological literature signaling networks are described by biologists as "pathways cartoons". In fact, such cartoons are commonly found in pathway databases as well. In this context, while graph-based models are the natural approach for static analysis, logic-based models, such as Boolean networks provide a framework still intuitive for biologists but tailored to relatively complex dynamic analysis. Of course, as soon as biologists gain a deeper understanding of a particular system, such simplistic models may become obsolete and more elaborate formalisms should come into play. However, nowadays, the lack of quantitative information at systems level suggests 7.2. Discussion and prospective that, for some time to come, high-level computational abstractions will be crucial for pushing the boundaries of biological knowledge. Moreover, despite their limitations, such simple and intuitive modeling frameworks can help to reduce the existing gap between theoretical and experimental research in systems biology.

We have adopted ASP as our computational method. Notably, like any other method, ASP has its own strengths and weaknesses. On the one hand, thanks to its origins in the area of knowledge representation and reasoning, ASP provides a simple yet rich and fully declarative modeling language. Furthermore, in the last decade, the development of highly efficient solvers have made of ASP an attractive framework for problem solving, yielding comparable results to integer linear programming or Boolean constraint solving. In this context, the added value of ASP is two-fold (at least). First, it provides a high-level executable modeling language.

In practice, this allows for very compact problem representations that can be tested and refined on-the-fly. Second, modern solvers implement various reasoning modes, such as enumeration, union and intersection, multi-objective optimization, and combination thereof.

Notably, this allows us to address a multitude of problems with minimal effort or ad hoc programming overhead. On the other hand, two aspects (at least) of ASP may limit its usage in systems biology. First, its strictly discrete nature forbids us to take into account numerical or quantitative information. Sometimes and to some extent, available data can be discretized. Nonetheless, in general, ASP is rather tailored to combinatorial problems with constraints over variables with either Boolean, or small domains. Second, the two phases in the process for problem solving with ASP, namely, grounding and solving, sometimes yield a bottleneck which requires advanced modeling skills or even makes impossible to solve large-scale instances.

Altogether, taking into account strengths and weaknesses, ASP is a relatively young technology which has proven to be very useful and efficient to solve numerous challenging problems in several application domains. Furthermore, the fact that it is an emergent and very active area of research suggests that, in the years to come, its usage will become more popular in the field of systems biology.

The work presented in this thesis has raised several interesting questions for future research. In particular, our work have opened the way to an exhaustive characterization of feasible logical models for a given system. Now, we need to develop a proper modeling framework to interpret and take advantage of such a characterization. This must be necessarily driven by available experimental technology allowing us to either confirm or refute generated hypotheses. For instance, phospho-proteomics assays like the one used for learning in Chapter 3 are performed over a population of cells and thus, it is unclear how to interpret the multitude of logical networks and their input-output behaviors. Given the existence of several logical input-output behaviors gathering different internal mechanisms, we need to elucidate if such mechanisms are a mere artifact of logical networks, or if they actually represent molecular mechanisms which in turn appear more or less often within each cell or at a population scale. Furthermore, despite the intrinsic uncertainty in biological systems, it is still rather hard to assess the amount of noise in measurements and how this impacts on our mathematical or computational models. This raises the question of identifiability and to what extent new experiments are able to yield more refined logical models. Thus, the method for experimental design presented in Chapter 4 requires to be validated and could help to tackle this issue. Finally, we find particularly interesting to explore further the approach introduced in Chapter 5 for finding intervention strategies by reasoning over an ensemble of logical networks. Again, this is a key methodological contribution allowing systems biologists to draw insights under uncertainty and non-identifiability. Nonetheless, we need to elucidate whether such an ensemble of networks describes alternative pathways within a single cell or at the population scale. Overall, we look forward for experimental validation of our methods and findings.

We conclude this thesis by noting that, integrative modeling approaches considering multiple levels and time-scales of causation pose a very challenging goal in systems biology. Towards this end, we envision a hybrid modeling framework combining (non-deterministic) logic-based, stochastic, and continuous approaches. Notably, in order to achieve all these challenges, we believe that more sophisticated computational methods are needed in order to integrate qualitative and quantitative knowledge in a uniform and robust manner. In particular, hybrid reasoning systems leveraging the expressiveness of several technologies and modeling approaches appears as a very promising track for future research in computer science. In fact, very recent developments in the ASP systems used throughout this thesis allow for an interplay between declarative logic programming and imperative "traditional" programming. This opens innumerable possibilities to combine available technologies into a unified environment for problem solving. Hopefully, advances on this subject will foster the usage of knowledge representation and reasoning methodologies in systems biology towards a better understanding of life.

A Proofs

A.1 Data discretization schemes

Let (V, E , σ) be a PKN. Let ξ = ((C i , P C i )) i ∈N be an experimental dataset over (V, E , σ) with size N ξ . Let k ∈ N define the discretization scheme. Let us denote with µ and µ k , the corresponding minima for Θ r ss and Θ r ss k over the space of models M (V,E ,σ) with respect to ξ:

µ = min (V,φ)∈M (V,E ,σ) Θ r ss ((V, φ), ξ) µ k = min (V,φ)∈M (V,E ,σ) Θ r ss k ((V, φ), ξ).
Then 10 -2k µ k converges to µ when k increases, with an exponential speed:

µ k = 10 2k µ + O(10 k ).
Moreover, any Boolean logic model minimizing Θ r ss , also minimizes Θ r ss k within the following tolerance t k :

t k = 2 � N ξ µ k + N ξ µ k .
Proof. Let (V, φ) be any Boolean logic model having evidence in (V, E , σ). Let π 1 , . . . , π n be the n Boolean predictions of (V, φ) with each π i defined under C i . The difference Θ r ss and 10 -2k Θ r ss k over (V, φ) with respect to ξ is given by:

� � �[Θ r ss -10 -2k Θ r ss k ]((V, φ), ξ) � � � = � � � n � i =1 � v∈d om(P C i ) � P C i (v) -π i (v) � 2 - � δ k (P C i (v)) -π i (v) � 2 � � � For each triplet (P C i , π i , v) let γ i (v) = δ k (P C i (v))-π i (v) and λ i (v) = P C i (v)-δ k (P C i (v)). Hence: � � �[Θ r ss -10 -2k Θ r ss k ]((V, φ), ξ) � � � = � � � n � i =1 � v∈d om(P C i ) � γ i (v) + λ i (v) � 2 -γ i (v) 2 � � � = � � � n � i =1 � v∈d om(P C i ) λ i (v) � 2γ i (v) + λ i (v) � � � � Recall that N ξ = � n i =1 � � d om(P C i ) � � .
From the Cauchy-Schwarz inequality we have that

n � i =1 � v∈d om(P C i ) � � �γ i (v) � � �≤ � N ξ � � � � n � i =1 � v∈d om(P C i ) γ i (v) 2 = � N ξ
� 10 -2k Θ r ss k ((V, φ), ξ).

Notice that from the discretization scheme we have that λ i (v) < 10 -k for every (i , v). It follows that:

� � �[Θ r ss -10 -2k Θ r ss k ]((V, φ), ξ) � � � ≤ 10 -k   n � i =1 � v∈d om(P C i ) 2 � � �γ i (v) � � �+ n � i =1 � v∈d om(P C i ) � � �λ i (v) � � �   ≤ 10 -k � 2 � N ξ � 10 -2k Θ r ss k ((V, φ), ξ) + 10 -k N ξ � .
We deduce that

µ ≤ 10 -2k µ k + 10 -k � 2 � N ξ � 10 -2k µ k + 10 -k N ξ � (A.1) ≤ 10 -2k µ k � 1 + 2 × 10 -k � N ξ 10 -2k µ k + 10 -2k N ξ 10 -2k µ k � = 10 -2k µ k       1 + 2 � N ξ µ k + N ξ µ k � �� � =t k      
With a similar reasoning introducing γ � i (v) = P C i (v) -π i (v) instead of γ i (v), we have the following relation. � � �[Θ r ss -10 -2k Θ r ss k ]((V, φ), ξ)

� � � = � � � n � i =1 � v∈d om(ω i ) λ i (v) � 2γ � i (v) -λ i (v) � � � � ≤ 10 -k � 2 � N ξ � Θ r ss ((V, φ), ξ) + 10 -k N ξ � .
Therefore,

µ k ≤ 10 2k µ + 10 k � 2 � N ξ � µ + 10 -k N ξ � ≤ 10 2k µ + 10 k � 2 � N ξ � µ + N ξ � � �� � =B
Introducing this inequality in (A.1), we deduce that:

10 2k µ ≤ µ k + 10 k � 2 � N ξ � 10 -2k µ k + 10 -k N ξ � ≤ µ k + 10 k � 2 � N ξ � µ + 10 -k B + N ξ � ≤ µ k + 10 k     2 � N ξ � µ + B + N ξ � �� � =C    
Altogether, we have that there exists D = max{B,C }, which is independent from k, such that

� � �10 2k µ -µ k � � �≤ D10 k .
A.2 Correctness of ASP encodings where h (head) is an atom and any b j (body) is a literal of the form a or ∼ a for an atom a where the connective ∼ corresponds to default negation. Next, for a rule r , we denote its head h with head (r ) and its body {b 1 , . . . , b n } with bod y(r ). Furthermore, we denote the positive literals b j (of the form a) with bod y(r ) + and the negative literals b j (of the form ∼ a) with bod y(r ) -. A set X ⊆ A of ground atoms is a model of a propositional logic program Π, if head (r ) ∈ X whenever bod y(r ) + ⊆ X and bod y(r ) -∩ X = � for every r ∈ Π.

Next, let us recall the formal definition of answer sets. In ASP, the semantics is given by the stable models semantics [START_REF] Gelfond | The stable model semantics for logic programming[END_REF]. In fact, we view rules with first-order variables as schemes representing their sets of ground instances. To this end, the reduct, Π X , of logic program Π relative to a set X of atoms is defined by Π X = {(head (r ) ← bod y(r ) + )θ | r ∈ Π, (bod y(r ) -θ) ∩ X = �, θ : v ar (r ) → A } where v ar (r ) is the set of all variables that occur in a rule r and θ is a ground substitution for the variables in r . Then, X is an answer set of Π if and only if X is a ⊆-minimal model of Π X . Note that Π X is a positive logic program, i.e., for all rules r ∈ Π X it holds bod y(r ) -= �. In fact, in what follows we rely on an operational characterization for computing the stable model of Ω k+1 (V,φ| C ) (A f ) for some k ≥ 0. We consider the following set of atoms X . To start with, the set of atoms τ((V, φ),C ) is included in X . Also, the set of atoms {free(v, s φ(v) ) | v ∈ d om(φ) \ d om(C )} is included in X . Finally, the set {eval(v, 1) | F (v) = t } ∪ {eval(v, -1) | F (v) = f } is also included in X . We need to show that X is a ⊆-minimal model of Π X . We do so by inspecting each rule in Π X . First, we note that X includes all facts in τ((V, φ),C ). Each of these facts belongs also to Π X . Thus, any set Y of atoms excluding at least one of them, cannot be a model of Π X . Next, consider the first rule in Π A. 3 . Notably, all its grounded instantiations belong to Π X . Furthermore, clamped(v, s) ∈ X only if v ∈ d om(C ), and either s = 1 and C (v) = t , or s = -1 and

C (v) = f . Notably, if C (v) = t then F (v) = t , whereas if C (v) = f then F (v) = f
. Therefore, all grounded instantiations of the first rule are satisfied by X , and any set excluding from X at least one atom of the form eval(v, s) with v ∈ d om(C ) and s ∈ {1, -1} cannot be a model of Π X . Next, consider the second rule in Π A. 3 . Its grounded instances belong to Π X only if clamped(v, s) ∉ X with v ∈ d om(φ), s ∈ {1, -1}. Since free (v, s φ(v) ) ∈ X for all v ∈ d om(φ) \ d om(C ), all such rules are satisfied by X , and any set excluding from X at least one atom over predicate free/2 cannot be a model of Π X . Now, let us consider the third rule in Π A. 3 . Note that all its grounded instantiations belong to Π X . Furthermore, if v ∈ d om(φ) \ d om(C ) then, F (v) = t iff there exists ψ ∈ φ(v) such that F (ψ) = t . Then, F (w) = t for all w ∈ ψ ∩ V , and F (w) = f for all ¬w ∈ ψ. Hence, the set of atoms {free(v, s φ(v) ), dnf(s φ(v) , s ψ )} ∪{clause(s ψ , w, 1), eval(w, 1) | w ∈ ψ ∩ V } ∪ {clause(s ψ , w, -1), eval(w, -1) | ¬w ∈ ψ} is included in X . Therefore, all grounded instantiations of the third rule are satisfied by X , and any set excluding from X at least one atom of the form eval(v, 1) with v ∈ d om(φ) \ d om(C ) cannot be a model of Π X . Finally, for the fourth rule only ground instantiations such eval(v, 1) ∉ X with v ∈ V are included, which implies F (v) = f . Furthermore, if v ∈ V \ d om(C ) we have two cases. If v ∉ d om(φ), all grounded instantiations of the fourth rule are satisfied by X , and any set excluding from X at least one atom of the form eval(v, -1) cannot be a model of Π X . If v ∈ d om(φ) \ d om(C ) then, F (v) = f iff for all ψ ∈ φ(v) there exists w such that, either F (w) = f with w ∈ ψ ∩ V , or F (w) = t with ¬w ∈ ψ. Hence, the set X includes either {free(v, s φ(v) ), dnf(s φ(v) , s ψ ), clause(s ψ , w, 1), eval(w, -1)} or {free(v, s φ(v) ), dnf(s φ(v) , s ψ ), clause(s ψ , w, -1), eval(w, 1)} .

Therefore, any set excluding from X at least one atom over the predicate eval/2 cannot be a model of Π X .

Hence, we have investigated all rules in Π and shown that their ground instances in Π X are satisfied by X . Moreover, we have checked that any set excluding from X at least one atom is not a model of Π X . Hence, X is a ⊆-minimal model of Π X and thus an answer set of Π.

Soundness. Let X be an answer set of Π = τ((V, φ),C ) ∪ Π A.3 . Let us briefly describe the reduct Π X . Notably, the set of facts τ((V, φ),C ) is included, i.e., τ((V, φ),C ) ⊆ Π X . Ground instances of first and third rules in Π A.3 are also included since they are positive. For the second rule, only ground instantiations such clamped(v, s) ∉ X with v ∈ d om(φ), s ∈ {1, -1} are included.

Similarly, for the fourth rule only ground instantiations such eval(v, 1) ∉ X with v ∈ V are included. Next, by definition, we know that X is a ⊆-minimal model of Π X . Furthermore,

C n(Π X ) = � i ≥0 T i Π X � = X .
In what what follows, let

F � = Ω k (V,φ| C ) (A f ) = Ω k+1 (V,φ| C ) (A f ) for some k ≥ 0.
Next, for all v ∈ V and j ≥ 2 we show by induction that if eval(v, s) ∈ T j Π X � then, either s = 1 and F � (v) = t , or s = -1 and F � (v) = f . Note that T 0 Π X � = � and T 1 Π X � = τ((V, φ),C ).

Case ( j = 2). By definition, T 2 Π X � = T Π X T 1 Π X � = T Π X τ((V, φ),C ). Then, it is easy to see that eval(v, 1) ∈ T 2 Π X � iff clamped(v, 1) ∈ τ((V, φ),C ). Furthermore, clamped(v, 1) ∈ τ((V, φ),C ) also implies v ∈ d om(C ) and C (v) = t . Also, we can see that eval(v, -1) ∈ T 2 Π X � iff either clamped(v, -1) ∈ τ((V, φ),C ), or variable(v) ∈ τ((V, φ),C ) and eval(v, 1) ∉ X . Moreover, in this case clamped(v, -1) ∈ τ((V, φ),C ) also implies v ∈ d om(C ) and C (v) = f . Next, if we assume eval(v, 1) ∈ T 2 Π X �, then we have φ| C (v) = �. Therefore, Ω k (V,φ| C ) (A f )(v) = t for all k ≥ 1. If we assume eval(v, -1) ∈ T 2 Π X �, then we have either φ|

C (v) = ⊥, or v ∈ V \ d om(C ). If φ| C (v) = ⊥, or v ∉ d om(φ| C ) it is easy to see that Ω k (V,φ| C ) (A f )(v) = f for all k ≥ 1.
For the remaining case, i.e, v ∈ d om(φ) \ d om(C ), we provide a rather informal argument due to the fact that Ω (V,φ| C ) is non-monotonic over two-valued assignments. Thus, it is hard (and does not worth) to write a precise constructive proof for finding the iterative step for which v reaches its fixpoint in Ω (V,φ| C ) starting from A f . However, since there are no feedback-loops in (V, φ), we know that all variables must reach their fixpoint at some iterative step. Moreover, since eval(v, 1) ∉ X , there must be a set of atoms S ⊆ X such that the body of all instantiations with respect to v of the third rule in Π 2 are false. Furthermore, provided that there are no feedbackloops in (V, φ), the derivation of all atoms in S must be independent from the atom eval(v, -1).

Then, it is safe to assume that if eval(w, s) ∈ S, then either s = 1 and F � (w) = t , or s = -1 and F � (w) = f . Notably, the difficulty to conclude this more precisely is due to the fact that there may exist eval(w, 1) ∈ S such that eval(w, 1) ∉ T 2 Π X �, i.e. eval(w, 1) is a consequence in a later iterative step. Again, due to the absence of feedback-loops which ensures the independence of S from eval(v, -1), we can capture such atoms in the inductive case below. Finally, it is easy to see that for all ψ ∈ φ(v) we have F � (ψ) = f and thus, F � (v) = f . Case ( j > 2). By definition, T j +1 Π X � = T Π X T j Π X �. Thus, if eval(v, s) ∈ T j +1 Π X �, either eval(v, s) ∈ T j Π X �, or eval(v, s) is a consequence of T j Π X � by applying rules in Π X . If eval(v, s) ∈ T j Π X �, by inductive hypothesis we have, either s = 1 and F � (v) = t , or s = -1 and F � (v) = f . Otherwise, we only need to consider s = 1 since for all j ≥ 2 it cannot be the case that eval(v, -1) ∈ T j +1 Π X � if grounded instantiations of the first rule are satisfied by X , and any set excluding from X at least one atom of the form eval(v, s) with v ∈ d om(C ) and s ∈ {1, -1} cannot be a model of Π X . Next, consider the second rule in Π A. 4 . Its grounded instances belong to Π X only if clamped(v, s) ∉ X with v ∈ d om(φ), s ∈ {1, -1}. Since free (v, s φ(v) ) ∈ X for all v ∈ d om(φ) \ d om(C ), all such rules are satisfied by X , and any set excluding from X at least one atom over predicate free/2 cannot be a model of Π X . Next, consider the third rule in Π A. 4 . Notably, all its grounded instantiations belong to Π X . Recall that eval_clause(s ψ , -1) ∈ X only if v ∈ d om(φ) and F (v) = f for all ψ ∈ φ(v). But, F (v) = f iff for all ψ ∈ φ(v) there exists w such that, either F (w) = f with w ∈ ψ ∩ V , or F (w) = t with ¬w ∈ ψ. Hence, the set X includes either {clause(s ψ , w, 1), eval(w, -1)} or {clause(s ψ , w, -1), eval(w, 1)} .

Therefore, any set excluding from X at least one atom over the predicate eval_clause/2 cannot be a model of Π X . Now, let us consider the fourth rule in Π A. 4 . Note that all its grounded instantiations belong to Π X . Furthermore, if v ∈ d om(φ) \ d om(C ) then, F (v) = t iff there exists ψ ∈ φ(v) such that F (ψ) = t . Then, F (w) = t for all w ∈ ψ ∩ V , and F (w) = f for all ¬w ∈ ψ. Hence, the set of atoms {free(v, s φ(v) ), dnf(s φ(v) , s ψ )} ∪{clause(s ψ , w, 1), eval(w, 1) | w ∈ ψ ∩ V } ∪ {clause(s ψ , w, -1), eval(w, -1) | ¬w ∈ ψ} is included in X . Therefore, all grounded instantiations of the fourth rule are satisfied by X , and any set excluding from X at least one atom of the form eval(v, 1) with v ∈ d om(φ)\d om(C ) cannot be a model of Π X . Finally, for the fifth rule all grounded instantiations belong to Π X . If is included in X . Therefore, all grounded instantiations of the fifth rule are satisfied by X , and any set excluding from X at least one atom of the form eval(v, -1) with v ∈ d om(φ) \ d om(C ) cannot be a model of Π X .

Hence, we have investigated all rules in Π and shown that their ground instances in Π X are satisfied by X . Moreover, we have checked that any set excluding from X at least one atom is not a model of Π X . Hence, X is a ⊆-minimal model of Π X and thus an answer set of Π.

Soundness. Let X be an answer set of Π = τ((V, φ),C ) ∪ Π A.4 . Let us briefly describe the reduct Π X . Notably, the set of facts τ((V, φ),C ) is included, i.e., τ((V, φ),C ) ⊆ Π X . Ground instances of all rules in Π A.4 except the second one are also included since they are positive. For the second rule, only ground instantiations such clamped(v, s) ∉ X with v ∈ d om(φ), s ∈ {1, -1} are included. Next, by definition, we know that X is a ⊆-minimal model of Π X . Furthermore,

C n(Π X ) = � i ≥0 T i Π X � = X .
Next, for all v ∈ V and j ≥ 2 we show by induction that if eval(v, s) ∈ T j Π X � then, either s = 1 and Ω j -1 (V,φ| C ) (A u )(v) = t , or s = -1 and Ω j -1 (V,φ| C ) (A u )(v) = f . Otherwise, Ω j -1 (V,φ| C ) (A u )(v) = u. Note that T 0 Π X � = � and T 1 Π X � = τ((V, φ),C ).

Case ( j = 2). By definition, T 2 Π X � = T Π X T 1 Π X � = T Π X τ((V, φ),C ). Then, it is easy to see that eval(v, 1) ∈ T 2 Π X � iff clamped(v, 1) ∈ τ((V, φ),C ). Furthermore, clamped(v, 1) ∈ τ((V, φ),C ) also implies v ∈ d om(C ) and C (v) = t . Also, we can see that eval(v, -1) ∈ T 2 Π X � iff clamped(v, -1) ∈ τ((V, φ),C ) Moreover, in this case clamped(v, -1) ∈ τ((V, φ),C ) also implies v ∈ d om(C ) and

C (v) = f .
Next, if we assume eval(v, 1) ∈ T 2 Π X �, then we have φ| C (v) = �. Therefore, it is easy to see that Ω 1 (V,φ| C ) (A u )(v) = t . If we assume eval(v, -1) ∈ T 2 Π X �, then we have φ| C (v) = ⊥. Therefore, again it is easy to see that Ω 1 (V,φ| C ) (A u )(v) = f . Notably, if clamped(v, s) ∉ τ((V, φ),C ) for neither s = 1 nor s = -1, we have v ∉ d om(C ). Therefore, we can see that Ω 1 (V,φ| C ) (A u )(v) = u.

Case ( j > 2). By definition, T j +1

Π X � = T Π X T j Π X �. Thus, if eval(v, s) ∈ T j +1
Π X �, either eval(v, s) ∈ T j Π X �, or eval(v, s) is a consequence of T j Π X � by applying rules in Π X . If eval(v, s) ∈ T j Π X �, by inductive hypothesis and monotonicity of Ω (V,φ| C ) over three-valued logics we have, either s = 1 and Ω j -1 Next, by inductive hypothesis we have Ω j -1 (V,φ| C ) (A u )(w) = t for all w ∈ ψ∩V , and Ω j -1 (V,φ| C ) (A u )(w) = f for all ¬w ∈ ψ. Then, we also have Ω j -1 (V,φ| C ) (A u )(ψ) = t . Therefore, provided that φ| C (v) is in disjunctive normal form, we have

(V,φ| C ) (A u )(v) = Ω j (V,φ| C ) (A u )(v) = t , or s = -1 and Ω j -1 (V,φ| C ) (A u )(v) = Ω j (V,φ| C ) (A u )(v) = f . Otherwise, free(v, s φ(v) ) ∈ T j Π X �
Ω j (V,φ| C ) (A u )(φ| C (v)) = Ω j (V,φ| C ) (A u )(v) = t .
If s = -1, for all ψ ∈ φ(v) we must have eval_clause(s ψ , -1) ∈ T j Π X �. Hence, we also have that there exists w such that, either {clause(s ψ , w, 1), eval(w, -1)} ⊆ T j Π X � ⊆ X with w ∈ ψ ∩ V , or {clause(s ψ , w, -1), eval(w, 1)} ⊆ T j Π X � ⊆ X with ¬w ∈ ψ. Next, by inductive hypothesis we have Ω j -1 (V,φ| C ) (A u )(w) = f for all w ∈ ψ ∩ V , and Ω j -1 (V,φ| C ) (A u )(w) = t for all ¬w ∈ ψ. Then, we also have Ω j -1 (V,φ| C ) (A u )(ψ) = f . Therefore, provided that φ| C (v) is in disjunctive normal form, we have

Ω j (V,φ| C ) (A u )(φ| C (v)) = Ω j (V,φ| C ) (A u )(v) = f .
Finally, if eval(v, s) ∉ T j +1 Π X � with s ∈ {1, -1}, by inductive hypothesis and monotonicity of Ω (V,φ| C ) over three-valued logics we have Ω j -1 (V,φ| C ) (A u )(v) = u. Furthermore, since eval(v, s) is neither a consequence of T j Π X � by applying rules in Π X , based on the previous cases we can see Proof. The proof follows from the Proposition 2.2.1. First, we note that rules 1-3 in Π 3.5 generate the representation of all clamping assignments C i ∈ C . Next, it is easy to extend Proposition 2.2.1 to consider several logical networks, in this only two. More precisely, we have that for each C i ∈ C there is an answer set X of Π = τ((V, φ j ), (V, φ j � )) ∪ Π 3.5 such that F j i = {v � → t | eval( j , v, 1) ∈ X }∪{v � → f | eval( j , v, -1) ∈ X } if and only if F j i is the unique fixpoint of Ω (V,φ j | C i ) reachable from A f , and the same holds with j � instead of j . Therefore, it follows that X is an answer set of Π (in particular, the atom diff is included) iff there exists v ∈ V R such that

F j i (v) � = F j � i (v).

Experimental design

Let B be a finite set of input-output behaviors represented by Boolean logic models ((V, φ j )) j ∈J . Let ε, s, and k be three positive integers with s ≤ |V S | and k ≤ |V K |. Then, there is an answer set X of τ(B, s, k)∪Π 4.2 such that Proof. The proof follows from the Proposition 2.

C i = {v � → t | v ∈ V S , clamped(i , v, 1) ∈ X } ∪ {v � → f | v ∈ V K , clamped(i , v, -
) ∈ C 1 (s, k) × • • • × C ε (s, k)
there is an answer set X of τ(B, s, k) ∪ Π � such that F j i = {v � → t | eval(i , j , v, 1) ∈ X } ∪ {v � → f | eval(i , j , v, -1) ∈ X } if and only if F j i is the unique fixpoint of Ω (V,φ j | C i ) reachable from A f . Also, one can verify that considering the complete set of rules in Π 4.2 , such an answer set X exists iff ε is the least integer such that for all pairs of networks (V, φ j ), (V, φ j � ) with j < j � , there are i ∈ {1, . . . , ε}, v ∈ V R such that � diff(i , j , j � , v), diff(i , j , j � ) � ⊆ X . Therefore, the first condition above is satisfied, whereas the three optimization statements in rules 23-25 enforce the desired optimality criteria in the second condition.

Minimal intervention strategies

Let (V, φ i ) i ∈N be a finite family of logical networks. Let (G j ,C j ) j ∈J be a finite family of intervention scenarios and k some positive integer. Then, there is an answer set X of τ((V, φ i ) i ∈N , (G j ,C j ) j ∈J , k) ∪ Π 5.2 such that I = {v � → t | intervention(v, 1) ∈ X } ∪ {v � → f | intervention(v, -1) ∈ X } if and only if I is a bounded intervention strategy for (G j ,C j ) j ∈J wrt (V, φ i ) i ∈N and k. Abstract: Deciphering the functioning of biological networks is one of the central tasks in systems biology. In particular, signal transduction networks are crucial for the understanding of the cellular response to external and internal perturbations. Importantly, in order to cope with the complexity of these networks, mathematical and computational modeling is required.

We propose a computational modeling framework in order to achieve more robust discoveries in the context of logical signaling networks. More precisely, we focus on modeling the response of logical signaling networks by means of automated reasoning using Answer Set Programming (ASP). ASP provides a declarative language for modeling various knowledge representation and reasoning problems. Moreover, available ASP solvers provide several reasoning modes for assessing the multitude of answer sets. Therefore, leveraging its rich modeling language and its highly efficient solving capacities, we use ASP to address three challenging problems in the context of logical signaling networks: learning of (Boolean) logical networks, experimental design, and identification of intervention strategies. Overall, the contribution of this thesis is three-fold. Firstly, we introduce a mathematical framework for characterizing and reasoning on the response of logical signaling networks. Secondly, we contribute to a growing list of successful applications of ASP in systems biology. Thirdly, we present a software providing a complete pipeline for automated reasoning on the response of logical signaling networks.

Key words: systems biology, logical signaling networks, answer set programming Résumé : Décrypter le fonctionnement des réseaux biologiques est une des missions centrales de la biologie des systèmes. En particulier, les réseaux de transduction du signal sont essentiels pour la compréhension de la réponse cellulaire à des perturbations externes ou internes.

Pour faire face à la complexité de ces réseaux, des modélisations aussi bien numériques que formelles sont nécessaires. Nous proposons un cadre de modélisation formelle, dans le cadre de réseaux logiques, afin d'obtenir des prédictions robustes sur le comportement et le contrôle des voies de signalisation. Nous modélisons la réponse des réseaux logiques de signalisation par du raisonnement automatique à l'aide de Programmation par Ensembles-Réponses (Answer Set Programming, ASP). ASP fournit un langage déclaratif pour la modélisation de divers problèmes de représentation des connaissances et de raisonnement. Des solveurs permettent plusieurs modes de raisonnement pour étudier la multitude d'ensembles réponses. En s'appuyant sur la richesse du langage de modélisation et ses capacités de résolution très efficaces, nous utilisons ASP pour modéliser et résoudre trois problèmes dans le contexte des réseaux logiques de signalisation : apprentissage de réseaux booléens, calculs de plan d'expériences, et identification des contrôleurs. Globalement, la contribution de cette thèse est de trois ordres. Premièrement, nous introduisons un cadre formel pour la caractérisation et le raisonnement sur la réponse des réseaux logiques de signalisation. Deuxièmement, nous contribuons à une liste croissante d'applications réussies d'ASP en biologie des systèmes. Troisièmement, nous présentons un logiciel fournissant un pipeline complet de raisonnement automatisé sur la réponse des réseaux logiques de signalisation.

Mots clefs : biologie des systèmes, réseaux de signalisation logiques, answer set programming

  Mots clefs : biologie des systèmes, réseaux de signalisation logiques, answer set programming xvi Introduction 1 1.1 Systems biology and signaling networks . . . . . . . . . . . . . . . . . . . . . . . . 1 1.2 Computational modeling and methods . . . . . . . . . . . . . . . . . . . . . . . . 3 1.3 Original contribution . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10 1.4 Organization of the thesis . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10 Generic framework for reasoning on the response of logical networks 13 2.1 Preliminaries . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13 2.1.1 Propositional logic and mathematical notation . . . . . . . . . . . . . . . 13 2.2 Characterizing the response of logical networks . . . . . . . . . . . . . . . . .

4. 3 .

 3 1 Instance . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4.3.2 Encoding . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4.3.3 Solving . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4.4 Empirical evaluation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4.4.1 Real-world problem instance . . . . . . . . . . . . . . . . . . . . . . . . . . 4.4.2 Optimal experimental designs . . . . . . . . . . . . . . . . . . . . . . . . . 4.4.3 Analyzing experimental designs . . . . . . . . . . . . . . . . . . . . . . . . 4.5 Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5 Minimal intervention strategies 5.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5.2 Problem . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

  right) first according to their MSE (colors), and then according to the number of models they gather (bars). The 2 most common behaviors describe the response of 1062 and 880 Boolean logic models having MSEs 0.0542 and 0.0519 respectively. . . . . . . . . . 42 3.5 Core predictions versus number of input-output behaviors for each tolerance. . . . . . 43

4 . 2 2 �

 422 g � → e ∧ ¬c}. . . . . . . . . . . . . . . . . . . . . . . . 48 xxi Optimal experimental design to discriminate between 91 input-output behaviors. (a) Description of each experimental condition. Black squares indicate the presence of the corresponding stimulus (green header) or inhibitor (red header). (b) Each column describes the number of pairs of behaviors (out of � 91 = 4095) discriminated by each experimental condition. (c) Number of pairwise differences by readouts with each experimental condition. (d) Overall pairwise differences with each experimental condition. . . . . . . . . . . . . . . . . . . . .

  . . . . . . . . . . . . . . . . . . 5.2 Frequency of single interventions. Vertical bars describe the frequency of each single intervention among all minimal intervention strategies with respect to different sets of logical networks. All interventions occur in less than 50% of the strategies yet, some interventions are clearly more frequent than others. Pairs of families M 16 and M 144 (blue bars), M 2150 and M 2306 (red bars), and M 3524 and

  (a) Toy prior knowledge network (pkn.dot). (b) Logical networks (V, φ i ) as (signed) directed hypergraphs (network-i .dot). (c) Union of all logical networks where the thickness of hyperedges correspond to their frequencies (networks-union.dot). (d) All inclusion-minimal intervention strategies (strategies.dot). . . . . . . . . . . . . . . . . . . . . . . . . . . . 90 xxiii List of Tables

  φ(c) = b ∨ e, we need to verify the existence of the hyperedges (S b , c) with S b = {(b, 1)} and (S e , c) with S e = {(e, 1)}.

  graph underlying the logical network in (a). Directed edges describe causal interactions.

Figure 2 . 1 :

 21 Figure 2.1: Graphical representation for logical networks and interaction graphs. Vertices represent biological entities and the interactions among them are represented as follows. Positive interactions are represented by an arrow (→) whereas negative interactions are represented by a T-shape (�).

  Figure 3.1. Consider the PKN (V, E , σ) defined in Figure 3.1a. From the graph coloring, we have V S = {a, b, c}, V K = {d } An arbitrary Boolean logic model (V, φ) derived from the PKN in (a), i.e. pruning the hypergraph in (b). Logical interactions in (V, φ) correspond to the mapping φ = {d � → a; e � → b∨c; f � → d ∧e; g � → e ∧¬c}.

Figure 3 .

 3 Figure 3.1: Learning Boolean logic models of immediate-early response. The green and red edges

Listing 3 . 4 :

 34 Enumeration of all (nearly) optimal Boolean logic models $ gringo toy . lp learning . lp -c maxrss =96 -c maxsize =10 | \ clasp --opt -mode = ignore -n0 -

  1: function BEHAVIORS(M : set of Boolean logic models)

Figure 3 . 2 :

 32 Figure 3.2: Prior knowledge network (V, E , σ) describing signaling pathways in human liver cells. It contains 31 nodes (V ) describing biological species: 7 stimuli (V S ), 7 inhibitors (V K ), 15 readouts (V R ) and 6 neither controlled nor observed (V U ). Furthermore, 53 signed directed edges (E ) describing activatory and inhibitory causal interactions yield 130 possible (signed) directed hyperedges.

Listing 3 . 6 :

 36 Learning all optimal Boolean logic models $ gringo extliver . lp learning . lp |\ clasp --conf = jumpy --opt -strategy =4 --opt -mode = optN -

Figure 3 . 3 :

 33 Figure 3.3: Distribution of Boolean logic models found for each tolerance according to their MSEs (Θ mse ). When 10% of tolerance is considered, two MSEs, viz. 0.0519 and 0.0542, gather 63% of the 5306 Boolean logic models.

Figure 3 . 4 :

 34 Figure 3.4: Logical input-output behaviors for 10% of tolerance. Behaviors are ordered (from left to right) first according to their MSE (colors), and then according to the number of models they gather (bars). The 2 most common behaviors describe the response of 1062 and 880 Boolean logic models having MSEs 0.0542 and 0.0519 respectively.

Figure 3 . 5 :

 35 Figure 3.5: Core predictions versus number of input-output behaviors for each tolerance.

Proposition 4 .

 4 3.1. Let B be a finite set of input-output behaviors represented by Boolean logic models ((V, φ j )) j ∈J . Let ε, s, and k be three positive integers with s ≤ |V S | and k ≤ |V K |. Then, there is an answer set

Listing 4 . 3 :

 43 Finding an optimum experimental design $ clingo design . lp toy . lp --quiet =1 clingo version 4.3.1 Reading from design . lp ... Solving ... Solving ... Answer : 1

Figure 4 . 2 : 2 �

 422 Figure 4.2: Optimal experimental design to discriminate between 91 input-output behaviors. (a) Description of each experimental condition. Black squares indicate the presence of the corresponding stimulus (green header) or inhibitor (red header). (b) Each column describes the number of pairs of behaviors (out of � 91 2 � = 4095) discriminated by each experimental condition. (c) Number of pairwise differences by readouts with each experimental condition. (d) Overall pairwise differences with each experimental condition.

Listing 5 . 4 :

 54 Enumeration of all minimal intervention strategies wrt 2306 logical networks $ clingo control . lp networks -2306. lp -n0 --quiet \ --dom -pref =32 --dom -mod =6 --heu = domain clingo version In Listing 5.4 we show the solving for the unbounded problem instance networks-2306.lp.

Figure 5 . 2 :

 52 Figure 5.2: Frequency of single interventions. Vertical bars describe the frequency of each single intervention among all minimal intervention strategies with respect to different sets of logical networks. All interventions occur in less than 50% of the strategies yet, some interventions are clearly more frequent than others. Pairs of families M 16 and M 144 (blue bars), M 2150 and M 2306 (red bars), and M 3524 and M 5306 (green bars), have the same strategies and thus we plot them together.

Figure 6 . 2 :

 62 Figure 6.2: High-level software design. Modules of caspo are divided into three different layers. First layer comprises the console module which implements functionalities related to the usage of caspo from the command-line. Entry-points for caspo subcommands are implemented here. Second layer comprises various modules which implement different sections of the pipeline for automated reasoning, namely, learn for learning Boolean logic models (Chapter 3), design for designing new experiments (Chapter 4), control for finding intervention strategies (Chapter 5), analyze for identifying input-output behaviors (Chapter 3), and visualize for basic visualization features. Third layer comprises the core module which implements "low-level" functionalities for the whole software. Main external dependecies are shown as well.

Listing 6 . 2 :

 62 Help message for learn subcommand $ caspo learn --help usage : caspo learn [ -h ] [ --clingo C ] [ --fit F ] [ --size S ] [ --factor D T discretization function : round , floor , ce il ( Default to round )

  For example, if the PKN contains edges a → c and b � c, then the header will have columns a = c, !b = c, and a+!b = c. Next, each row in the file describes a different logical network by specifying which hyperedges are present, and which ones are absent. Hence, let (V, φ 1 ) and (V, φ 2 ) be two logical networks with φ 1 (c) = a ∨ ¬b and φ 2 (c) = a ∧ ¬b. Such logical networks are described in networks.csv as: a = c, !b = c, a+!b = c, representation of logical networks is relatively simple and very easy to share with third-party software. In fact, some of the following subcommands use this kind of file format as an input. Listing 6.3: Running learn subcommand $ caspo learn pkn . sif dataset . csv 10 --fit 0.1 --size 5 Running caspo learn ... Wrote out / networks . csv

Listing 6 . 4 :

 64 Help message for analyze subcommand $ caspo analyze --help usage : caspo analyze [ -h ] [ --clingo C ] [ --networks N ] [ --midas M T ] [ --strategies S ] optional arguments : -h , --help show this help message an d exit --clingo C clingo solver binary ( Default to ' clingo ') --networks N logical networks in CSV format --midas M T experimental dataset in MIDAS file and time -point --strategies S intervention stratgies in CSV format Next, in Listing 6.5 we show the execution of the analyze subcommand for our toy example. Let us briefly describe the output files from this subcommand.

  show this help message and exit --clingo C clingo solver binary ( De fault to ' clingo ') --stimuli S maximum number of stimuli per experiment --inhibitors I maximum number of inhibitors per e xperiment --experiments E maximum number of experiments ( Default to 20)

Figure 6 . 4 :

 64 Figure 6.4: Visualization provided by caspo. (a) Toy prior knowledge network (pkn.dot). (b) Logical networks (V, φ i ) as (signed) directed hypergraphs (network-i .dot). (c) Union of all logical networks where the thickness of hyperedges correspond to their frequencies (networks-union.dot). (d) All inclusion-minimal intervention strategies (strategies.dot).

First, let us

  introduce standard mathematical notation for dealing with logic programs. A propositional logic program over a set A of ground atoms is a finite set of rules of the form h ← b 1 , . . . , b n .

v

  ∈ d om(φ) \ d om(C ) and F (v) = f , then the set of atoms {free(v, s φ(v) )} ∪ {eval_clause(s ψ , -1), dnf(s φ(v) , s ψ ) | ψ ∈ φ(v)}

  and thus, v ∈ d om(φ) \ d om(C ). If s = 1, there must exist ψ ∈ φ(v) such that Y ⊆ T j Π X � with Y = {free(v, s φ(v) ), dnf(s φ(v) , s ψ )}∪{clause(s ψ , w, 1), eval(w, 1) | w ∈ ψ ∩ V } ∪ {clause(s ψ , w, -1), eval(w, -1) | ¬w ∈ ψ} .

  1) ∈ X } with i = 1, . . . , ε if and only if, 1. ε is the least number of clamping assignments for which (4.1) holds,2. and (C 1 , . . . ,C ε ) ∈ arg min (C 1 ,...,C ε )∈Δ � Θ V S ((C 1 , . . . ,C ε )) , Θ V K ((C 1 , . . . ,C ε )) � with Δ = arg max (C 1 ,...,C ε )∈C ε (s,k) � Θ diff (B, (C 1 , . . . ,C ε )) � and C ε (s, k) the set of all ε-tuples (C 1 , . . . ,C ε ) ∈ C 1 (s, k) × • • • × C ε (s, k) satisfying (4.1).

  Logical networks and their response with Answer Set Programming . . . 18 2.3 Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 20 Learning Boolean logic models of immediate-early response 21 3.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 21 3.2 Problem . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 23 3.2.1 Prior knowledge network and phospho-proteomics dataset . . . . . . . . 23 3.2.2 Boolean input-output predictions . . . . . . . . . . . . . . . . . . . . . . . 25 3.2.3 Learning Boolean logic models . . . . . . . . . . . . . . . . . . . . . . . . . 26 3.3 Learning Boolean logic models with Answer Set Programming . . . . . . . . . . 29 3.3.1 Instance . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 30 3.3.2 Encoding . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 31 3.3.3 Solving . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 34 3.4 Finding input-output behaviors with Answer Set Programming . . . . . . . . . . 35 Encoding . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .3.4.3 Solving . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3.5 Empirical evaluation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3.5.1 Real-world problem instance . . . . . . . . . . . . . . . . . . . . . . . . . . 3.5.2 Optimal Boolean logic models. . . . . . . . . . . . . . . . . . . . . . . . . . 3.5.3 Enumeration of (nearly) optimal Boolean logic models. . . . . . . . . . . 3.5.4 Analyzing logical input-output behaviors. . . . . . . . . . . . . . . . . . . 3.5.5 Comparing with a meta-heuristic approach. . . . . . . . . . . . . . . . . . 3.6 Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4 Experimental design for discrimination of input-output behaviors 4.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

. . 14 2.2.1 Logical networks and interaction graphs . . . . . . . . . . . . . . . . . . . 14 2.2.2 Characterizing the response of the system . . . . . . . . . . . . . . . . . . 15 2.2.3 3.4.1 Instance . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 35 xvii Contents 3.4.2 4.2 Problem . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4.2.1 Logical input-output behaviors and search space of experiments . . . . 4.2.2 Experimental design . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4.3 Experimental design with Answer Set Programming . . . . . . . . . . . . . . . .

  Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6.2 Software design . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6.2.1 High-level software design . . . . . . . . . . . . . . . . . . . . . . . . . . . 6.2.2 Generic workflow for subcommands . . . . . . . . . . . . . . . . . . . . . 6.3 Usage . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6.3.1 Usage for end-users . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6.3.2 Usage for developers . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6.4 Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Contribution . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7.2 Discussion and prospective . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

	Contents
	6 Software toolbox: caspo
	6.1 7 Conclusion and prospective List of Figures
	2.1 Graphical representation for logical networks and interaction graphs. Vertices represent 7.1 Bibliography biological entities and the interactions among them are represented as follows. Pos-
	Curriculum Vitae
	xviii	xix

5.2.1 Intervention scenarios and strategies . . . . . . . . . . . . . . . . . . . . . 5.2.2 Enumeration of minimal (bounded) intervention strategies . . . . . . . . 5.3 Minimal intervention strategies with Answer Set Programming . . . . . . . . . . 5.3.1 Instance . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5.3.2 Encoding . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5.3.3 Solving . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5.4 Empirical evaluation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5.4.1 Real-world problem instance . . . . . . . . . . . . . . . . . . . . . . . . . . 5.4.2 Minimal intervention strategies . . . . . . . . . . . . . . . . . . . . . . . . 5.4.3 Towards small yet robust intervention strategies . . . . . . . . . . . . . . 5.4.4 Comparing with a dedicated algorithm . . . . . . . . . . . . . . . . . . . . 5.5 Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

A Proofs

A.1 Data discretization schemes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . A.2 Correctness of ASP encodings . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . A.2.1 Basic ASP representation . . . . . . . . . . . . . . . . . . . . . . . . . . . . A.2.2 Extended ASP representations . . . . . . . . . . . . . . . . . . . . . . . . . itive interactions are represented by an arrow (→) whereas negative interactions are represented by a T-shape (�). . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15 3.1 Learning Boolean logic models of immediate-early response. The green and red edges correspond to activations and inhibitions, respectively. Green nodes represent ligands that can be experimentally stimulated (V S ). Red nodes represent species that can be inhibited or knocked out (V K ). Blue nodes represent species that can be measured (V R ). White nodes are neither measured, nor manipulated (V U ). . . . . . . . . . . . . . . . . 24 3.2 Prior knowledge network (V, E , σ) describing signaling pathways in human liver cells. It contains 31 nodes (V ) describing biological species: 7 stimuli (V S ), 7 inhibitors (V K ), 15 readouts (V R ) and 6 neither controlled nor observed (V U ). Furthermore, 53 signed directed edges (E ) describing activatory and inhibitory causal interactions yield 130 possible (signed) directed hyperedges. . . . . . . . . . . . . . . . . . . . . . . . . . . 38 3.3 Distribution of Boolean logic models found for each tolerance according to their MSEs (Θ mse ). When 10% of tolerance is considered, two MSEs, viz. 0.0519 and 0.0542, gather 63% of the 5306 Boolean logic models. . . . . . . . . . . . . . . . . . . . . . . . . . . 41 3.4 Logical input-output behaviors for 10% of tolerance. Behaviors are ordered (from left to

  6.1 Pipeline for reasoning on the response of logical signaling networks using caspo.At first, all (nearly) optimal Boolean logic models are learned by confronting prior knowledge on causal interactions with a phosphorylation dataset. Then, supported by insights from experts and various validation methods, we can decide if the ensemble of Boolean models needs further refinements. In such a case, optimal experiments can be designed in order to discriminate the set of behaviors at hand. By combining the previous dataset with the new observations, the learning is performed again yielding a new ensemble of models. After several High-level software design. Modules of caspo are divided into three different layers. First layer comprises the console module which implements functionalities related to the usage of caspo from the command-line. Entry-points for caspo subcommands are implemented here. Second layer comprises various modules which implement different sections of the pipeline for automated reasoning, namely, learn for learning Boolean logic models (Chapter 3), design for designing new experiments (Chapter 4), control for finding intervention strategies (Chapter 5), analyze for identifying input-output behaviors (Chapter 3), and visualize for basic visualization features. Third layer comprises the core module which implements "low-level" functionalities for the whole software. Main external dependecies are shown as well. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 80 6.3 Workflow for caspo subcommands. For clarity, we distinguish three execution levels. First, the command-line (end-user) level where input and output files

iterations, the "high-quality" ensemble of logical networks can be used to find (robust) intervention strategies and generate novel hypotheses. . . . . . . . . . xxii 6.2 are handled. Second, the subcommands (application) level where input data is converted to logic facts, combined with a specific logic program, and given to the next level for launching ASP tools. Normally, some kind of "business logic" is implemented at this level, for instance, the identification of input-output behaviors using Algorithm 1 (Section 3.4.3), or first find the optimum and then enumerate solutions within certain tolerance. Third, the ASP solving (external) level where ASP tools are executed using system calls and the resulting answer sets are loaded into memory as python objects, which in turn are provided to the application level for further analysis. . . . . . . . . . . . . . . . . . . . . . . . 82 6.4 Visualization provided by caspo.

  2.1 Truth tables for classical (Boolean) logic. . . . . . . . . . . . . . . . . . . . . . . . . . 13 2.2 Truth tables for Kleene's logic. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14 2.3 Exemplary iterated application of Ω (V,φ| C ) for (V, φ) in Figure 2.1a, clamping assignment

Table 2 .

 2 2: Truth tables for Kleene's logic.

  3.3: Learning an optimum Boolean logic model

	$ gringo toy . lp learning . lp | clasp --quiet =1
	clasp version 3.0.2
	Reading from stdin
	Solving ...
	Answer : 13
	formula (e ,1) formula (d ,2) formula (g ,3) formula (f ,4) \
	dnf (1 ,1) dnf (1 ,2) dnf (2 ,4) dnf (3 ,14) dnf (4 ,15) \
	clause (1 ,b ,1) clause (2 ,c ,1) clause (4 ,a ,1) \
	clause (14 , e ,1) clause (14 , c , -1) clause (15 , d ,1) clause (15 , e ,1)
	Optimization : 88 7
	OPTIMUM FOUND
	Models	: 13
	Optimum	: yes
	Optimization : 88 7
	Calls	: 1
	Time	: 0.005 s ( Solving : 0.00 s 1 st Model : 0.00 s Unsat : 0.00 s )
	CPU Time	: 0.000 s

  Phosphorylation activities P C i for the 15 readouts were measured using the xMAP technology (Luminex) at 30 minutes after perturbation and normalized to the range [0, 1]. The time-point characteristic for the immediate-early response, viz. 30 minutes, was chosen based on preliminary experiments (considering several time-points) looking for the largest changes in protein modification states. The number of measurements or size of the dataset is given by N ξ = 858. Notice that this does not correspond exactly to 64 × 15 = 960 due to bad-readouts in the experiments. Importantly, both Θ r ss and Θ r ss k defined respectively in (3.2) and(3.5), are absolute values which normally increase with N ξ . Thus, in order to provide an better picture of how well a Boolean logic model fits the available (amount of) observations, in what follows we report the normalized (discrete) residual sum of squares, i.e., mean squared error (MSE). Towards this end, for a Boolean logic model (V, φ) and dataset ξ, let us define Θ mse and Θ mse k as

Table 3 .

 3 1: Enumeration of (nearly) optimal Boolean logic models. We report for each tolerance T , the number of Boolean logic models found M , the CPU time used by the ASP solver t enum , the range of MSEs Θ mse k and Θ mse , the range of sizes Θ si ze , the number of logical input-output behaviors B and the CPU time used by the script implementing Algorithm 1.

	T	M	t enum	Θ mse k	Θ mse	Θ si ze	B t i n-out
	0%	16	0.35s	0.0499	0.0499	28	1	0.560s
	2%	144	0.32s 0.0499 -0.0507 0.0499 -0.0507 27 -28 4	4.846s
	4% 2150 0.

  |V S |+|V K | . However, in practice, combining more than a few perturbations in the same experiment may be out of reach for current technology. In this context, let us denote with |C i | V S and |C i | V K , the number of stimuli and inhibitors respectively clamped in C i . That is, |C i

Table 3

 3

	Listing 4.4: Finding an optimal experimental design to discriminate 4 behaviors
	$ clingo design . lp behaviors -31. lp -c maxstimuli =3 -c maxinhi bitors =2\
	--quiet =2 --conf = many -t 8
	clingo version 4.3.1
	Reading from design . lp ...
	Solving ...
	Solving ...
	Solving ...
	Solving ...
	Solving ...
	Optimization : 28138 12 7
	OPTIMUM FOUND
	Models	: 19
	Optimum	: yes
	Optimization : 28138 12 7
	Calls	: 5
	Time	: 119.240 s ( Solving : 11 6.15 s 1 st Model : 0.70 s Unsat : 20.08 s )
	CPU Time	: 931.380 s
	Threads	: 8	( Winner : 0)

.1. Let us denote with B m the corresponding set of m input-output behaviors, namely, B 4 , B 31 , B 38 , B 66 , and B 91 . Then, in what follows, we denote with the filename behaviors-m.lp, the set of logic facts describing each problem instance B m as illustrated in Listing 4.1 for our toy example.

Table 4 .

 4 2: Input-output discrimination over the search space of experiments C

  In fact, now we can use the analyze subcommand again with the intervention strategies as input. Currently, only basic statistical analysis is implemented for intervention strategies. Nonetheless, further analysis may be implemented in the future. The output file strategies-stats.csv contains the frequency of each single intervention (either positive or negative), and mutually exclusive/inclusive pairs. Notice that, since we do not use neither --networks nor --midas arguments, the result is different from the previous call to this subcommand shown in Listing 6.5 Notably, if we use arguments --networks, --midas, and --strategies in the same call, all analyses are performed with such a call.Visualization support. Basic visualization features are provided by the subcommand visualize. In Listing 6.11 we show the corresponding help message for this subcommand. Similarly to the analyze subcommand, in this case there are no required arguments. The goal of this subcommand is to provide relatively simple visualization for the outcome from other subcommands. More precisely, it is possible to visualize a prior knowledge network in a SIF file with the corresponding experimental setup given in a MIDAS file. Also, visualization of logical networks as (signed) directed hypergraphs is provided for either a random sample or all networks in given CSV file. Moreover, the union (overlapping) of all logical networks is also provided. Finally, intervention strategies given in a CSV file can be visualized as well. In all cases, we choose to use DOT files as output format. Such a format is a quite widespread way of describing graph structures. Importantly, various programs can process a DOT file and render it in graphical form using several file formats, e.g., PDF, PNG, SVG and PS among others. Notably, most of such programs are included in the Graphviz package which is freely available.

	caspo analytics summary
	= == == == === == == = == == = == =
	Total intervention strategies : 3
	$ caspo visualize --help
	usage : caspo visualize [ -h ] [ --pkn P ] [ --midas M ] [ --net works N ]
		[ --sample R ] [ --union ] [ --strategies S ]
	$ caspo control out / networks . csv scenarios . csv
	Running caspo control ... optional arguments :
	-h , --help	show this help message an d exit
	Wrote out / strategies . csv --pkn P prior knowledge netw ork in SIF format
	--midas M	experimental dataset in M IDAS file
	--networks N	logical networks in CSV format
	--sample R	visualize a sample of R logical networks
		( Default to all )
	--union	visualize the union of logical networks
		( Default to False )
	--strategies S intervention stratgies in CSV format
	Listing 6.10: Running analyze subcommand (again)
	$ caspo analyze --strategies out / strategies . csv
	Running caspo analyze ...
	Wrote out / strategies -stats . csv
	Wrote out / summary . txt

12

Listing 6.11: Help message for visualize subcommand

  2.1. First, we note that rules 8-10 in Π 4.2 generate the representation of all clamping assignments (C 1 , . . . ,C ε) ∈ C 1 (s, k)ו • •×C ε (s, k) for increasing values of ε ≥ 1.Next, it is easy to extend Proposition 2.2.1 to consider several logical networks and clamping assignments. More precisely, let us denote with Π � the set of rules 1-17 in Π 4.2 . Then, we have that for each (C 1 , . . . ,C ε

  a Formal Approach Based on Answer Set Programming. D. Gilbert and M. Heiner (Eds.): 10th International Conference on Computational Methods in Systems Biology.LNCS 7605, pp. 342-361. Springer, Heidelberg. DOI: 10.1007/978-3-642-33636-2 20 AWARDS Best Paper at "The 10th Conference on Computational Methods in Systems Biology, 3-5 October 2012, The Royal Society, London, UK". Videla S., Guziolowski C., Eduati F., Thiele S., Grabe N., Saez-Rodriguez J. and Siegel A. Revisiting the Training of Logic Models of Protein Signaling Networks with a Formal Approach based on Answer Set Programming. TEACHING EXPERIENCE Answer Set Programming for Systems Biology (graduate seminar) November 2013 Center of Mathematical Modeling, University of Chile, Chile. Assistant March 2006 -March 2007 / March 2010 -March 2011 Facultad de Matemática, Astronomía y Física -Univ. Nacional de Córdoba. Argentina. July 2011 Intel. Web applications development at the Argentina Software Development Center. • HTML5, Javascript, CSS3 Entrepreneur June 2007 -July 2009 Development of web sites and applications using free software technologies: • Plone CMS, Zope/Grok, Django, PostgreSQL, ExtJS Summer School in Formal Modeling of Biological Regulatory Networks. June 2013. Île de Porquerolles, France. • Latin American eScience Workshop 2013. May 2013. São Paulo, Brazil. • The São Paulo School of Advanced Science on e-Science for Bioenergy Research. October 2012. Campinas, Brazil. • 2012 International Summer School in Methods in Bioinformatics. August 2012. Tarragona, Spain. • 30 th Scientific Annual Meeting of the Argentine Society of Virology. December 2010. Córdoba, Argentina. • 4 th School of Biology and Mathematics. August 2010. Córdoba, Argentina. • Testing on Web Applications. September 2009. INTI. Córdoba, Argentina. • Testing as part of the Quality Assurance. May 2009. INTI. Córdoba, Argentina. Dr. Anne Siegel (France): anne.siegel@irisa.fr • Dr. Torsten Schaub (Germany): torsten@cs.uni-potsdam.de • Dr. Laura Alonso i Alemany (Argentina): alemany@famaf.unc.edu.ar

		Abstract/Résumé
	SOFTWARE	Contributions to the Python community (main developer):
	CONTRIBU-	• caspo
	TIONS	• pyzcasp
		• extdirect.django
		• hurry.extjs
		• megrok.jinja
	Teacher • Introduction to Algorithms • Algorithms and Data Structures I Software Engineer January 2011 -Junior Programmer March 2007 -June 2007 Santex America. Development and support of web sites. • PHP, OsCommerce, MySQL, HTML, CSS, Javascript • 122 INDUSTRY EXPERIENCE ATTENDANCE TO SCHOOLS AND SEMINARS REFERENCES • 123

Note that aforecited works are only some, among many, examples of such methods applied in the field.

http://www.mat.unical.it/aspcomp2013/ASPStandardization

Also known as sum-of-products[Klamt et al.,

2006b].2 More generally, a directed hyperedge is a pair (S, T ) with T ⊆ V . We consider the particular case where T is a singleton. Directed hypergraphs are sometimes referred to as "AND/OR graphs"[START_REF] Gallo | Directed hypergraphs and applications[END_REF]

The interested reader may notice the resemblance to single-step operators for logic programs introduced in[START_REF] Apt | Contributions to the theory of logic programming[END_REF] and[START_REF] Fitting | A Kripke-Kleene semantics for logic programs[END_REF] for two-and three-valued assignments respectively.

The interested reader may notice the analogy with the elimination of nodes neither controllables nor (leading to) observables during the compression of the PKN described in[Saez-Rodriguez et al.,

2009].

Notice that predicates clause/3 are only used for the sake of interpretation. One could simply replace Line 45 at the end of the encoding with #show clause(J,V,S) : edge(J,V,S); dnf(_,J). and remove Line 4.

Using the option --quiet=1 only the last (optimum) answer set is printed. Notice that the solver prints all the atoms in the answer set in a single line but we have (manually) introduced breaklines to improve readability.

Option --opt-mode=ignore tells the solver to ignore optimize statements; option -n0 tells the solver to enumerate all solutions; and option --quiet avoids printing enumerated solutions.

In fact, we have developed the library pyzcasp (available at http://svidela.github.io/pyzcasp/) providing this kind of functionality. Moreover, we rely on it in order to implement the software presented in

Chapter 6.

Notably, for computing Θ mse , beforehand one must run the solver without using the option --quiet.

We note that permutations, e.g., clamped(2,b,1), clamped(1,b,1), and clamped(1,c,1), are allowed in our encoding, but one can encode additional symmetry-breaking constraints in order to avoid them.

As in the previous chapter, we have elaborated upon our basic ASP representation (Chapter 2) in order describe the underlying lexicographic multi-objective optimization. Moreover, in this case, we have exploited the incremental and multi-threading solving features of the ASP

It is worth noting that, our notion of clamping assignments introduced in Chapter

was originally motivated as an abstraction (closer to standard logic terminology) of intervention sets.

http://www.python.org/

http://bioasp.github.io/caspo/

http://bioasp.github.io/

http://pyparsing.wikispaces.com/

http://www.numpy.org/

http://networkx.github.io/

http://code.google.com/p/pydot/

http://svidela.github.io/pyzcasp/

http://potassco.sourceforge.net/

http://wiki.cytoscape.org/Cytoscape_User_Manual/Network_Formats

http://www.cellnopt.org/doc/cnodocs/midas.html

http://graphviz.org/

http://github.com/bioasp/caspo

Acknowledgements

others. Instead, we aim at capturing generic problem settings which can be adapted to specific use cases by exploiting the elaboration tolerance of our methods.

Let us illustrate the definitions given above with our toy example from Figure 4.1 and experimental conditions C 1 = {b � → t } and C 2 = {b � → t , c � → t }. As we have shown in Table 4.1, using C 1 and C 2 we can discriminate between the three pairs of input-output behaviors. Hence, the condition given in (4.2) is satisfied for ε = 2 and the 2-tuple (C 1 ,C 2 ). In fact, in this case, ε = 2 is the minimum number of experiments required in order to satisfy (4.2). Next, we can count the number of differences among every pair of behaviors. As detailed above, we have

Therefore, Θ diff ({(V, φ 1 ), (V, φ 2 ), (V, φ 3 )}, (C 1 ,C 2 )) = 4. Finally, the complexity of the 2-tuple (C 1 ,C 2 ) is given by the two functions Θ V S and Θ V K . The number of stimuli is given by Θ V S ((C 1 ,C 2 )) = 3, whereas the number of inhibitors is given by Θ V K ((C 1 ,C 2 )) = 0.

Experimental design with Answer Set Programming

Instance

The representation of the problem instance is essentially the same as in Section 3.4.1 but applied to several networks instead of only a pair. To be more precise, let B be a finite set of input-output behaviors represented by Boolean logic models (V, φ 1 ), . . . , (V, φ n ). The facts formula( j ,v,s φ j (v) ) map variables v ∈ V to their corresponding formulas φ j (v) with j = 1, . . . , n. Meanwhile, facts over predicates variable/1, dnf/2 and clause/3 remain the same as in Listing 2.1. Also, as in Chapter 3, facts over predicates stimulus/1, inhibitor/1, and readout/1 denote nodes in V S , V K , and V R respectively. Finally, we consider two constants, namely, maxstimuli=s and maxinhibitors=k, in order to represent the search space of experimental conditions C (s, k). By default, we assign such constants to |V S | and |V K |, respectively. Afterwards, at grounding time, we can use command-line options -c maxstimuli=s -c maxinhibitors=k in order to overwrite these values with arbitrary s and k.

Listing 4.1 shows the instance representation for our toy example. That is, the three inputoutput behaviors represented by the Boolean logic models (V, φ 1 ), (V, φ 2 ), and (V, φ 3 ) shown in Figure 4.1. Listing 4.1: Toy example input instance (toy.lp) variable ( " f " ) . variable ( " e " ) . variable ( " a " ) . variable (" g " ) . variable ( " b " ) . variable ( " c " ) . variable ( " d " ) .

formula (1 , " d " ,1) . formula (1 , " e " ,0) . formula (1 , " f " ,3) . formula (1 , " g " ,2) . formula (2 , " d " ,4) . formula (2 , " e " ,0) . formula (2 , " f " ,3) . formula (2 , " g " ,2) . formula (3 , " d " ,5) . formula (3 , " e " ,0) . formula (3 , " f " ,3) . formula (3 , " g " ,2) . dnf (0 ,2) . dnf (0 ,0) . dnf (1 ,7) . dnf (1 ,8) . dnf (2 ,14) . dnf (3 ,16) . dnf (4 ,0) . dnf (4 ,7) . dnf (5 ,8) . dnf (4 ,8) . Π 5.2 the set of rules given in Listing 5.2. Proposition 5.3.1. Let (V, φ i ) i ∈N be a finite family of logical networks. Let (G j ,C j ) j ∈J be a finite family of intervention scenarios and k some positive integer. Then, there is an answer set X of τ((V, φ

and only if I is a bounded intervention strategy for (G j ,C j ) j ∈J wrt (V, φ i ) i ∈N and k.

Solving

Normally ASP solvers allow for computing cardinality-minimal solutions whereas we are interested in finding ⊆-minimal solutions. In [START_REF] Kaminski | Minimal Intervention Strategies in Logical Signaling Networks with Answer Set Programming[END_REF] we have shown how one can overcome this limitation by means of meta-programming and disjunctive logic programs [Gebser et al., 2011a] or by using a specialized solver like hclasp [START_REF] Gebser | Domain-specific heuristics in answer set programming[END_REF]. However, herein we leverage the functionality recently introduced in clasp 3 series which allow for computing ⊆-minimal solutions out-of-the-box by incorporating the features from hclasp. Importantly, this requires to use very specific command-line options for clasp. We refer the reader to clasp's documentation for more details.

In Listing 5.3 we show the only intervention strategy found for the intervention scenario In previous chapters we have shown how can we learn and refine an ensemble of logical networks in an iterative fashion. In particular, in Chapter 3, using realworld signaling pathways in human liver cells and a publicly available phospho-proteomics dataset, we have learned Boolean logic models for various levels of tolerance over fitness

Based on the information generated by the analyze subcommand, one could decide whether additional experiments are required or not. Note that, eventually, one may find an unique logical input-output behavior. In such a case, there is nothing else to discriminate. However, this is not necessarily the only criterion to break the loop of learning and experimentation.

In fact, finding an unique input-output behavior seems very unlikely from our experiments. Hence, when several input-output behaviors exists, we can assess them, for example, by means of their core predictions and variances.

Listing Finding an optimal experimental design. The optimal experimental design as described in Chapter 4 is provided by the subcommand design. In Listing 6.6 we show the corresponding help message for this subcommand. In this case, there are two required arguments, namely, the representative logical networks for each input-output behavior and the phospho-proteomics dataset. The representative logical networks must be given in a CSV file as already described.

In particular, after the execution of the analyze subcommand, the output file behaviors.csv can be used directly as an input here. Again, as explained before, this subcommand requires the dataset in a MIDAS file in order to extract the information about inputs, i.e., stimuli or inhibitors, and outputs, i.e., readouts.

Listing 6.6: Help message for design subcommand

Conclusion and prospective

In previous chapters we have presented a computational modeling approach for the construction, refinement, and control of logical signaling networks. In what follows we summarize the main contribution of this thesis and discuss about its novelty and limitations. In particular, we discuss the strengths and weaknesses of our modeling and computational methods. We conclude with prospective lines of research and future directions to explore questions raised by our work.

Contribution

On the modeling side, we have presented a mathematical framework for reasoning on the response of logical signaling networks relying on propositional logic and fixpoint semantics. Despite its relative simplicity, such a framework has proven to be generic and flexible enough to describe several interesting problems in the field. In particular, we have characterized three challenging combinatorial optimization problems related to logical signaling networks. In Chapter 3 we have revisited the problem consisting of learning from an interaction graph and phosphorylation activities at a pseudo-steady state, (Boolean) logical networks describing the immediate-early response of the system. Next, in Chapter 4 we have proposed a novel problem specification for finding optimal experimental designs to discriminate between rival logical models. Finally, in Chapter 5 we have revisited the problem consisting of finding intervention strategies in logical signaling networks. Moreover, in order to increase robustness, we extended this problem for reasoning over several alternative logical networks. Notably, these three problems (or slight variations thereof) have been previously described by other authors using different formalisms. In contrast, the proposed framework provides an unified computational modeling approach for reasoning on logical signaling networks.

On the computational side, we have addressed each of the aforementioned problems by means of Answer Set Programming (ASP). The distinctive features of ASP have allowed us to model and solve each problem in a uniform and efficient way. More precisely, in Chapter 2 we have provided a basic ASP representation to describe logical networks and their response in positive programs. For a positive program P and a set of atoms X , we define T P X = {head (r ) | r ∈ P and bod y(r ) ⊆ X } .

Iterated applications of T P are written as T j P for j ≥ 0, where T 0 P X = X and T i +1 P = T P T i P X for i ≥ 0 .

Then, C n(P ) = � i ≥0 T i P � is the smallest fixpoint of T P and defines the stable model of P .

A.2.1 Basic ASP representation

For a logical network (V, φ) and clamping assignment C over V , let us denote with τ((V, φ),C ) the set of logical facts as in Listing 2.1 and Listing 2.2. More precisely,

where each s (•) stands for some arbitrary but unique name in its respective context here.

Classical (Boolean) logic

First, we define Π A.3 by combining Listings 2.3, 2.4, and 2.5

and we prove the Proposition 2.2.1.

Let (V, φ) be a logical network without feedback-loops and let C be a clamping assignment over V . Then, there is an answer set

Completeness.

In what follows we denote

Next, by inductive hypothesis we have F � (w) = t for all w ∈ ψ ∩V , and F � (w) = f for all ¬w ∈ ψ.

Then, we also have

Hence, it follows that

Kleene's (three-valued) logics

Next, we define Π A.4 by combining Listings 2.3, 2.4, and 2.6.

and we prove the Proposition 2.2.2.

Let (V, φ) be a logical network and let C be a clamping assignment over V . Then, there is an answer set

Completeness.

In what follows we denote

for some k ≥ 0. We consider the following set of atoms X . To start with, the set of atoms τ((V, φ),C ) is included in X . Also, the set of atoms {free(v, (φ) and F (v) = f , for all ψ ∈ φ(v) atoms of the form eval_clause(s ψ , -1) are included in X . We need to show that X is a ⊆-minimal model of Π X . We do so by inspecting each rule in Π X . First, we note that X includes all facts in τ((V, φ),C ). Each of these facts belongs also to Π X . Thus, any set Y of atoms excluding at least one of them, cannot be a model of Π X . Next, consider the first rule in Π A. 4 . Notably, all its grounded instantiations belong to Π X . Furthermore, clamped(v, s) ∈ X only if v ∈ d om(C ), and either s = 1 and C (v) = t , or s = -1 and

A.2.2 Extended ASP representations

In what follows we provide informal arguments to show the correctness of each ASP encoding relying on the proofs given above. In each case, our application-specific encodings are straightforward elaborations of the rules in Π A.3 or Π A. 4 , plus certain rules or optimization statements describing the exact corresponding mathematical formulation.

Learning Boolean logic models of immediate-early response Let (V, E , σ) be a PKN. Let ξ = (C i , P C i ) be an experimental dataset over (V, E , σ) and let k define the discretization scheme. Then, there is an answer set

Proof. The proof follows from the Proposition 2.2.1. First, we note that rules 1-10 in Π 3.2 generate the representation of all logical networks (V, φ) ∈ M (V,E ,σ) . Next, it is easy to extend Proposition 2.2.1 to consider several clamping assignments C i . More precisely, let us denote with Π � the set of rules 1-19 in Π 3.2 . Then, we have that for each (V, φ) ∈ M (V,E ,σ) there is an answer set

Finding logical input-output behaviors

Let (V, φ j ), (V, φ j � ) be two Boolean logic models. Then, there is an answer set of τ((V, φ j ), (V, φ j � )) ∪ Π 3.5 if and only if there exist

Proof. The proof follows from the Proposition 2.2.2. First, we note that rules 1-14 in Π 5.2 generate the representation of all "candidate" intervention sets I . Next, it is easy to extend Proposition 2.2.2 to consider several logical networks (V, φ i ) i ∈N and clamping assignments (C j • I ) j ∈J . More precisely, let us denote with Π � the set of rules 1-26 in Π 5.2 . Then, we have that for each "candidate" intervention set I , there is an answer set X of τ((V, φ i ) i ∈N , (G j ,C j ) j ∈J , k)∪ Π � such that F i j = {v � → t | eval(i , j , v, 1) ∈ X } ∪ {v � → f | eval(i , j , v, -1) ∈ X } if and only if F i j is the unique fixpoint of Ω (V,φ i | C j •I ) reachable from A u . Also, one can verify that considering the complete set of rules in Π 5.2 , such an answer set X exists iff for all (G j ) j ∈J and i ∈ N , it hold G j ⊆ F i j and |I | ≤ k. Therefore, I is a bounded intervention strategy for (G j ,C j ) j ∈J wrt (V, φ i ) i ∈N and k. Moreover, if k ≤ 0 the integrity constraint in rule 31 is not applied and thus, I is an unbounded intervention strategy.