Page suivante: 2 Requis biologique Niveau précédent: Satisfaction de contraintes et Page précédente: Sommaire

1 Introduction

L'utilisation des techniques de satisfaction de contraintes s'appuie sur la formalisation d'un problème en un réseau de contraintes, structure déclarative qui permet d'exprimer des relations entre des objets. Les nuds ou variables du réseau représentent généralement un attribut de l'objet dont la valeur devra être choisie dans un domaine habituellement fini. Une contrainte exprime une relation entre les valeurs des nuds qu'elle relie. Les techniques de propagation de contraintes permettent, par un processus de déduction, de simplifier ou d'expliciter un réseau de contraintes (inférence de nouvelles contraintes, réduction de l'ensemble des valeurs que peut prendre une variable...).

Certains problèmes mathématiques posés par la biologie se ramènent à la recherche de l'ensemble des interprétations en accord avec un ensemble de spécifications : hypothèses émises dans le domaine de la biologie, données provenant d'expériences réalisées et règles de bon sens. Ces problèmes sont la plupart du temps fortement combinatoires.

Il n'est donc pas surprenant que l'utilisation de systèmes de propagation à base de contraintes en biologie ne soit pas une nouveauté [ Buc 78, Ste 78, Ste 81]. Les spécifications sont généralement traduites sous forme de contraintes qui seront utilisées activement pour réduire un espace de recherche trop vaste. Un regain d'intérêt se manifeste aujourd'hui pour ce type d'outil [ Raw 94]. On ne peut certainement pas détacher ce regain d'intérêt des efforts réalisés et des résultats obtenus autour des problèmes de satisfaction de contraintes depuis quelques années.

Pourtant, il semble que le paradigme des systèmes à base de contraintes se heurte à la résolution de problèmes réels dans lesquels les données peuvent être incomplètes, entachées d'erreurs, provenir de sources différentes et donc être à l'origine de conflits en phase de résolution. Certains systèmes qui tentent de prendre en considération les erreurs, par exemple sous forme de données imprécises, se heurtent au problème de la production d'un très grand nombre de solutions souvent inexploitables.

Nous passons en revue trois domaines d'application pour lesquels des systèmes de propagation de contraintes sont (ou ont été) utilisés dans le domaine de la biologie moléculaire. La première section fournit au lecteur informaticien les connaissances biologiques minimales nécessaires à la compréhension des problèmes. Les trois sections qui suivent s'attachent respectivement à des problèmes de cartographie, d'analyse structurale et de planification d'expériences. La conclusion présente des extensions et améliorations qui sont souhaitables pour tenter de mieux répondre aux problèmes réels.

Page suivante: 2 Requis biologique Niveau précédent: Satisfaction de contraintes et Page précédente: Sommaire