Le Web sémantique propose un ensemble de standards et d'outils pour la formalisation et l'interopérabilité de connaissances partagées sur le Web, sous la forme d'ontologies. Les ontologies biomédicales et les données associées constituent de nos jours un ensemble de connaissances complexes, hétérogènes et interconnectées, dont l'analyse est porteuse de grands enjeux en santé, par exemple dans le cadre de la pharmacovigilance. On proposera dans cette thèse des méthodes permettant d'utiliser ces ontologies biomédicales pour étendre les possibilités d'un processus de fouille de données, en particulier, permettant de faire cohabiter et d'exploiter les connaissances de plusieurs ontologies biomédicales. Les travaux de cette thèse concernent dans un premier temps une méthode fondée sur les structures de patrons, une extension de l'analyse formelle de concepts pour la découverte de co-occurences de événements indésirables médicamenteux dans des données patients. Cette méthode utilise une ontologie de phénotypes et une ontologie de médicaments pour permettre la comparaison de ces événements complexes, et la découverte d'associations à différents niveaux de généralisation, par exemple, au niveau de médicaments ou de classes de médicaments. Dans un second temps, on utilisera une méthode numérique fondée sur des mesures de similarité sémantique pour la classification de déficiences intellectuelles génétiques. On étudiera deux mesures de similarité utilisant des méthodes de calcul différentes, que l'on utilisera avec différentes combinaisons d'ontologies phénotypiques et géniques. En particulier, on quantifiera l'influence que les différentes connaissances de domaine ont sur la capacité de classification de ces mesures, et comment ces connaissances peuvent coopérer au sein de telles méthodes numériques. Une troisième étude utilise les données ouvertes liées ou LOD du Web sémantique et les ontologies associées dans le but de caractériser des gènes responsables de déficiences intellectuelles. On utilise ici la programmation logique inductive, qui s'avère adaptée pour fouiller des données relationnelles comme les LOD, en prenant en compte leurs relations avec les ontologies, et en extraire un modèle prédictif et descriptif des gènes responsables de déficiences intellectuelles. L'ensemble des contributions de cette thèse montre qu'il est possible de faire coopérer avantageusement une ou plusieurs ontologies dans divers processus de fouille de données / The semantic Web proposes standards and tools to formalize and share knowledge on the Web, in the form of ontologies. Biomedical ontologies and associated data represents a vast collection of complex, heterogeneous and linked knowledge. The analysis of such knowledge presents great opportunities in healthcare, for instance in pharmacovigilance. This thesis explores several ways to make use of this biomedical knowledge in the data mining step of a knowledge discovery process. In particular, we propose three methods in which several ontologies cooperate to improve data mining results. A first contribution of this thesis describes a method based on pattern structures, an extension of formal concept analysis, to extract associations between adverse drug events from patient data. In this context, a phenotype ontology and a drug ontology cooperate to allow a semantic comparison of these complex adverse events, and leading to the discovery of associations between such events at varying degrees of generalization, for instance, at the drug or drug class level. A second contribution uses a numeric method based on semantic similarity measures to classify different types of genetic intellectual disabilities, characterized by both their phenotypes and the functions of their linked genes. We study two different similarity measures, applied with different combinations of phenotypic and gene function ontologies. In particular, we investigate the influence of each domain of knowledge represented in each ontology on the classification process, and how they can cooperate to improve that process. Finally, a third contribution uses the data component of the semantic Web, the Linked Open Data (LOD), together with linked ontologies, to characterize genes responsible for intellectual deficiencies. We use Inductive Logic Programming, a suitable method to mine relational data such as LOD while exploiting domain knowledge from ontologies by using reasoning mechanisms. Here, ILP allows to extract from LOD and ontologies a descriptive and predictive model of genes responsible for intellectual disabilities. These contributions illustrates the possibility of having several ontologies cooperate to improve various data mining processes

