Algorithme de branch-and-price-and-cut pour le problème de conception de réseaux avec coûts fixes, capacités et un seul produit

De nombreux problèmes liés aux domaines du transport, des télécommunications et de la logistique peuvent être modélisés comme des problèmes de conception de réseaux. Le problème classique consiste à transporter un flot (données, personnes, produits, etc.) sur un réseau sous un certain nombre de contraintes dans le but de satisfaire la demande, tout en minimisant les coûts. Dans ce mémoire, on se propose d'étudier le problème de conception de réseaux avec coûts fixes, capacités et un seul produit, qu'on transforme en un problème équivalent à plusieurs produits de façon à améliorer la valeur de la borne inférieure provenant de la relaxation continue du modèle. La méthode que nous présentons pour la résolution de ce problème est une méthode exacte de branch-and-price-and-cut avec une condition d'arrêt, dans laquelle nous exploitons à la fois la méthode de génération de colonnes, la méthode de génération de coupes et l'algorithme de branch-and-bound. Ces méthodes figurent parmi les techniques les plus utilisées en programmation linéaire en nombres entiers. Nous testons notre méthode sur deux groupes d'instances de tailles différentes (gran-des et très grandes), et nous la comparons avec les résultats donnés par CPLEX, un des meilleurs logiciels permettant de résoudre des problèmes d'optimisation mathématique, ainsi qu’avec une méthode de branch-and-cut. Il s'est avéré que notre méthode est prometteuse et peut donner de bons résultats, en particulier pour les instances de très grandes tailles.

Réduction des artéfacts de tuteur coronarien au moyen d’un algorithme de reconstruction avec renforcement des bords : étude prospective transversale en tomodensitométrie 256 coupes

Les artéfacts métalliques entraînent un épaississement artéfactuel de la paroi des tuteurs en tomodensitométrie (TDM) avec réduction apparente de leur lumière. Cette étude transversale prospective, devis mesures répétées et observateurs avec méthode en aveugle, chez 24 patients consécutifs/71 tuteurs coronariens a pour objectif de comparer l’épaisseur de paroi des tuteurs en TDM après reconstruction par un algorithme avec renforcement des bords et un algorithme standard. Une angiographie coronarienne par TDM 256 coupes a été réalisée, avec reconstruction par algorithmes avec renforcement des bords et standard. L’épaisseur de paroi des tuteurs était mesurée par méthodes orthogonale (diamètres) et circonférentielle (circonférences). La qualité d’image des tuteurs était évaluée par échelle ordinale, et les données analysées par modèles linéaire mixte et régression logistique des cotes proportionnelles. L’épaisseur de paroi des tuteurs était inférieure avec l’algorithme avec renforcement des bords comparé à l’algorithme standard, avec les méthodes orthogonale (0,97±0,02 vs 1,09±0,03 mm, respectivement; p<0,001) et circonférentielle (1,13±0,02 vs 1,21±0,02 mm, respectivement; p<0,001). Le premier causait moins de surestimation par rapport à l’épaisseur nominale comparé au second, avec méthodes orthogonale (0,89±0,19 vs 1,00±0,26 mm, respectivement; p<0,001) et circonférentielle (1,06±0,26 vs 1,13±0,31 mm, respectivement; p=0,005) et diminuait de 6 % la surestimation. Les scores de qualité étaient meilleurs avec l’algorithme avec renforcement des bords (OR 3,71; IC 95% 2,33–5,92; p<0,001). En conclusion, la reconstruction des images avec l’algorithme avec renforcement des bords génère des parois de tuteurs plus minces, moins de surestimation, et de meilleurs scores de qualité d’image que l’algorithme standard.

Bases moléculaires et cellulaires d’un trouble neurodéveloppemental causé par l’haploinsuffisance de SYNGAP1

