Étude de la médiane de permutations sous la distance de Kendall-Tau

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.

Generation and screening of natural product-like compounds for antibiotic discovery

Avec l’apparition de plus en plus de souches de bactérie résistante aux antibiotiques, le développement de nouveaux antibiotiques est devenu une important problématique pour les agences de santé. C’est pour cela que la création de nouvelles plateformes pour accélérer la découverte de médicaments est devenu un besoin urgent. Dans les dernières décennies, la recherche était principalement orientée sur la modification de molécules préexistantes, la méta-analyse d’organismes produisant des molécules activent et l’analyse de librairies moléculaires pour trouver des molécules synthétiques activent, ce qui s’est avéré relativement inefficace. Notre but était donc de développer de nouvelles molécules avec des effets thérapeutiques de façon plus efficace à une fraction du prix et du temps comparé à ce qui se fait actuellement. Comme structure de base, nous avons utilisé des métabolites secondaires qui pouvaient altérer le fonctionnement des protéines ou l’interaction entre deux protéines. Pour générer ces molécules, j’ai concentré mes efforts sur les terpènes, une classe de métabolites secondaires qui possède un large éventail d’activités biologiques incluant des activités antibactériennes. Nous avons développé un système de chromosome artificiel de levure (YAC) qui permet à la fois l’assemblage directionnel et combinatoire de gènes qui permet la création de voies de biosynthèse artificielles. Comme preuve de concept, j’ai développé des YACs qui contiennent les gènes pour l’expression des enzymes impliquées dans la biosynthèse de la -carotène et de l’albaflavenone et produit ces molécules avec un haut rendement. Finalement, Des YACs produits à partir de librairies de gènes ont permis de créer une grande diversité de molécules.

Interrelated product design activities sequencing with efficient tabu search algorithms

This paper proposes and investigates a metaheuristic tabu search algorithm (TSA) that generates optimal or near optimal solutions sequences for the feedback length minimization problem (FLMP) associated to a design structure matrix (DSM). The FLMP is a non-linear combinatorial optimization problem, belonging to the NP-hard class, and therefore finding an exact optimal solution is very hard and time consuming, especially on medium and large problem instances. First, we introduce the subject and provide a review of the related literature and problem definitions. Using the tabu search method (TSM) paradigm, this paper presents a new tabu search algorithm that generates optimal or sub-optimal solutions for the feedback length minimization problem, using two different neighborhoods based on swaps of two activities and shifting an activity to a different position. Furthermore, this paper includes numerical results for analyzing the performance of the proposed TSA and for fixing the proper values of its parameters. Then we compare our results on benchmarked problems with those already published in the literature. We conclude that the proposed tabu search algorithm is very promising because it outperforms the existing methods, and because no other tabu search method for the FLMP is reported in the literature. The proposed tabu search algorithm applied to the process layer of the multidimensional design structure matrices proves to be a key optimization method for an optimal product development.