Abstract FR:

Notre travail est une contribution à la résolution de problèmes de classification supervisée dans le domaine de l'informatique chimique, les problèmes SAR. Ces problèmes, destinés à construire des modèles reliant les structures chimiques avec une activité physico-chimique ou biologique, portent sur des objets, les molécules, modélisés par des graphes. Dans ce cadre, nous étudions le plus grand sous-graphe commun à deux graphes comme moyen de description des molécules. Nous commençons par présenter un algorithme permettant de déterminer un plus grand sous-graphe commun à deux graphes, les sous-graphes considérés étant les sous-graphes induits et connexes. Cet algorithme est performant et souple : il s'adapte directement à d'autres notions de plus grand sous-graphe commun. Nous évaluons ensuite l'intérêt du plus grand sous-graphe commun pour un problème SAR particulier : la prédiction de la biodégradabilité facile. Dans ce contexte, nous montrons que les similarités établies uniquement en quantifiant l'importance du plus grand sous-graphe commun regroupent effectivement des molécules d'activité similaire. De plus, en fonctionnant directement à partir des objets étudiés, le plus grand sous-graphe commun permet une première exploration des données d'un nouveau problème SAR. Ces travaux expérimentaux permettent de conclure sur l'intérêt effectif du plus grand sous-graphe commun dans la construction des modèles SAR.