Approches de programmation par contraintes pour l'analyse des propriétés structurelles des réseaux de Petri et application aux réseaux biochimiques
Institution:
Paris 7Disciplines:
Directors:
Abstract EN:
Petri nets are a simple formalism for modelling concurrent computation. This formalism has been proposed as a promising tool to describe and analyse biochemical networks. In this thesis, we explore the structural properties of Petri nets as a mean to provide information about the biochemical system evolution and its dynamics, especially when kinetic data are missing, making simulations impossible. In particular, we consider the structural properties of siphons and traps. We show that these structures entail a family of particular stability properties which can be characterized by a fragment of CTL over infinite state structures. Mixed integer linear programs have been proposed and a state-of-the-art algorithm from the Petri net community has been described later to compute minimal sets of siphons and traps in Petri nets. We present a simple boolean model capturing these notions and compare SAT and CLP methods for enumerating the set of all minimal siphons and traps of a Petri net. Our methods successfully apply to a practical benchmark composed of the 404 models from the biomodels. Net repository. We analyse why these programs perform so well on even very large biological rnodels although the decision problem is NP-complete. We show that, in networks with bounded tree-width, the existence of a minimal siphon containing a given set of places can be decided in linear lime and the Siphon-Trap property as well. Moreover, we consider two other Petri net structural properties: place and transition invariants. We present a simple method to extract minimal semi-positive invariants of a Petri net as a constraint satisfaction problem on finite domains using constraint programming with symmetry detection and breaking. This allows us to generalize well-known results about the steady-state analysis of symbolic Ordinaty Differential Equations systems corresponding to biochemical reactions by taking into account the structure of the reaction network. The study of the underlying Petri net, initially introduced for metabolic flux analysis, provides classes of reaction systems for which the symbolic computation of steady states is possible.
Abstract FR:
Les réseaux de Petri représentent un simple formalisme pour modéliser les calculs concurrents. Ce formalisme a été proposé comme un outil prometteur pour décrire et analyser les réseaux biochimiques. Dans cette thèse, nous explorons les propriétés structurelles des réseaux de Petri comme un moyen de fournir des informations sur l'évolution du système biochimique et sa dynamique, en particulier lorsque les données cinétiques sont absentes, ce qui rend les simulations numériques impossibles. Nous considérons les propriétés structurelles de siphons et de pièges. Nous montrons que ces structures définissent une famille de propriétés qui peuvent être caractérisés par un fragment de CTL sur les structures infinies. Des programmes linéaires en nombres entiers ont été proposés pour calculer les ensembles minimaux de siphons et de pièges dans les réseaux de Petri. Un algorithme dédié, qui représente l'état de l'art dans la communauté des réseaux de Petri, a été décrit plus tard. Nous présentons un modèle booléen simple qui capture ces notions et nous comparons deux méthodes, SAT et PLC, pour énumérer l'ensemble des siphons et des pièges minimaux d'un réseau de Petri. Nos méthodes s'appliquent avec succès à un banc d'essai pratique composé de 404 modèles du dépôt biomodels. Net. Nous analysons pourquoi ces programmes performent aussi bien sur même de très grands modèles biologiques, bien que le problème de décision relatif soit NP-complet. Nous montrons que, dans les réseaux à largeur arborescente bornée, l'existence d'un siphon minimal contenant un ensemble donné de places peut être décidé en temps linéaire, ainsi que et la propriété Siphon-Trap. En outre, nous considérons deux autres propriétés structurelles de réseaux Petri nets: les invariants de places et de transition. Nous présentons une méthode simple pour extraire les invariants minimaux semi-positifs d'un réseau de Petri comme un problème de satisfaction de contraintes sur les domaines finis en utilisant la programmation par contraintes avec détection de symétrie et de rupture. Cela nous permet de généraliser les résultats connus sur l'analyse de systèmes symboliques d'équations différentielles ordinaires correspondant à des réactions biochimiques en régime permanent en tenant compte de la structure du réseau de réaction. En effet, l'étude de réseau de Petri sous-jacent, initialement introduit pour l'analyse des flux métaboliques, fournit des classes de systèmes de réaction pour lesquelles le calcul symbolique des états d'équilibre est possible.