Conception d'un système ASP basé sur une nouvelle sémantique et application aux problèmes biologiques
Institution:
Aix-MarseilleDisciplines:
Directors:
Abstract EN:
Answer Set Programming (ASP) is a declarative programming paradigm based on logic. In the first part of this thesis, we use a new semantics for logic programs to design an ASP system. This semantics offers the ability to compute all the stable models of a logic program, and to compute extra-models when the logic program does not have stable models. We also proposed an approach to exploit symmetries and thus avoid the exploration of isomorphic spaces in the search tree.The symmetries are statically processed by adding additional constraints in a pretreatment phase to eliminate them. In the second part of the thesis, we apply our ASP approach to represent and solve some biological problems. First, we proposed a method to search attractors for a chosen update mode (synchronous or asynchronous). In this method, attractor detection involves simulating the dynamics of Boolean networks, and then checking for the existence of attractors. Secondly, we proposed an approach for the detection of attractors where no simulation is carried out. The approach will focus on the particular case of circuits that play an important role in biological systems. We have seen that there are some common properties between circuit networks and the new semantics. In addition to the search of attractors, we have treated in this thesis the formalization and the reasoning on genes networks
Abstract FR:
La programmation par ensemble réponse (Answer Set Programming, ASP) est un paradigme de programmation déclaratif basé sur la logique. Dans la première partie de la thèse, nous exploitons une nouvelle sémantique pour les programmes logiques dans la conception d'un nouveau système ASP. La sémantique nous donne la possibilité de calculer tous les modèles stables d'un programme logique, et de calculer des extra-modèles lorsque le programme logique n'a pas de modèles stables. Nous avons aussi proposé une approche pour exploiter les symétries et éviter ainsi l'exploration d'espaces isomorphes dans l'arbre de recherche. Les symétries sont traitées de manière statique en ajoutant dans une phase de prétraitement des contraintes supplémentaires pour les éliminer. La seconde partie de la thèse traite les problèmes biologiques via l'approche ASP décrite en première partie. Dans un premier temps, nous avons proposé une méthode dédiée à la recherche d’attracteurs pour un mode de mise à jour choisi (synchrone ou asynchrone). Dans cette approche, la détection d'attracteurs passe par la simulation de la dynamique des réseaux booléens, puis par la vérification de l'existence des attracteurs. Dans un second temps, une approche pour la détection d’attracteurs est proposée. Dans celle-ci, aucune simulation n'est effectuée. L'approche se concentrera sur le cas particulier des circuits qui jouent un rôle important dans les systèmes biologiques. Nous avons mentionné qu'il existe certaines propriétés communes entre les circuits et la nouvelle sémantique. En plus de la recherche d'attracteurs, nous avons traité la formalisation et le raisonnement sur des réseaux de gènes