Cette thèse est à l'intersection de deux domaines de recherche en plein expansion, à savoir la fouille de données et la bio-informatique. Avec l'émergence des bases de graphes au cours des dernières années, de nombreux efforts ont été consacrés à la fouille des sous-graphes fréquents. Mais le nombre de sous-graphes fréquents découverts est exponentiel, cela est due principalement à la nature combinatoire des graphes. Beaucoup de sous-graphes fréquents ne sont pas pertinents parce qu'ils sont redondants ou tout simplement inutiles pour l'utilisateur. En outre, leur nombre élevé peut nuire ou même rendre parfois irréalisable toute utilisation ultérieure. La redondance dans les sous-graphes fréquents est principalement due à la similarité structurelle et / ou sémantique, puisque la plupart des sous-graphes découverts diffèrent légèrement dans leur structures et peuvent exprimer des significations similaires ou même identiques. Dans cette thèse, nous proposons deux approches de sélection des sous-graphes représentatifs parmi les fréquents a n d'éliminer la redondance. Chacune des approches proposées s'intéresse à un type spécifique de redondance. La première approche s'adresse à la redondance sémantique où la similarité entre les sous-graphes est mesurée en fonction de la similarité entre les étiquettes de leurs nœuds, en utilisant les connaissances de domaine. La deuxième approche s'adresse à la redondance structurelle où les sous-graphes sont représentés par des descripteurs topologiques définis par l'utilisateur, et la similarité entre les sous-graphes est mesurée en fonction de la distance entre leurs descriptions topologiques respectives. Les principales données d'application de cette thèse sont les structures 3D des protéines. Ce choix repose sur des raisons biologiques et informatiques. D'un point de vue biologique, les protéines jouent un rôle crucial dans presque tous les processus biologiques. Ils sont responsables d'une variété de fonctions physiologiques. D'un point de vue informatique, nous sommes intéressés à la fouille de données complexes. Les protéines sont un exemple parfait de ces données car elles sont faites de structures complexes composées d'acides aminés interconnectés qui sont eux-mêmes composées d'atomes interconnectés. Des grandes quantités de structures protéiques sont actuellement disponibles dans les bases de données en ligne. Les structures 3D des protéines peuvent être transformées en graphes où les acides aminés représentent les nœuds du graphe et leurs connexions représentent les arêtes. Cela permet d'utiliser des techniques de fouille de graphes pour les étudier. L'importance biologique des protéines et leur complexité ont fait d'elles des données d'application appropriées pour cette thèse.

Certains processus biologiques tels que le transport vésiculaire sont régulés par des motifs qui guident les protéines vers les membranes courbées. L'un d'entre eux est le motif ALPS (Amphipathic Lipid Packing Sensor) qui reconnaît les défauts de packing provoqués par la courbure convexe de la membrane. Dans ce travail, nous combinons des simulations de dynamique moléculaire (DM) et des expériences de dichroïsme circulaire (CD) pour comprendre ce phénomène à l'échelle moléculaire. Les simulations de DM nous ont permis de caractériser et de quantifier les défauts de packing entre les lipides. Nous montrons que les défauts de packing provoqués par la courbure membranaire sont similaires à ceux provoqués par l'introduction de lipides coniques dans une bicouche plate composée de lipides cylindriques. En examinant l'interaction du motif ALPS avec une membrane contenant de tels défauts, nous montrons que l'insertion précoce de ce motif à la membrane est guidée par l'insertion de ses gros résidus hydrophobes dans des défauts pré-existants. Les expériences de CD et les simulations de DM avec échanges de répliques indiquent que les défauts facilitent le repliement du motif ALPS en une hélice alpha partielle. Enfin, les expériences de CD nous ont permis d'explorer la thermodynamique d'insertion du motif ALPS en fonction de la composition lipidique. Notre travail suggère que la composition de séquence particulière du motif ALPS ainsi que son faible taux d'hélicité jouent un rôle dans la reconnaissance des défauts de packing, donc de la courbure.