La déficience intellectuelle est la cause d’handicap la plus fréquente chez l’enfant. De nombreuses évidences convergent vers l’idée selon laquelle des altérations dans les gènes synaptiques puissent expliquer une fraction significative des affections neurodéveloppementales telles que la déficience intellectuelle ou encore l’autisme. Jusqu’à récemment, la majorité des mutations associées à la déficience intellectuelle a été liée au chromosome X ou à la transmission autosomique récessive. D’un autre côté, plusieurs études récentes suggèrent que des mutations de novo dans des gènes à transmission autosomique dominante, requis dans les processus de la plasticité synaptique peuvent être à la source d’une importante fraction des cas de déficience intellectuelle non syndromique. Par des techniques permettant la capture de l’exome et le séquençage de l’ADN génomique, notre laboratoire a précédemment reporté les premières mutations pathogéniques dans le gène à transmission autosomique dominante SYNGAP1. Ces dernières ont été associées à des troubles comportementaux tels que la déficience intellectuelle, l’inattention, des problèmes d’humeur, d’impulsivité et d’agressions physiques. D’autres patients sont diagnostiqués avec des troubles autistiques et/ou des formes particulières d’épilepsie généralisée. Chez la souris, le knock-out constitutif de Syngap1 (souris Syngap1+/-) résulte en des déficits comme l’hyperactivité locomotrice, une réduction du comportement associée à l’anxiété, une augmentation du réflexe de sursaut, une propension à l’isolation, des problèmes dans le conditionnement à la peur, des troubles dans les mémoires de travail, de référence et social. Ainsi, la souris Syngap1+/- représente un modèle approprié pour l’étude des effets délétères causés par l’haploinsuffisance de SYNGAP1 sur le développement de circuits neuronaux. D’autre part, il est de première importance de statuer si les mutations humaines aboutissent à l’haploinsuffisance de la protéine. SYNGAP1 encode pour une protéine à activité GTPase pour Ras. Son haploinsuffisance entraîne l’augmentation des niveaux d’activité de Ras, de phosphorylation de ERK, cause une morphogenèse anormale des épines dendritiques et un excès dans la concentration des récepteurs AMPA à la membrane postsynaptique des neurones excitateurs. Plusieurs études suggèrent que l’augmentation précoce de l’insertion des récepteurs AMPA au sein des synapses glutamatergiques contribue à certains phénotypes observés chez la souris Syngap1+/-. En revanche, les conséquences de l’haploinsuffisance de SYNGAP1 sur les circuits neuronaux GABAergiques restent inconnues. Les enjeux de mon projet de PhD sont: 1) d’identifier l’impact de mutations humaines dans la fonction de SYNGAP1; 2) de déterminer si SYNGAP1 contribue au développement et à la fonction des circuits GABAergiques; 3) de révéler comment l’haploinsuffisance de Syngap1 restreinte aux circuits GABAergiques affecte le comportement et la cognition. Nous avons publié les premières mutations humaines de type faux-sens dans le gène SYNGAP1 (c.1084T>C [p.W362R]; c.1685C>T [p.P562L]) ainsi que deux nouvelles mutations tronquantes (c.2212_2213del [p.S738X]; c.283dupC [p.H95PfsX5]). Ces dernières sont toutes de novo à l’exception de c.283dupC, héritée d’un père mosaïque pour la même mutation. Dans cette étude, nous avons confirmé que les patients pourvus de mutations dans SYNGAP1 présentent, entre autre, des phénotypes associés à des troubles comportementaux relatifs à la déficience intellectuelle. En culture organotypique, la transfection biolistique de l’ADNc de Syngap1 wild-type dans des cellules pyramidales corticales réduit significativement les niveaux de pERK, en fonction de l’activité neuronale. Au contraire les constructions plasmidiques exprimant les mutations W362R, P562L, ou celle précédemment répertoriée R579X, n’engendre aucun effet significatif sur les niveaux de pERK. Ces résultats suggèrent que ces mutations faux-sens et tronquante résultent en la perte de la fonction de SYNGAP1 ayant fort probablement pour conséquences d’affecter la régulation du développement cérébral. Plusieurs études publiées suggèrent que les déficits cognitifs associés à l’haploinsuffisance de SYNGAP1 peuvent émerger d’altérations dans le développement des neurones excitateurs glutamatergiques. Toutefois, si, et auquel cas, de quelle manière ces mutations affectent le développement des interneurones GABAergiques résultant en un déséquilibre entre l’excitation et l’inhibition et aux déficits cognitifs restent sujet de controverses. Par conséquent, nous avons examiné la contribution de Syngap1 dans le développement des circuits GABAergiques. A cette fin, nous avons généré une souris mutante knockout conditionnelle dans laquelle un allèle de Syngap1 est spécifiquement excisé dans les interneurones GABAergiques issus de l’éminence ganglionnaire médiale (souris Tg(Nkx2.1-Cre);Syngap1flox/+). En culture organotypique, nous avons démontré que la réduction de Syngap1 restreinte aux interneurones inhibiteurs résulte en des altérations au niveau de leur arborisation axonale et dans leur densité synaptique. De plus, réalisés sur des coupes de cerveau de souris Tg(Nkx2.1-Cre);Syngap1flox/+, les enregistrements des courants inhibiteurs postsynaptiques miniatures (mIPSC) ou encore de ceux évoqués au moyen de l’optogénétique (oIPSC) dévoilent une réduction significative de la neurotransmission inhibitrice corticale. Enfin, nous avons comparé les performances de souris jeunes adultes Syngap1+/-, Tg(Nkx2.1-Cre);Syngap1flox/+ à celles de leurs congénères contrôles dans une batterie de tests comportementaux. À l’inverse des souris Syngap1+/-, les souris Tg(Nkx2.1-Cre);Syngap1flox/+ ne présentent pas d’hyperactivité locomotrice, ni de comportement associé à l’anxiété. Cependant, elles démontrent des déficits similaires dans la mémoire de travail et de reconnaissance sociale, suggérant que l’haploinsuffisance de Syngap1 restreinte aux interneurones GABAergiques dérivés de l’éminence ganglionnaire médiale récapitule en partie certains des phénotypes cognitifs observés chez la souris Syngap1+/-. Mes travaux de PhD établissent pour la première fois que les mutations humaines dans le gène SYNGAP1 associés à la déficience intellectuelle causent la perte de fonction de la protéine. Mes études dévoilent, également pour la première fois, l’influence significative de ce gène dans la régulation du développement et de la fonction des interneurones. D’admettre l’atteinte des cellules GABAergiques illustre plus réalistement la complexité de la déficience intellectuelle non syndromique causée par l’haploinsuffisance de SYNGAP1. Ainsi, seule une compréhension raffinée de cette condition neurodéveloppementale pourra mener à une approche thérapeutique adéquate.

