Pour mieux saisir les liens complexes entre génotype et phénotype, une méthode utilisée consiste à étudier les relations entre différents éléments biologiques (entre les protéines, entre les métabolites...). Celles-ci forment ce qui est appelé un réseau biologique, que l'on représente algorithmiquement par un graphe. Nous nous intéressons principalement dans cette thèse au problème de la recherche d'un motif (multi-ensemble de couleurs) dans un graphe coloré, représentant un réseau biologique. De tels motifs correspondent généralement à un ensemble d'éléments conservés au cours de l'évolution et participant à une même fonction biologique. Nous continuons l'étude algorithmique de ce problème et de ses variantes (qui admettent plus de souplesse biologique), en distinguant les instances difficiles algorithmiquement et en étudiant différentes possibilités pour contourner cette difficulté (complexité paramétrée, réduction d'instance, approximation...). Nous proposons également un greffon intégré au logiciel Cytoscape pour résoudre efficacement ce problème, que nous testons sur des données réelles.Nous nous intéressons également à différents problèmes de génomique comparative. La démarche scientifique adoptée reste la même: depuis une formalisation d'un problème biologique, déterminer ses instances difficiles algorithmiquement et proposer des solutions pour contourner cette difficulté (ou prouver que de telles solutions sont impossibles à trouver sous des hypothèses fortes) / To investigate the complex links between genotype and phenotype, one can study the relations between different biological entities. It forms a biological network, represented by a graph. In this thesis, we are interested in the occurrence of a motif (a multi-set of colors) in a vertex-colored graph, representing a biological network. Such motifs usually correspond to a set of elements realizing a same function, and which may have been evolutionarily preserved. We follow the algorithmic study of this problem, by establishing hard instances and studying possibilities to cope with the hardness (parameterized complexity, preprocessing, approximation...). We also develop a plugin for Cytoscape, in order to solve efficiently this problem and to test it on real data.We are also interested in different problems related to comparative genomics. The scientific method is the same: studying problems arising from biology, specifying the hard instances and giving solutions to cope with the hardness (or proving such solutions are unlikely)

La distance de Kendall-τ compte le nombre de paires en désaccord entre deux permuta- tions. La distance d’une permutation à un ensemble est simplement la somme des dis- tances entre cette permutation et les permutations de l’ensemble. À partir d’un ensemble donné de permutations, notre but est de trouver la permutation, appelée médiane, qui minimise cette distance à l’ensemble. Le problème de la médiane de permutations sous la distance de Kendall-τ, trouve son application en bio-informatique, en science politique, en télécommunication et en optimisation. Ce problème d’apparence simple est prouvé difficile à résoudre. Dans ce mémoire, nous présentons plusieurs approches pour résoudre le problème, pour trouver une bonne solution approximative, pour le séparer en classes caractéristiques, pour mieux com- prendre sa compléxité, pour réduire l’espace de recheche et pour accélérer les calculs. Nous présentons aussi, vers la fin du mémoire, une généralisation de ce problème et nous l’étudions avec ces mêmes approches. La majorité du travail de ce mémoire se situe dans les trois articles qui le composent et est complémenté par deux chapitres servant à les lier. / The Kendall-τ distance counts the number of pairwise disagreements between two permutations. The distance between a permutation and a set is simply the sum of the distances between the considered permutation and the permutations of the set. Given a set of permutations, we want to find the permutation, called median, that minimise that distance to the set. The problem of finding a median of permutations under the Kendall-τ distance, finds applications in bioinformatics, political science, telecommunications and optimization. This simple appearing problem is proven difficult to solve. In this master thesis, we present a few approaches to solve the problem, to find a good approximate solution, to separate it into caracteristic classes, to deepen our understanding of its complexity, to reduce the search space and to accelerate calculations. We also present, at the end of this thesis, a generalization of this problem and we study it with the same approaches. The majority of the work in this thesis is located in the three papers which compose it and is complemented by two chapters, that bound them all together.

L'augmentation et la dissémination de la résistance aux antibiotiques chez les bactéries à gram-negatif, particulièrement les Entérobactéries, les bactéries du genre Pseudomonas et Acinetobacter, représentent un problème majeur de santé publique au niveau mondial. Les infections nosocomiales causées par les bactéries multi-résistantes (BMR) ont conduit non seulement à une augmentation de la mortalité, de la morbidité, et du coût de traitement, mais aussi continuent de mettre en danger la vie des patients surtout immunodéprimés en milieu hospitalier. Bien entendu, l'utilisation abusive et non contrôlée des antibiotiques a grandement contribué à la large diffusion des déterminants de la résistance; cependant, des études récentes ont démontré que ces déterminants de la résistance pouvaient émerger à partir de sources anciennes et/ou environnementales. Ainsi, face à cette préoccupation mondiale, plusieurs études ont été rapportées avec des recommandations importantes de conduire des études épidémiologiques, moléculaires, et génomiques afin de contrôler la diffusion et l'augmentation de la résistance aux antibiotiques. De plus, durant ces 10 dernières années, nous avons assisté à l'emergence et au développement de nouvelles technologies de séquençage à haut débit coïncidant avec une augmentation exponentielle du nombre de genomes bactériens séquencés. / The increase and spread of multidrug-resistant (MDR) gram-negative bacteria especially Enterobacteriaceae, Pseudomonas, and Acinetobacter (E.P.A) species have become a major concern worldwide. The hospital-acquired infections caused by MDR bacteria have led not only to an increase in mortality, morbidity, and cost of treatment, but also continue to endanger the life of patients, especially those immunocompromised. Although the frequent misuse of antibiotic drug has greatly contributed to worldwide dissemination and resistance to antibiotics; recent studies have shown that these resistance determinants could emerge from ancient or environmental sources. Front of this worldwide concern, several studies have been reported with significant recommendations to conduct molecular epidemiology, and genomic studies, in order to control the increase and the dissemination of the antibiotic resistance. Moreover, during these last 10 years, we are witnessing the emergence and development of new technologies of high throughput sequencing and coinciding with an exponential increase of number of bacterial genomes sequenced today. Therefore, it is in this context that the project of this thesis was conducted with three essential objectives: (i) the genome sequencing of clinical MDR bacteria, the analysis and the identification of the mechanisms and the genetic determinants of antimicrobial resistance (ii) the achievement of molecular epidemiology studies from clinical MDR bacteria responsible of outbreak (iii) the development and implementation of molecular tools for monitoring and diagnosis of potential MDR bacteria.