En forêt tropicale humide Amazonienne, les facteurs gouvernant l'évolution des espèces d'arbres restent peu connus et continuellement débattus. En particulier, les micro-variations environnementales attirent beaucoup d'attention car elles induisent de profondes modifications de structure et composition des communautés. Les variations micro-environnementales associées à la topographie ont couramment été évoquées comme facteur de radiations adaptatives chez les espèces d'arbres. Cependant, l'hypothèse de l'adaptation locale n'a jamais été testée au niveau intra-spécifique chez les arbres de forêt amazonienne alors que l'on sait que la diversité génétique des arbres tropicaux est couramment structurée à faibles échelles spatiales par des processus neutres (en particulier du fait de restrictions de flux de gènes). Dans cette étude, j'ai étudié le processus de différentiation génétique d'une espèce d'arbre (Eperua falcata, Fabaceae) dans les paysages forestiers de Guyane française grâce à la combinaison d'une approche phénotypique (génétique quantitative) et d'une approche moléculaire (génétique des populations). Je me suis attachée à répondre à trois questions principales : 1) Comment se distribue la diversité génétique dans les paysages forestiers de Guyane française ? 2) Quelles forces évolutives sont impliquées dans le processus de différentiation génétique à faible échelle spatiale ? 3) Est-ce que le processus d'adaptation locale contribue à structurer la diversité génétique à faible échelle spatiale ?

Nucleotide sequence alignment is a method used to identify regions of similarity between organisms at the genomic level. In this thesis we focus on the alignment of millions of short sequences produced by Next-Generation Sequencing (NGS) technologies against a reference database. Particularly, we direct our attention toward the analysis of metagenomic and metatranscriptomic data, that is the DNA and RNA directly extracted for an environment. Two major challenges were confronted in our developed algorithms. First, all NGS technologies today are susceptible to sequencing errors in the form of nucleotide substitutions, insertions and deletions and error rates vary between 1-15%. Second, metagenomic samples can contain thousands of unknown organisms and the only means of identifying them is to align against known closely related species. To overcome these challenges we designed a new approximate matching technique based on the universal Levenshtein automaton which quickly locates short regions of similarity (seeds) between two sequences allowing 1 error of any type. Using seeds to detect possible high scoring alignments is a widely used heuristic for rapid sequence alignment, although most existing software are optimized for performing high similarity searches and apply exact seeds. Furthermore, we describe a new indexing data structure based on the Burst trie which optimizes the search for approximate seeds. We demonstrate the efficacy of our method in two implemented software, SortMeRNA and SortMeDNA. The former can quickly filter ribosomal RNA fragments from metatranscriptomic data and the latter performs full alignment for genomic and metagenomic data.

Les systèmes de workflows disposent de modules de gestion de provenance qui collectent les informations relatives aux exécutions (données consommées et produites) permettant d'assurer la reproductibilité d'une expérience. Pour plusieurs raisons, la complexité de la structure du workflow et de ses d'exécutions est en augmentation, rendant la réutilisation de workflows plus difficile. L'objectif global de cette thèse est d'améliorer la réutilisation des workflows en fournissant des stratégies pour réduire la complexité des structures de workflow tout en préservant la provenance. Deux stratégies sont introduites. Tout d'abord, nous introduisons SPFlow un algorithme de réécriture de workflow scientifique préservant la provenance et transformant tout graphe acyclique orienté (DAG) en une structure plus simple, série-parallèle (SP). Ces structures permettent la conception d'algorithmes polynomiaux pour effectuer des opérations complexes sur les workflows (par exemple, leur comparaison) alors que ces mêmes opérations sont associées à des problèmes NP-difficile pour des structures générales de DAG. Deuxièmement, nous proposons une technique capable de réduire la redondance présente dans les workflow en détectant et supprimant des motifs responsables de cette redondance, nommés "anti-patterns". Nous avons conçu l'algorithme DistillFlow capable de transformer un workflow en un workflow sémantiquement équivalent "distillé", possédant une structure plus concise et dans laquelle on retire autant que possible les anti-patterns. Nos solutions (SPFlow et DistillFlow) ont été testées systématiquement sur de grandes collections de workflows réels, en particulier avec le système Taverna. Nos outils sont disponibles à l'adresse: https://www.lri.fr/~chenj/.