La biologie des systèmes intègre données et connaissances par des méthodes bioinformatiques, afin de mieux appréhender la physiologie des organismes. Une problématique est l’applicabilité de ces techniques aux organismes non modèles, au centre de plus en plus d’études, grâce aux avancées de séquençage et à l’intérêt croissant de la recherche sur les microbiotes. Cette thèse s’intéresse à la modélisation du métabolisme par des réseaux, et de sa fonctionnalité par diverses sémantiques basées sur les graphes et les contraintes stoechiométriques. Une première partie présente des travaux sur la complétion de réseaux métaboliques pour les organismes non modèles. Une méthode basée sur les graphes est validée, et une seconde, hybride, est développée, en programmation par ensembles réponses (ASP). Ces complétions sont appliquées à des réseaux métaboliques d’algues en biologie marine, et étendues à la recherche de complémentarité métabolique entre Ectocarpus siliculosus et une bactérie symbiotique. En s’appuyant sur les méthodes de complétion, la seconde partie de la thèse vise à proposer et implémenter une sélection de communautés à l’échelle de grands microbiotes. Une approche en deux étapes permet de suggérer des symbiotes pour l’optimisation d’un objectif donné. Elle supporte la modélisation des échanges et couvre tout l’espace des solutions. Des applications sur le microbiote intestinal humain et la sélection de bactéries pour une algue brune sont présentées. Dans l’ensemble, cette thèse propose de modéliser, développer et appliquer des méthodes reposant sur des sémantiques de graphe pour élaborer des hypothèses sur le métabolisme des organismes. / Systems biology relies on computational biology to integrate knowledge and data, for a better understanding of organisms’ physiology. Challenges reside in the applicability of methods and tools to non-model organisms, for instance in marine biology. Sequencing advances and the growing importance of elucidating microbiotas’ roles, have led to an increased interest into these organisms. This thesis focuses on the modeling of the metabolism through networks, and of its functionality using graphs and constraints semantics. In particular, a first part presents work on gap-filling metabolic networks in the context of non-model organisms. A graph-based method is benchmarked and validated and a hybrid one is developed using Answer Set Programming (ASP) and linear programming. Such gap-filling is applied on algae and extended to decipher putative interactions between Ectocarpus siliculosus and a symbiotic bacterium. In this direction, the second part of the thesis aims at proposing formalisms and implementation of a tool for selecting and screening communities of interest within microbiotas. It enables to scale to large microbiotas and, with a two-step approach, to suggest symbionts that fit the desired objective. The modeling supports the computation of exchanges, and solving can cover the whole solution space. Applications are presented on the human gut microbiota and the selection of bacterial communities for a brown alga. Altogether, this thesis proposes modeling, software and biological applications using graph-based semantics to support the elaboration of hypotheses for elucidating the metabolism of organisms.

