Les peptides non-ribosomiaux sont des molécules produites par les micro-organismes et présentant un large éventail d'activités biologiques et pharmaceutiques. Par exemple, ils peuvent présenter des activités antibiotiques, immuno-modulatrices ou anti-tumorales. Ces peptides sont synthétisés par de grands complexes multi-enzymatiques, appelés synthétases ou NRPS (NonRibosomal Peptide Synthetases). Deux traits caractéristiques distinguent ces peptides des peptides ribosomiaux classiques : le premier est que leur structure primaire n'est pas toujours linéaire mais peut être totalement ou partiellement cyclique, branchée voir même poly-cyclique, et le second est la diversité des monomères incorporés au sein de ces peptides qui dépasse largement les vingt acides aminés protéogéniques. Nous avons développé Norine, la première ressource publique entièement dédiée aux peptides nonribosomiaux. Norine contient actuellement plus de 1 000 peptides, modélisés par des graphes étiquetés non-orientés, ainsi que des outils informatiques permettant leur analyse, comme la comparaison de compositions en monomères, la recherche de motifs structuraux ou la recherche par similarité. Des analyses statistiques sur les données contenues dans Norine ont permis de mettre en évidence des caractéristiques biologiques intéressantes comme la spécificité des monomères en fonction de l'activité biologique qui nous a conduit à l'élaboration d'un outil d'aide à la prédiction de la fonction biologique d'un peptide à partir de sa composition monomérique. En trois ans, Norine est devenue la ressource internationale pour les peptides non-ribosomiaux.

La génomique comparée est essentiellement une forme de fouille de données dans des grandes collections de relations <em>n</em>-aires. La croissance du nombre de génomes sequencés créé un stress sur la génomique comparée qui croit, au pire géométriquement, avec la croissance en données de séquence. Aujourd'hui même des laboratoires de taille modeste obtient, de façon routine, plusieurs génomes à la fois - et comme des grands consortia attend de pouvoir réaliser des analyses tout-contre-tout dans le cadre de ses stratégies multi-génomes. Afin d'adresser les besoins à tous niveaux il est nécessaire de repenser les cadres algorithmiques et les technologies de stockage de données utilisés pour la génomique comparée. Pour répondre à ces défis de mise à l'échelle, dans cette thèse nous développons des méthodes originales basées sur les technologies NoSQL et MapReduce. À partir d'une caractérisation des sorts de données utilisés en génomique comparée et d'une étude des utilisations typiques, nous définissons un formalisme pour le Big Data en génomique, l'implémentons dans la plateforme NoSQL Cassandra, et évaluons sa performance. Ensuite, à partir de deux analyses globales très différentes en génomique comparée, nous définissons deux stratégies pour adapter ces applications au paradigme MapReduce et dérivons de nouveaux algorithmes. Pour le premier, l'identification d'événements de fusion et de fission de gènes au sein d'une phylogénie, nous reformulons le problème sous forme d'un parcours en parallèle borné qui évite la latence d'algorithmes de graphe. Pour le second, le clustering consensus utilisé pour identifier des familles de protéines, nous définissons une procédure d'échantillonnage itérative qui converge rapidement vers le résultat global voulu. Pour chacun de ces deux algorithmes, nous l'implémentons dans la plateforme MapReduce Hadoop, et évaluons leurs performances. Cette performance est compétitive et passe à l'échelle beaucoup mieux que les algorithmes existants, mais exige un effort particulier (et futur) pour inventer les algorithmes spécifiques.