Cette thèse s'intéresse à l'application des méthodes à noyaux sur graphes pour la prédiction de propriétés moléculaires. Dans ce manuscrit, nous présentons un état de l'art des méthodes à noyaux sur graphes définies dans le cadre de la chémoinformatique et plus particulièrement les noyaux sur graphes basés sur les sacs de motifs. Dans ce cadre, nous proposons un nouveau noyau sur graphes basé sur un ensemble explicite de sous-arbres, appelés treelets, permettant d'encoder une grande partie de l'information structurelle acyclique des graphes moléculaires. Nous proposons également de combiner ce noyau avec des méthodes d'apprentissage à noyaux multiples afin d'extraire un ensemble de motifs pertinents. Cette contribution est ensuite étendue en incluant l'information cyclique encodée par deux représentations moléculaires définies par le graphe de cycles pertinents et l'hypergraphe de cycles pertinents. Le graphe des cycles pertinents permet d'encoder le système cyclique d'une molécule. L'hypergraphe de cycles pertinents correspond à une nouvelle représentation moléculaire permettant d'encoder à la fois le système cyclique d'une molécule ainsi que les relations d'adjacence entre les cycles et les parties acycliques. Nous proposons également deux noyaux sur graphes utilisant ces représentations. Enfin, la dernière partie vise à définir des noyaux sur graphes pour la chémoinformatique basés sur la distance d'édition. Un premier noyau est basé sur un opérateur de régularisation utilisant la distance d'édition entre graphes moléculaires. Le second noyau introduit la comparaison de treelets dissimilaires basée sur un algorithme de calcul de la distance d'édition entre treelets.

Plusieurs types d'expérimentation existent pour étudier et comprendre les systèmes biologiques. Dans ces travaux, nous nous intéressons à la simulation in silico, c'est-à-dire à la simulation numérique de modèles sur un ordinateur. Les systèmes biologiques sont composés d'entités, à la fois nombreuses et variées, en interaction les unes avec les autres. Ainsi, ils peuvent être modélisés par l'intermédiaire de deux approches complémentaires : l'approche population-centrée et l'approche individu-centrée. Face à la multitude et à la variété des phénomènes composant les systèmes biologiques, il nous semble pertinent de coupler ces deux approches pour obtenir une modélisation mixte. En outre, en raison de la quantité conséquente d'informations que représente l'ensemble des entités et des interactions à modéliser, la simulation numérique des systèmes biologiques est particulièrement coûteuse en temps de calcul informatique. Ainsi, dans ce mémoire, nous proposons des solutions techniques de parallélisation permettant d'exploiter au mieux les performances offertes par les architectures multicoeur et multiprocesseur et les architectures graphiques pour la simulation de systèmes biologiques à base de modélisations mixtes. Nous appliquons nos travaux au domaine de la coagulation du sang et plus particulièrement à l'étude de la cinétique biochimique à l'échelle microscopique ainsi qu'à la simulation d'un vaisseau sanguin virtuel. Ces deux applications nous permettent d'évaluer les performances offertes par les solutions techniques de parallélisation que nous proposons, ainsi que leur pertinence dans le cadre de la simulation des systèmes biologiques.