L'objectif de cette dissertation est de développer une approche originale de validation de circuits digitaux complexes décrits dans le langage VHDL. Nous proposons de générer automatiquement, à partir d'une description VHDL comportemental au niveau algorithmique, les vecteurs de test à appliquer sur une description de niveau RTL. Nous présentons d'abord la validation de descriptions VHDL au niveau algorithmique dans le contexte général du processus de conception de circuits complexes. Ce type de description étant similaire à un programme, nous explorons les techniques utilisées dans le domaine du test de logiciels, notamment celles basées sur un critère de couverture. Nous présentons le critère du test structuré, qui est fondé sur l'utilisation du graphe de flot de contrôle du programme sous test, et de la complexité cyclomatique de McCabe comme index du nombre de chemins à tester. Nous présentons également l'algorithme de Poole qui permet de générer cet ensemble de chemins. Cependant, le langage VHDL possède des caractéristiques que l'on ne retrouve pas dans les langages de programmation traditionnels (notion de temps, interconnexion de « process » s'exécutant en parallèle, mécanisme de « retard delta »). Nous proposons donc une modélisation adéquate sous forme de graphes, permettant d'appliquer les techniques précédentes à des descriptions VHDL restreintes à un sous-ensemble prenant en compte un style de description algorithmique : un graphe de flot de contrôle, un graphe de modélisation de « process », un graphe de dépendance. Nous exposons ensuite une méthodologie pour la génération de vecteurs de test à partir des chemins générés depuis ces graphes : application de l'algorithme de Poole sur la base de la complexité cyclomatique, analyse et modification éventuelle des chemins, génération et résolution des contraintes, extraction des vecteurs de test. L'approche est finalement illustrée par la réalisation du prototype logiciel GENESI qui nous a permis d'obtenir des résultats sur les « benchmarks ITC'99 ».

Cette thèse présente l'étude de l'implantation d'un système Prolog parallèle sur une architecture sans mémoire commune dans le cadre du projet PLoSys (Parallel Logic System). L'exécution exploite le parallélisme de manière implicite. Le système repose sur un modèle OU multiséquentiel. Le partage de l'état d'exécution est assuré par copie des données. Le langage Prolog supporté est complet, et intègre les effets de bord classiques du langage. La gestion parallèle fait l'objet d'une étude complète pour préserver la compatibilité avec l'exécution séquentielle du langage Prolog. En particulier, une méthode originale est présentée pour la gestion parallèle des effets de bord. Enfin, ce document présente la réalisation d'un prototype portable, ainsi que l'analyse des résultats obtenus

Ce travail a pour thème l'extraction de connaissances à partir de données provenant de plusieurs sources reflétant un même phénomène. L'objectif visé est l'amélioration de la qualité des systèmes de surveillance. Lorsque les données sont redondantes, l'utilisation de plusieurs sources permet de pallier aux problèmes de perte de signal et de bruit. Lorsque les données sont complémentaires, l'utilisation conjointe des différentes sources permet d'augmenter les performances en détection de ces systèmes. Nous appliquons nos travaux au domaine du diagnostic d'arythmies cardiaques. Nous utilisons une technique d'apprentissage artificiel relationnel (la programmation logique inductive) pour apprendre des règles discriminantes permettant de caractériser les arythmies à partir de plusieurs voies d'un électrocardiogramme et de mesures de pression artérielle. Pour exploiter la redondance des sources, nous apprenons dans un premier temps, des règles à partir des données des différentes sources prises séparément. Pour exploiter la complémentarité des sources, un apprentissage multisource naïf consisterait à apprendre globalement sur l'ensemble des données et avec un langage d'expression des concepts permettant de couvrir toute la richesse des données représentées. En alternative à un tel type d'apprentissage, nous proposons une méthode plus efficace qui s'appuie sur des apprentissages monosources, ie. effectués sur chacune des sources séparément, pour biaiser l'espace de recherche multisource. Le fait de s'appuyer sur les règles monosources permet de restreindre le langage des hypothèses ainsi que le nombre de relations possibles entre les objets représentés sur les différentes sources. Ce travail a été effectué dans le cadre du projet RNTS (Réseau National des Technologies et de la Santé) Cepica. Les résultats montrent que les règles apprises par apprentissage multisource sont au moins aussi bonnes que les règles monosources dans le cas où les données sont redondantes et meilleures dans les cas où les sources sont complémentaires. La technique d'apprentissage biaisé permet en outre d'apprendre des règles de manière beaucoup plus efficace que dans le cas naïf en bénéficiant d'un biais de langage généré automatiquement. Ces nouvelles règles sont incorporées au système Calicot pour la surveillance de patients souffrant de troubles du rythme cardiaque.<br />~

Le terme agent a été introduit pour masquer l'origine diverse des participants (produits logiciels ou humains) intervenant dans une interaction. Un agent est considéré comme une boîte noire capable de contrôler son comportement. Cette propriété, appelée autonomie, est en contradiction avec la possibilité de contrôler l'agent depuis l'extérieur. Dans cette thèse, nous proposons la norme sociale comme une solution de compromis à ce conflit. Une norme a le double rôle d'informer quel est le comportement désirable et d'influencer les agents pour qu'ils l'adoptent. Cette thèse comprend deux parties, la première introduit les concepts, la seconde propose les outils. La première partie est centrée autour du paradigme de la conception sociale des Systèmes Multi-Agents (SMA). Nous montrons comment les notions de dépendance sociale, d'organisation et de rôle permettent de mieux décrire l'interaction entre agents. La notion de norme est définie dans ses diférentes acceptions : domaine juridique, sécurité informatique, systèmes distribués, et SMA. Ensuite, nous présentons nos choix et nos solutions concernant l'interaction normative. Les structures architecturales qui en résultent sont appelées Système d'Agents Normatifs (SAN). Nous montrons quels en sont les acteurs majeurs et quels sont les outils pour les construire. La description des normes utilise les concepts d'action, de temps, d'obligation et d'agence. La deuxième partie montre comment ces concepts sont formalisés dans la littérature (p. ex. logique temporelle, déontique, de l'action) et présente leurs inconvénients majeurs. Ensuite, nous proposons un modèle temporel pour décrire l'interaction normative en expliquant les choix des éléments utilisés et nous montrons son applicabilité. Le modèle est utilisé pour produire les outils nécessaires à la construction des SAN : le monitoring des comportements des agents, la détection des violations, l'ordonnancement déontique, la communication normative.

De nombreuses applications du traitement automatique des langues (recherche d'information, traduction automatique, etc.) requièrent des ressources sémantiques spécifiques à leur tâche et à leur domaine. Pour répondre à ces besoins spécifiques, nous avons développé ASARES, un système d'acquisition d'informations sémantiques lexicales sur corpus. Celui-ci répond à un triple objectif : il permet de fournir des résultats de bonne qualité, ses résultats et le processus ayant conduit à leur extraction sont interprétables, et enfin, il est assez générique et automatique pour être aisément portable d'un corpus à un autre. Pour ce faire, ASARES s'appuie sur une technique d'apprentissage artificiel symbolique --- la programmation logique inductive --- qui lui permet d'inférer des patrons d'extraction morphosyntaxiques et sémantiques à partir d'exemples des éléments lexicaux sémantiques que l'on souhaite acquérir. Ces patrons sont ensuite utilisés pour extraire du corpus de nouveaux éléments. Nous montrons également qu'il est possible de combiner cette approche symbolique avec des techniques d'acquisition statistiques qui confèrent une plus grande automaticité à ASARES. Pour évaluer la validité de notre méthode, nous l'avons appliquée à l'extraction d'un type de relations sémantiques entre noms et verbes définies au sein du Lexique génératif appelées relations qualia. Cette tâche d'acquisition revêt deux intérêts principaux. D'une part, ces relations ne sont définies que de manière théorique ; l'interprétabilité linguistique des patrons inférés permet donc d'en préciser le fonctionnement et les réalisations en contexte. D'autre part, plusieurs auteurs ont noté l'intérêt de ce type de relations dans le domaine de la recherche d'information pour donner accès à des reformulations sémantiquement équivalentes d'une même idée. Grâce à une expérience d'extension de requêtes, nous vérifions expérimentalement cette affirmation : nous montrons que les résultats d'un système de recherche exploitant ces relations qualia, acquises par ASARES, sont améliorés de manière significative quoique localisée.

Durant cette thèse, nous avons travaillé sur l'adaptation des algorithmes d'inférence grammaticale pour la recherche des propriétés communes à un ensemble de protéines. L'inférence grammaticale positive cherche à générer, à partir d'un ensemble de mots appartenant à un langage cible particulier inconnu, une représentation grammaticale qui est "optimale" par rapport à ce langage, c'est-à-dire qui rassemble et organise les particularités des mots du langage. Nous avons utilisé le diagramme de Taylor, qui classe les acides aminés suivant leurs propriétés physico-chimiques, pour construire, sous forme de treillis, un ordre sur les groupes d'acides aminés. Nous avons aussi développé une méthode d'inférence (SDTM) qui calcule les meilleurs alignements locaux entre les paires de protéines suivant un score fondé à la fois sur cet ordre et sur les propriétés statistiques de l'ensemble de protéines donné. Le résultat est une machine séquentielle proche de celle de Mealy avec des sorties réduites à "accepte" et "rejette". L'algorithme commence par construire le plus grand automate reconnaissant exactement les mots du langage et le généralise par fusions successives des paires de transitions correspondant aux acides aminés appariés dans les alignements sélectionnés. Les expérimentations ont montré l'intérêt de cette combinaison de méthodes importées de la découverte de motifs et de l'inférence grammaticale.

Déterminer la structure 3D des protéines expérimentalement est une tâche très lourde et coûteuse, qui peut s'avérer parfois impossible à réaliser. L'arrivée massive de données provenant des programmes de séquençage à grande échelle impose de passer d'une approche biochimique à une approche bioinformatique, et nécessite en particulier de développer des méthodes de prédiction sur des séquences.<br />Cette thèse propose l'exploration de deux nouvelles pistes pour progresser dans la résolution de prédiction de ponts disulfures dans les protéines. Cette liaison covalente stabilise et contraint fortement la conformation spatiale de la protéine et la connaissance des positions où elle intervient peut réduire considérablement la complexité du problème de la prédiction de la structure 3D. Pour cela, nous utilisons dans un premier temps, l'inférence grammaticale et plus particulièrement les langages de contrôle introduit par Y. Takada, puis dans un deuxième temps, la programmation logique inductive.<br />Diverses expériences visent à confronter un cadre théorique d'apprentissage et des algorithmes généraux d'inférence grammaticale régulière à une application pratique de prédiction d'appariements spécifiques au sein d'une séquence protéique. D'autres expérimentations montrent que la programmation logique inductive donne de bons résultats sur la prédiction de l'état oxydé des cystéines en inférant des règles interprétables par les biologistes. Nous proposons un algorithme d'induction heuristique dont l'idée est d'effectuer plusieurs phases d'apprentissage en tenant compte des résultats obtenus aux phases précédentes permettant ainsi de diminuer considérablement la combinatoire dans les espaces d'hypothèses logiques en construisant des règles de plus en plus discriminantes.

Une demande croissante d'outils pour construire et décrypter des réseaux génétiques contrôlant des processus cellulaires est ressentie en biologie. Nous soutenons que l'utilisation de l'approche déclarative est pertinente et applicable pour répondre aux questions des biologistes sur ces réseaux, en général partiellement connus. L'idée principale est de modéliser des connaissances portant à la fois sur la structure et la dynamique d'un réseau par un ensemble de contraintes représentant l'ensemble des solutions, de vérifier sa cohérence, de réparer une incohérence éventuelle par un relâchement automatique, et d'inférer des propriétés sur la structure et la dynamique du réseau. Pour montrer la faisabilité de l'approche, nous formalisons les réseaux discrets de R. Thomas et les propriétés biologiques pertinentes, proposons un outil reposant sur la programmation logique par contraintes en coopération avec un solveur SAT, et la validons sur des applications biologiques significatives.