Étude des propriétés polyédrales du problème de conception de réseaux multiproduits, avec coût fixe et capacité

Thèse numérisée par la Direction des bibliothèques de l'Université de Montréal.

Développement d'un curriculum et d'un modèle de l'apprenant orientés vers un domaine multidisciplinaire : l'informatique quantique

Mémoire numérisé par la Direction des bibliothèques de l'Université de Montréal.

Généalogie et pratique de médias liés à l'usage du Cosmos : du gnomon à l'astrolabe

Mémoire numérisé par la Direction des bibliothèques de l'Université de Montréal.

Nanoparticules et réseaux de neurones artificiels : de la préparation à la modélisation

Thèse numérisée par la Direction des bibliothèques de l'Université de Montréal.

Accumulation de dose à partir de champs de déformation 4D appliqués aux traitements au CyberKnife et à l'IMRT

Le cancer pulmonaire est la principale cause de décès parmi tous les cancers au Canada. Le pronostic est généralement faible, de l'ordre de 15% de taux de survie après 5 ans. Les déplacements internes des structures anatomiques apportent une incertitude sur la précision des traitements en radio-oncologie, ce qui diminue leur efficacité. Dans cette optique, certaines techniques comme la radio-chirurgie et la radiothérapie par modulation de l'intensité (IMRT) visent à améliorer les résultats cliniques en ciblant davantage la tumeur. Ceci permet d'augmenter la dose reçue par les tissus cancéreux et de réduire celle administrée aux tissus sains avoisinants. Ce projet vise à mieux évaluer la dose réelle reçue pendant un traitement considérant une anatomie en mouvement. Pour ce faire, des plans de CyberKnife et d'IMRT sont recalculés en utilisant un algorithme Monte Carlo 4D de transport de particules qui permet d'effectuer de l'accumulation de dose dans une géométrie déformable. Un environnement de simulation a été développé afin de modéliser ces deux modalités pour comparer les distributions de doses standard et 4D. Les déformations dans le patient sont obtenues en utilisant un algorithme de recalage déformable d'image (DIR) entre les différentes phases respiratoire générées par le scan CT 4D. Ceci permet de conserver une correspondance de voxels à voxels entre la géométrie de référence et celles déformées. La DIR est calculée en utilisant la suite ANTs («Advanced Normalization Tools») et est basée sur des difféomorphismes. Une version modifiée de DOSXYZnrc de la suite EGSnrc, defDOSXYZnrc, est utilisée pour le transport de particule en 4D. Les résultats sont comparés à une planification standard afin de valider le modèle actuel qui constitue une approximation par rapport à une vraie accumulation de dose en 4D.

Algorithmique et complexité des systèmes à compteurs

Réalisé en cotutelle avec l'École normale supérieure de Cachan – Université Paris-Saclay

Algorithmes de construction et correction d'arbres de gènes par la réconciliation

Les gènes, qui servent à encoder les fonctions biologiques des êtres vivants, forment l'unité moléculaire de base de l'hérédité. Afin d'expliquer la diversité des espèces que l'on peut observer aujourd'hui, il est essentiel de comprendre comment les gènes évoluent. Pour ce faire, on doit recréer le passé en inférant leur phylogénie, c'est-à-dire un arbre de gènes qui représente les liens de parenté des régions codantes des vivants. Les méthodes classiques d'inférence phylogénétique ont été élaborées principalement pour construire des arbres d'espèces et ne se basent que sur les séquences d'ADN. Les gènes sont toutefois riches en information, et on commence à peine à voir apparaître des méthodes de reconstruction qui utilisent leurs propriétés spécifiques. Notamment, l'histoire d'une famille de gènes en terme de duplications et de pertes, obtenue par la réconciliation d'un arbre de gènes avec un arbre d'espèces, peut nous permettre de détecter des faiblesses au sein d'un arbre et de l'améliorer. Dans cette thèse, la réconciliation est appliquée à la construction et la correction d'arbres de gènes sous trois angles différents: 1) Nous abordons la problématique de résoudre un arbre de gènes non-binaire. En particulier, nous présentons un algorithme en temps linéaire qui résout une polytomie en se basant sur la réconciliation. 2) Nous proposons une nouvelle approche de correction d'arbres de gènes par les relations d'orthologie et paralogie. Des algorithmes en temps polynomial sont présentés pour les problèmes suivants: corriger un arbre de gènes afin qu'il contienne un ensemble d'orthologues donné, et valider un ensemble de relations partielles d'orthologie et paralogie. 3) Nous montrons comment la réconciliation peut servir à "combiner'' plusieurs arbres de gènes. Plus précisément, nous étudions le problème de choisir un superarbre de gènes selon son coût de réconciliation.