La fonction d'une protéine est souvent subordonnée à l'interaction avec un certain nombre de partenaires. L'étude de la structure tridimensionnelle de ces complexes, qui ne peut souvent se faire expérimentalement, permettrait la compréhension de nombreux processus cellulaires. Le travail présenté ici se compose de deux parties. La première traite de la mise en place d'une fonction de score pour l'amarrage protéine-protéine et la deuxième de l'étude cristallographique d'une protéine tétramérique qui est une cible antibiotique potentielle : la thymidylate synthase X de Paramecium bursaria Chlorella virus. La modélisation des complexes protéine-protéine ou docking comporte deux étapes successives : d'abord, un grand nombre de conformations sont générées, puis une fonction de score est utilisée pour les classer. Cette fonction de score doit prendre en compte à la fois la complémentarité géométrique des deux molécules et les propriétés physico-chimiques des surfaces en interaction. Nous nous sommes intéressés à la seconde étape à travers le développement d'une fonction de score rapide et fiable. Ceci est possible grâce à la tessellation de Voronoï de la structure tridimensionnelle des protéines. En effet, les tessellations de Voronoï ou de Laguerre se sont avérées être de bons modèles mathématiques de la structure des protéines. En particulier, cette formalisation permet de faire une bonne description de l'empilement et des propriétés structurales des résidus. Cette modélisation rend compte l'empilement des résidus à l'interface entre deux protéines. Ainsi, il est possible de mesurer un ensemble de paramètres sur des complexes protéine-protéine dont la structure est connue expérimentalement et sur des complexes leurres générés artificiel- lement. Ces paramètres, sont la fréquence d'apparition des résidus ou des paires de résidus, les volumes des cellules de Voronoï, les distances entre les résidus en contact à l'interface, la surface de l'interface et le nombre de résidus à l'interface. Ils ont été utilisés en entrée de procédures d'apprentissage statistique. Grâce à ces procédures (apprentissage logistique, séparateurs à vaste marge (SVM) et algorithmes génétiques), on peut obtenir des fonctions de score efficaces, ca- pables de séparer les leurres des structures réelles. Dans un deuxième temps, j'ai déterminé expérimentalement la structure de la thymidylate synthase X, cible antibiotique de choix. La thymidylate synthase X est une flavoprotéine qui a été découverte récemment. Elle intervient dans la synthèse du dTMP chez la plupart des procaryotes mais n'existe pas chez les eucaryotes supérieurs. Cette protéine catalyse le transfert de methyle du tétrahydrofolate vers le dUMP grâce à son cofacteur le FAD et au NADPH qui intervient comme substrat. La structure tridimensionnelle de l'homotétramère de la thymidylate synthase X en présence de son cofacteur, le FAD, a été résolue à 2.4 Å par remplacement moléculaire. Comme pour les structures de thymidylate synthase X de Thermotoga maritima et de Mycobacterium tuberculosis précédemment résolues, le monomère se compose d'un coeur de feuillets β et de deux hélices α à son extrémité. Le site actif se trouve à l'interface de trois monomères, la partie isoalloxazine du FAD étant accessible au solvant et proche d'une longue boucle flexible. La fixation du FAD dans cette structure est légèrement différente de celles déjà observées par la conformation de la partie adénine. Cette structure, associée aux études de mutagénèse dirigée de nos collaborateurs, a permis de mettre évidence des résidus jouant un rôle majeur lors de la catalyse.