Cette thèse s'inscrit dans le cadre de réflexions sur la réhabilitation des structures urbaines des stations touristiques françaises de montagne, visant à une meilleure adéquation entre les pratiques actuelles des individus et l'organisation de l'espace environnant existant. Au sein de cette thématique apparaît le besoin d'élaborer un outil d'aide à la réflexion capable d'évaluer les fonctionnements des espaces des stations touristiques de montagne. A partir de ce constat, ce travail cherche à articuler une réflexion sur les pratiques de populations de stations touristiques de montagne avec une analyse de l'utilisation du temps et de l'espace par les individus (emplois du temps et de l'espace). L'approche méthodologique et théorique est fondée sur les principes et concepts de la « Time-Geography » développé par Torsten Hägerstrand (université de Lund). Les fondements de la « Time-Geography » sont développés et commentés à travers les travaux de l'école de géographie de Lund. Sont ensuite définis les objectifs d'une méthodologie cherchant à rendre compte de l'image globale des actions individuelles et collectives et de comprendre les mécanismes qui régulent, au quotidien, les processus mis en œuvre dans l'élaboration de la chaîne des activités que les individus réalisent dans l'espace et dans le temps. A titre d'exemple, une enquête est réalisée auprès des touristes, d'habitants permanents et de travailleurs saisonniers dans la station de Valloire (Savoie). Les emplois du temps et de l'espace de chaque individu interrogé sont analysés de façon exploratoire grâce à deux approches : un traitement statistique résume l'information en cherchant des homogénéités dans les emplois du temps et de l'espace ; l'utilisation d'une base de données temporelles gérant des historiques enrichit les conclusions du traitement statistique en mettant en évidence des formes de structures d'organisation des emplois du temps et de l'espace.

Les bases actuelles de données multimédia nécessitent des outils de plus en plus avancés pour pouvoir être parcourues avec efficacité. Dans ce contexte, la recherche en interaction avec un utilisateur est une approche qui permet de résoudre des requêtes à la sémantique complexe avec rapidité, sans pour autant nécessiter un haut niveau d'expertise utilisateur. Parmi les différents éléments intervenant dans la conception d'un système de recherche interactive, deux parties essentielles interviennent: l'indexation et la similarité entre les documents multimédia, et la gestion du processus interactif. Dans le contexte de la recherche multimédia par le contenu, on s'appuie sur des descriptions visuelles extraites automatiquement des documents. Suite à cette étape initiale, il est nécessaire de produire des structures de données, appelées index, ainsi qu'une métrique capable de comparer ces structures. Pour ce faire, nous proposons de représenter un document sous la forme d'un graphe, où chaque sommet du graphe représente une partie du document (région, point d'intérêt, ...) et chaque arête du graphe représente une relation entre deux parties du document. Puis, nous introduisons des métriques associées, sous la forme de fonctions noyaux sur graphes, qui permettent d'utiliser ces représentations complexes avec les méthodes d'apprentissages Hilbertiennes, telle que les SVMs. La gestion du processus interactif entre le système et un utilisateur a fait d'important progrès grâce à l'approche dite par apprentissage actif. Les premières approches proposent des critères pertinents pour la sélection de document à faire annoter par l'utilisateur, dans le but de trouver les documents recherchés au plus vite. Dans ce contexte, nous proposons d'aller plus loin en nous intéressant à la fabrication "en ligne" d'index et métriques associées en fonction de la nature de la recherche. En d'autres termes, nous proposons de remplacer le schéma traditionnel, où un unique index général est utilisé, par un schéma d'indexation active, où chaque utilisateur dispose d'un index dédié à sa requête.

Cette thèse est composée de deux contributions à l'étude des bases de données : (i) la première contribution porte sur l'amélioration de la compréhension, par l'étude formelle, de la tension entre les fonctionnalités de cohérence et de confidentialité. Cette tension permet, dans certaines situations, d'utiliser les contraintes d'intégrité (cohérence) pour révéler des secrets (confidentialité) et donc réaliser des fraudes. L'étude fixe tout d'abord un cadre général de recherche en donnant une définition formelle des notions de secret, révélation et fraude. Puis, une occurrence particulière, et originale, de tension est formalisée selon une méthode inspirée des méthodes de programmation. Cette occurrence s'est avérée liée aux treillis de Galois. (ii) la deuxième contribution porte sur la spécification et l'implémentation d'une fonctionalité originale : le classement d'objets selon leur histoire. A cette fin, l'étude répond successivement aux trois questions : qu'est-ce que l'histoire d'un objet, comment exprimer des propriétés sur l'histoire des objets, et comment les vérifier efficacement ? L'expression est réalisée par des formules de logique temporelle et la méthode de vérification repose sur la traduction de ces formules en expressions régulières puis en automates d'états finis. L'implémentation réalisée utilise cette méthode de classement pour classer a posteriori des objets du langage prototypique NewtonScript.

La fouille de données et la Programmation Par Contraintes (PPC) sont deux domaines de l'informatique qui ont eu, jusqu'à très récemment, des destins séparés. Cette thèse est l'une des toutes premières à s'intéresser aux liens entre la fouille de données et la PPC, et notamment aux apports de cette dernière à l'extraction de motifs sous contraintes. Différentes méthodes génériques pour la découverte de motifs locaux ont été proposées. Mais, ces méthodes ne prennent pas en considération le fait que l'intérêt d'un motif dépend souvent d'autres motifs. Un tel motif est appelé motif n-aire. Très peu de travaux concernant l'extraction de motifs n-aires ont été menés et les méthodes développées sont toutes ad hoc. Cette thèse propose un cadre unifié pour modéliser et résoudre les contraintes n-aires en fouille de données. Tout d'abord, l'extraction de motifs n-aires est modélisée sous forme de problème de satisfaction de contraintes (CSP). Puis, un langage de requêtes à base de contraintes de haut niveau est proposé. Ce langage permet d'exprimer une large panoplie de contraintes n-aires. Plusieurs méthodes de résolution sont développées et comparées. Les apports principaux de ce cadre sont sa déclarativité et sa généricité. Il s'agit du premier cadre générique et flexible permettant la modélisation et la résolution de contraintes n-aires en fouille de données.

Ce mémoire décrit mes activités de recherche et d'animation de recherche depuis ma thèse, soutenue en 2002. Les travaux décrits ici ont été principalement menés au LIRMM (Université Montpellier 2, CNRS UMR 5506), au sein de l'équipe TATOO. Dans ce contexte, je me suis attachée à concilier des visions trop souvent vues comme divergentes au sein des communautés liées à la fouille de données complexes : gérer l'approximation (à la fois dans les données et dans les résultats produits), la fouille de données et les bases de données complexes et volumineuses, notamment les entrepôts de données. Plus précisément, mes travaux visent à montrer qu'il est possible de relever le défi jusqu'à présent non totalement solutionné d'extraire des connaissances exploitables par les experts non informaticiens à partir d'entrepôts de données, en prenant en compte au mieux les particularités de ce domaine. En particulier, j'ai porté d'une part une grande attention à exploiter la dimension temporelle des entrepôts et d'autre part à montrer autant que faire se peut que flou et passage à l'échelle ne sont pas des notions antagonistes. Dans cet objectif, j'ai mené, dirigé, encadré et valorisé à travers des collaborations scientifiques et industrielles des travaux dont je rapporte ici une synthèse.

Au cours des dernières années, le volume des données qui sont capturées et générées a explosé. Les progrès des technologies informatiques, qui fournissent du stockage à bas prix et une très forte puissance de calcul, ont permis aux organisations d'exécuter des analyses complexes de leurs données et d'en extraire des connaissances précieuses. Cette tendance a été très importante non seulement pour l'industrie, mais a également pour la science, où les meilleures instruments et les simulations les plus complexes ont besoin d'une gestion efficace des quantités énormes de données. Le parallélisme est une technique fondamentale dans la gestion de données extrêmement volumineuses car il tire parti de l'utilisation simultanée de plusieurs ressources informatiques. Pour profiter du calcul parallèle, nous avons besoin de techniques de partitionnement de données efficaces, qui sont en charge de la division de l'ensemble des données en plusieurs partitions et leur attribution aux nœuds de calculs. Le partitionnement de données est un problème complexe, car il doit prendre en compte des questions différentes et souvent contradictoires telles que la localité des données, la répartition de charge et la maximisation du parallélisme. Dans cette thèse, nous étudions le problème de partitionnement de données, en particulier dans les bases de données parallèles scientifiques qui sont continuellement en croissance. Nous étudions également ces partitionnements dans le cadre MapReduce. Dans le premier cas, nous considérons le partitionnement de très grandes bases de données dans lesquelles des nouveaux éléments sont ajoutés en permanence, avec pour exemple une application aux données astronomiques. Les approches existantes sont limitées à cause de la complexité de la charge de travail et l'ajout en continu de nouvelles données limitent l'utilisation d'approches traditionnelles. Nous proposons deux algorithmes de partitionnement dynamique qui attribuent les nouvelles données aux partitions en utilisant une technique basée sur l'affinité. Nos algorithmes permettent d'obtenir de très bons partitionnements des données en un temps d'exécution réduit comparé aux approches traditionnelles. Nous étudions également comment améliorer la performance du framework MapReduce en utilisant des techniques de partitionnement de données. En particulier, nous sommes intéressés par le partitionnement efficient de données d'entrée avec l'objectif de réduire la quantité de données qui devront être transférées dans la phase intermédiaire, connu aussi comme " shuffle ". Nous concevons et mettons en œuvre une stratégie qui, en capturant les relations entre les tuples d'entrée et les clés intermédiaires, obtient un partitionnement efficace qui peut être utilisé pour réduire de manière significative le surcharge de communications dans MapReduce.

Dans cette thèse, nous nous intéressons à des problèmes à la croisée de deux domaines, les bases de données et les bases de connaissances. Nous considérons deux problèmes équivalents concernant les requêtes conjonctives avec négation : l'inclusion de requêtes et l'évaluation d'une requête booléenne sous l'hypothèse du monde ouvert. Nous reformulons ces problèmes sous la forme d'un problème de déduction dans un fragment de la logique du premier ordre. Puis nous raffinons des schémas d'algorithmes déjà existants et proposons de nouveaux algorithmes. Pour les étudier et les comparer expérimentalement, nous proposons un générateur aléatoire et analysons l'influence des différents paramètres sur la difficulté des instances du problème étudié. Finalement, à l'aide de cette méthodologie expérimentale, nous comparons les apports des différents raffinements et les algorithmes entre eux.

Au vu de la croissance considérable de la consommation des antidépresseurs au cours des dernières décennies et de la part non négligeable de patients qui restent non traités ou mal traités, la question du bon usage ou du mésusage de ces médicaments s'impose. Les trois études présentées dans ce rapport se sont intéressées à décrire l'augmentation de la consommation des antidépresseurs et à en comprendre les mécanismes sous-jacents. L'analyse des données de vente indique que la croissance des antidépresseurs diffère entre les pays étudiés, mais qu'elle suit un schéma classique d'augmentation suivie d'une stabilisation à un certain seuil, et que les politiques de limitation des dépenses de santé ont un impact, différent selon la maturité du marché. Les travaux sur données de remboursement montrent que si l'on peut parler de mésusage dans l'utilisation des antidépresseurs, il semble lié non pas à une prescription hors indication mais plutôt inappropriée : traitement sans diagnostic précis, prescription unique suggérant un traitement injustifié, traitement trop court en regard des recommandations internationales qui préconisent au moins 6 mois pour éviter rechutes et récidives. Les travaux que nous avons menés montrent que les bases de données peuvent constituer un outil fiable d'évaluation de la consommation (données de vente) ou d'utilisation des antidépresseurs (bases de remboursement) : utilisation simple et rapide de données de vente afin d'avoir un panorama des pratiques et utilisation plus complexe des bases de remboursement afin de mieux comprendre les pratiques. Utilisés en pratique courante, des tableaux de bord de suivi de consommation pourraient alerter les pouvoirs publics sur les dérives des consommations et permettre de mettre en place des analyses plus poussées afin de caractériser les pratiques et mieux comprendre les vecteurs de la consommation.