Les travaux de recherche présentés par l'auteur ont pour objet l'application de techniques d'extraction de connaissances à partir de données (ECD) en biologie. Deux thèmes majeurs de recherche en bio-informatique sont abordés : la recherche d'homologues distants dans des familles de protéines et l'analyse du transcriptome. La recherche d'homologues distants à partir de séquences protéiques est une problématique qui consiste à découvrir de nouveaux membres d'une famille de protéines. Celle-ci partageant généralement une fonction biologique, l'identification de la famille permet d'investiguer le rôle d'une séquence protéique. Des classifieurs ont été développés pour discriminer une superfamille de protéines particulière, celle des cytokines. Ces protéines sont impliquées dans le système immunitaire et leur étude est d'une importance cruciale en thérapeutique. La technique des Séparateurs à Vastes Marges (SVM) a été retenue, cette technique ayant donné les résultats les plus prometteurs pour ce type d'application. Une méthode originale de classification a été conçue, basée sur une étape préliminaire de découverte de mots sur-représentés dans la famille d'intérêt. L'apport de cette démarche est d'utiliser un dictionnaire retreint de motifs discriminants, par rapport à des techniques utilisant un espace global de k-mots. Une comparaison avec ces dernières méthodes montre la pertinence de cette approche en termes de performances de classification. La seconde contribution pour cette thématique porte sur l'agrégation des classifieurs basée sur des essaims grammaticaux. Cette méthode vise à optimiser l'association de classifieurs selon des modèles de comportement sociaux, à la manière des algorithmes génétiques d'optimisation. Le deuxième axe de recherche traite de l'analyse des données du transcriptome. L'étude du transcriptome représente un enjeu considérable, tant du point de vue de la compréhension des mécanismes du vivant que des applications cliniques et pharmacologiques. L'analyse implicative sur des règles d'association, développée initialement par Régis Gras, a été appliquée aux données du transcriptome. Une approche originale basée sur des rangs d'observation a été proposée. Deux applications illustrent la pertinence de cette méthode : la sélection de gènes informatifs et la classification de tumeurs. Enfin, une collaboration étroite avec une équipe INSERM dirigée par Rémi Houlgatte a conduit à l'enrichissement d'une suite logicielle dédiée aux données de puces à ADN. Cette collection d'outils dénommée MADTOOLS a pour objectifs l'intégration de données du transcriptome et l'aide à la méta-analyse. Une application majeure de cette suite utilise les données publiques relatives aux pathologies musculaires. La méta-analyse, en se basant sur des jeux de données indépendants, améliore grandement la robustesse des résultats. L'étude systématique de ces données a mis en évidence des groupes de gènes co-exprimés de façon récurrente. Ces groupes conservent leur propriété discriminante au travers de jeux très divers en termes d'espèces, de maladies ou de conditions expérimentales. Cette étude peut évidemment se généraliser à l'ensemble des données publiques concernant le transcriptome. Elle ouvre la voie à une approche à très grande échelle de ce type de données pour l'étude d'autres pathologies humaines.

La génomique comparative est une discipline importante pour la compréhension de l'évolution du vivant. Différentes méthodes de comparaison existent, nous nous intéressons ici en particulier aux mesures de (dis)similarités entre les génomes. Dans cette étude, nous étudions 3 mesures : les nombres d'adjacences, de points de cassures et d'intervalles communs. En présence de gènes dupliqués ou lorsque l'ordre des gènes n'est que partiellement connu, calculer ces mesures est un problème connu pour être NP-difficile. D'une part, nous désirons calculer les nombres d'adjacences et de points de cassures pour trois modèles (exemplaire, intermédiaire, maximum) entre deux génomes possédant des duplications. Afin d'obtenir un algorithme exact, nous modélisons ces problèmes en programmes pseudo-booléens. Après expérimentation sur 12 génomes de γ-protéobactéries, nous obtenons suffisamment de résultats pour : comparer les deux mesures et les 3 modèles et évaluer des heuristiques. À ce titre, nous proposons une famille d'heuristiques basée sur une recherche de plus longue sous-séquence commune qui donne de très bons résultats sur ces données. Parallèlement à cela, nous avons étudié, pour différents problèmes de calcul de mesures entre deux génomes avec duplication, l'approximation polynomial. D'autre part, nous calculons les nombres d'adjacences et d'intervalles communs entre deux ordres partiels (avec la possibilité qu'un des ordres soit total). Nous utilisons de nouveau une approche de programmation pseudo-booléenne. À l'aide de près de 800 génomes simulés, nous étudions l'influence de paramètres inhérents aux ordres partiels et nous comparons les deux mesures étudiées.