Molecular mechanisms for a switch-like mating decision in Saccharomyces cerevisiae

Les changements évolutifs nous instruisent sur les nombreuses innovations permettant à chaque organisme de maximiser ses aptitudes en choisissant le partenaire approprié, telles que les caractéristiques sexuelles secondaires, les patrons comportementaux, les attractifs chimiques et les mécanismes sensoriels y répondant. L'haploïde de la levure Saccharomyces cerevisiae distingue son partenaire en interprétant le gradient de la concentration d'une phéromone sécrétée par les partenaires potentiels grâce à un réseau de protéines signalétiques de type kinase activées par la mitose (MAPK). La décision de la liaison sexuelle chez la levure est un événement en "tout–ourien", à la manière d'un interrupteur. Les cellules haploïdes choisissent leur partenaire sexuel en fonction de la concentration de phéromones qu’il produit. Seul le partenaire à proximité sécrétant des concentrations de phéromones égales ou supérieures à une concentration critique est retenu. Les faibles signaux de phéromones sont attribués à des partenaires pouvant mener à des accouplements infructueux. Notre compréhension du mécanisme moléculaire contrôlant cet interrupteur de la décision d'accouplement reste encore mince. Dans le cadre de la présente thèse, je démontre que le mécanisme de décision de la liaison sexuelle provient de la compétition pour le contrôle de l'état de phosphorylation de quatre sites sur la protéine d'échafaudage Ste5, entre la MAPK, Fus3, et la phosphatase,Ptc1. Cette compétition résulte en la dissociation de type « intérupteur » entre Fus3 et Ste5, nécessaire à la prise de décision d'accouplement en "tout-ou-rien". Ainsi, la décision de la liaison sexuelle s'effectue à une étape précoce de la voie de réponse aux phéromones et se produit rapidement, peut-être dans le but de prévenir la perte d’un partenaire potentiel. Nous argumentons que l'architecture du circuit Fus3-Ste5-Ptc1 génère un mécanisme inédit d'ultrasensibilité, ressemblant à "l'ultrasensibilité d'ordre zéro", qui résiste aux variations de concentration de ces protéines. Cette robustesse assure que l'accouplement puisse se produire en dépit de la stochasticité cellulaire ou de variations génétiques entre individus.Je démontre, par la suite, qu'un évènement précoce en réponse aux signaux extracellulaires recrutant Ste5 à la membrane plasmique est également ultrasensible à l'augmentation de la concentration de phéromones et que cette ultrasensibilité est engendrée par la déphosphorylation de huit phosphosites en N-terminal sur Ste5 par la phosphatase Ptc1 lorsqu'elle est associée à Ste5 via la protéine polarisante, Bem1. L'interférence dans ce mécanisme provoque une perte de l'ultrasensibilité et réduit, du même coup, l'amplitude et la fidélité de la voie de réponse aux phéromones à la stimulation. Ces changements se reflètent en une réduction de la fidélité et de la précision de la morphologie attribuable à la réponse d'accouplement. La polarisation dans l'assemblage du complexe protéique à la surface de la membrane plasmique est un thème général persistant dans tous les organismes, de la bactérie à l'humain. Un tel complexe est en mesure d'accroître l'efficacité, la fidélité et la spécificité de la transmission du signal. L'ensemble de nos découvertes démontre que l'ultrasensibilité, la précision et la robustesse de la réponse aux phéromones découlent de la régulation de la phosphorylation stoichiométrique de deux groupes de phosphosites sur Ste5, par la phosphatase Ptc1, un groupe effectuant le recrutement ultrasensible de Ste5 à la membrane et un autre incitant la dissociation et l'activation ultrasensible de la MAPK terminal Fus3. Le rôle modulateur de Ste5 dans la décision de la destinée cellulaire étend le répertoire fonctionnel des protéines d'échafaudage bien au-delà de l'accessoire dans la spécificité et l'efficacité des traitements de l'information. La régulation de la dynamique des caractères signal-réponse à travers une telle régulation modulaire des groupes de phosphosites sur des protéines d'échafaudage combinées à l'assemblage à la membrane peut être un moyen général par lequel la polarisation du destin cellulaire est obtenue. Des mécanismes similaires peuvent contrôler les décisions cellulaires dans les organismes complexes et peuvent être compromis dans des dérèglements cellulaires, tel que le cancer. Finalement, sur un thème relié, je présente la découverte d'un nouveau mécanisme où le seuil de la concentration de phéromones est contrôlé par une voie sensorielle de nutriments, ajustant, de cette manière, le point prédéterminé dans lequel la quantité et la qualité des nutriments accessibles dans l'environnement déterminent le seuil à partir duquel la levure s'accouple. La sous-unité régulatrice de la kinase à protéine A (PKA),Bcy1, une composante clé du réseau signalétique du senseur aux nutriments, interagit directement avec la sous-unité α des petites protéines G, Gpa1, le premier effecteur dans le réseau de réponse aux phéromones. L'interaction Bcy1-Gpa1 est accrue lorsque la cellule croit en présence d'un sucre idéal, le glucose, diminuant la concentration seuil auquel la décision d'accouplement est activée. Compromettre l'interaction Bcy1-Gpa1 ou inactiver Bcy1 accroît la concentration seuil nécessaire à une réponse aux phéromones. Nous argumentons qu'en ajustant leur sensibilité, les levures peuvent intégrer le stimulus provenant des phéromones au niveau du glucose extracellulaire, priorisant la décision de survie dans un milieu pauvre ou continuer leur cycle sexuel en choisissant un accouplement.

Stochastic simulation to improve land-cover estimates derived from coarse spatial resolution satellite imagery = La simulation stochastique pour améliorer les estimations de la couverture des sols à partir d'images satellitales à résolution spatiale grossière

Thèse diffusée initialement dans le cadre d'un projet pilote des Presses de l'Université de Montréal/Centre d'édition numérique UdeM (1997-2008) avec l'autorisation de l'auteur.

Parallel metaheuristics for stochastic capacitated multicommodity network design

Mémoire numérisé par la Division de la gestion de documents et des archives de l'Université de Montréal

TONGA : un algorithme de gradient naturel pour les problèmes de grande taille

Mémoire numérisé par la Division de la gestion de documents et des archives de l'Université de Montréal

Prices of durable nonrenewable natural resources under stochastic investment opportunities

On étudie l'évolution du prix d'une ressource naturelle non renouvelable dans le cas où cette ressource est durable, c'est-à-dire qu'une fois extraite elle devient un actif productif détenu hors terre. On emprunte à la théorie de la détermination du prix des actifs pour ce faire. Le choix de portefeuille porte alors sur les actifs suivant : un stock de ressource non renouvelable détenu en terre, qui ne procure aucun service productif; un stock de ressource détenu hors terre, qui procure un flux de services productifs; un stock d'un bien composite, qui peut être détenu soit sous forme de capital productif, soit sous forme d'une obligation dont le rendement est donn e. Les productivités du secteur de production du bien composite et du secteur de l'extraction de la ressource évoluent de façon stochastique. On montre que la prédiction que l'on peut tirer quant au sentier de prix de la ressource diffère considérablement de celle qui découle de la règle d'Hotelling élémentaire et qu'aucune prédiction non ambiguë quant au comportement du sentier de prix ne peut être obtenue de façon analytique.

Étude fonctionnelle du cotransporteur Na+/glucose (hSGLT1) : courant de fuite, vitesse de cotransport et modélisation cinétique

Les résultats présentés dans cette thèse précisent certains aspects de la fonction du cotransporteur Na+/glucose (SGLT1), une protéine transmembranaire qui utilise le gradient électrochimique favorable des ions Na+ afin d’accumuler le glucose à l’intérieur des cellules épithéliales de l’intestin grêle et du rein. Nous avons tout d’abord utilisé l’électrophysiologie à deux microélectrodes sur des ovocytes de xénope afin d’identifier les ions qui constituaient le courant de fuite de SGLT1, un courant mesuré en absence de glucose qui est découplé de la stoechiométrie stricte de 2 Na+/1 glucose caractérisant le cotransport. Nos résultats ont démontré que des cations comme le Li+, le K+ et le Cs+, qui n’interagissent que faiblement avec les sites de liaison de SGLT1 et ne permettent pas les conformations engendrées par la liaison du Na+, pouvaient néanmoins générer un courant de fuite d’amplitude comparable à celui mesuré en présence de Na+. Ceci suggère que le courant de fuite traverse SGLT1 en utilisant une voie de perméation différente de celle définie par les changements de conformation propres au cotransport Na+/glucose, possiblement similaire à celle empruntée par la perméabilité à l’eau passive. Dans un deuxième temps, nous avons cherché à estimer la vitesse des cycles de cotransport de SGLT1 à l’aide de la technique de la trappe ionique, selon laquelle le large bout d’une électrode sélective (~100 μm) est pressé contre la membrane plasmique d’un ovocyte et circonscrit ainsi un petit volume de solution extracellulaire que l’on nomme la trappe. Les variations de concentration ionique se produisant dans la trappe en conséquence de l’activité de SGLT1 nous ont permis de déduire que le cotransport Na+/glucose s’effectuait à un rythme d’environ 13 s-1 lorsque le potentiel membranaire était fixé à -155 mV. Suite à cela, nous nous sommes intéressés au développement d’un modèle cinétique de SGLT1. En se servant de l’algorithme du recuit simulé, nous avons construit un schéma cinétique à 7 états reproduisant de façon précise les courants du cotransporteur en fonction du Na+ et du glucose extracellulaire. Notre modèle prédit qu’en présence d’une concentration saturante de glucose, la réorientation dans la membrane de SGLT1 suivant le relâchement intracellulaire de ses substrats est l’étape qui limite la vitesse de cotransport.

New simulation schemes for the Heston model

Les titres financiers sont souvent modélisés par des équations différentielles stochastiques (ÉDS). Ces équations peuvent décrire le comportement de l'actif, et aussi parfois certains paramètres du modèle. Par exemple, le modèle de Heston (1993), qui s'inscrit dans la catégorie des modèles à volatilité stochastique, décrit le comportement de l'actif et de la variance de ce dernier. Le modèle de Heston est très intéressant puisqu'il admet des formules semi-analytiques pour certains produits dérivés, ainsi qu'un certain réalisme. Cependant, la plupart des algorithmes de simulation pour ce modèle font face à quelques problèmes lorsque la condition de Feller (1951) n'est pas respectée. Dans ce mémoire, nous introduisons trois nouveaux algorithmes de simulation pour le modèle de Heston. Ces nouveaux algorithmes visent à accélérer le célèbre algorithme de Broadie et Kaya (2006); pour ce faire, nous utiliserons, entre autres, des méthodes de Monte Carlo par chaînes de Markov (MCMC) et des approximations. Dans le premier algorithme, nous modifions la seconde étape de la méthode de Broadie et Kaya afin de l'accélérer. Alors, au lieu d'utiliser la méthode de Newton du second ordre et l'approche d'inversion, nous utilisons l'algorithme de Metropolis-Hastings (voir Hastings (1970)). Le second algorithme est une amélioration du premier. Au lieu d'utiliser la vraie densité de la variance intégrée, nous utilisons l'approximation de Smith (2007). Cette amélioration diminue la dimension de l'équation caractéristique et accélère l'algorithme. Notre dernier algorithme n'est pas basé sur une méthode MCMC. Cependant, nous essayons toujours d'accélérer la seconde étape de la méthode de Broadie et Kaya (2006). Afin de réussir ceci, nous utilisons une variable aléatoire gamma dont les moments sont appariés à la vraie variable aléatoire de la variance intégrée par rapport au temps. Selon Stewart et al. (2007), il est possible d'approximer une convolution de variables aléatoires gamma (qui ressemble beaucoup à la représentation donnée par Glasserman et Kim (2008) si le pas de temps est petit) par une simple variable aléatoire gamma.

Quantification de la relation séquence-activité de l’ARN par prédiction de structure tridimensionnelle

Dans un premier temps, nous avons modélisé la structure d’une famille d’ARN avec une grammaire de graphes afin d’identifier les séquences qui en font partie. Plusieurs autres méthodes de modélisation ont été développées, telles que des grammaires stochastiques hors-contexte, des modèles de covariance, des profils de structures secondaires et des réseaux de contraintes. Ces méthodes de modélisation se basent sur la structure secondaire classique comparativement à nos grammaires de graphes qui se basent sur les motifs cycliques de nucléotides. Pour exemplifier notre modèle, nous avons utilisé la boucle E du ribosome qui contient le motif Sarcin-Ricin qui a été largement étudié depuis sa découverte par cristallographie aux rayons X au début des années 90. Nous avons construit une grammaire de graphes pour la structure du motif Sarcin-Ricin et avons dérivé toutes les séquences qui peuvent s’y replier. La pertinence biologique de ces séquences a été confirmée par une comparaison des séquences d’un alignement de plus de 800 séquences ribosomiques bactériennes. Cette comparaison a soulevée des alignements alternatifs pour quelques unes des séquences que nous avons supportés par des prédictions de structures secondaires et tertiaires. Les motifs cycliques de nucléotides ont été observés par les membres de notre laboratoire dans l'ARN dont la structure tertiaire a été résolue expérimentalement. Une étude des séquences et des structures tertiaires de chaque cycle composant la structure du Sarcin-Ricin a révélé que l'espace des séquences dépend grandement des interactions entre tous les nucléotides à proximité dans l’espace tridimensionnel, c’est-à-dire pas uniquement entre deux paires de bases adjacentes. Le nombre de séquences générées par la grammaire de graphes est plus petit que ceux des méthodes basées sur la structure secondaire classique. Cela suggère l’importance du contexte pour la relation entre la séquence et la structure, d’où l’utilisation d’une grammaire de graphes contextuelle plus expressive que les grammaires hors-contexte. Les grammaires de graphes que nous avons développées ne tiennent compte que de la structure tertiaire et négligent les interactions de groupes chimiques spécifiques avec des éléments extra-moléculaires, comme d’autres macromolécules ou ligands. Dans un deuxième temps et pour tenir compte de ces interactions, nous avons développé un modèle qui tient compte de la position des groupes chimiques à la surface des structures tertiaires. L’hypothèse étant que les groupes chimiques à des positions conservées dans des séquences prédéterminées actives, qui sont déplacés dans des séquences inactives pour une fonction précise, ont de plus grandes chances d’être impliqués dans des interactions avec des facteurs. En poursuivant avec l’exemple de la boucle E, nous avons cherché les groupes de cette boucle qui pourraient être impliqués dans des interactions avec des facteurs d'élongation. Une fois les groupes identifiés, on peut prédire par modélisation tridimensionnelle les séquences qui positionnent correctement ces groupes dans leurs structures tertiaires. Il existe quelques modèles pour adresser ce problème, telles que des descripteurs de molécules, des matrices d’adjacences de nucléotides et ceux basé sur la thermodynamique. Cependant, tous ces modèles utilisent une représentation trop simplifiée de la structure d’ARN, ce qui limite leur applicabilité. Nous avons appliqué notre modèle sur les structures tertiaires d’un ensemble de variants d’une séquence d’une instance du Sarcin-Ricin d’un ribosome bactérien. L’équipe de Wool à l’université de Chicago a déjà étudié cette instance expérimentalement en testant la viabilité de 12 variants. Ils ont déterminé 4 variants viables et 8 létaux. Nous avons utilisé cet ensemble de 12 séquences pour l’entraînement de notre modèle et nous avons déterminé un ensemble de propriétés essentielles à leur fonction biologique. Pour chaque variant de l’ensemble d’entraînement nous avons construit des modèles de structures tertiaires. Nous avons ensuite mesuré les charges partielles des atomes exposés sur la surface et encodé cette information dans des vecteurs. Nous avons utilisé l’analyse des composantes principales pour transformer les vecteurs en un ensemble de variables non corrélées, qu’on appelle les composantes principales. En utilisant la distance Euclidienne pondérée et l’algorithme du plus proche voisin, nous avons appliqué la technique du « Leave-One-Out Cross-Validation » pour choisir les meilleurs paramètres pour prédire l’activité d’une nouvelle séquence en la faisant correspondre à ces composantes principales. Finalement, nous avons confirmé le pouvoir prédictif du modèle à l’aide d’un nouvel ensemble de 8 variants dont la viabilité à été vérifiée expérimentalement dans notre laboratoire. En conclusion, les grammaires de graphes permettent de modéliser la relation entre la séquence et la structure d’un élément structural d’ARN, comme la boucle E contenant le motif Sarcin-Ricin du ribosome. Les applications vont de la correction à l’aide à l'alignement de séquences jusqu’au design de séquences ayant une structure prédéterminée. Nous avons également développé un modèle pour tenir compte des interactions spécifiques liées à une fonction biologique donnée, soit avec des facteurs environnants. Notre modèle est basé sur la conservation de l'exposition des groupes chimiques qui sont impliqués dans ces interactions. Ce modèle nous a permis de prédire l’activité biologique d’un ensemble de variants de la boucle E du ribosome qui se lie à des facteurs d'élongation.

Étude structure/fonction des cotransporteurs Na+/glucose

Cette thèse porte sur l’étude de la relation entre la structure et la fonction chez les cotransporteurs Na+/glucose (SGLTs). Les SGLTs sont des protéines membranaires qui se servent du gradient électrochimique transmembranaire du Na+ afin d’accumuler leurs substrats dans la cellule. Une mise en contexte présentera d’abord un bref résumé des connaissances actuelles dans le domaine, suivi par un survol des différentes techniques expérimentales utilisées dans le cadre de mes travaux. Ces travaux peuvent être divisés en trois projets. Un premier projet a porté sur les bases structurelles de la perméation de l’eau au travers des SGLTs. En utilisant à la fois des techniques de modélisation moléculaire, mais aussi la volumétrie en voltage imposé, nous avons identifié les bases structurelles de cette perméation. Ainsi, nous avons pu identifier in silico la présence d’une voie de perméation passive à l’eau traversant le cotransporteur, pour ensuite corroborer ces résultats à l’aide de mesures faites sur le cotransporteur Na/glucose humain (hSGLT1) exprimé dans les ovocytes. Un second projet a permis d’élucider certaines caractéristiques structurelles de hSGLT1 de par l’utilisation de la dipicrylamine (DPA), un accepteur de fluorescence dont la répartition dans la membrane lipidique dépend du potentiel membranaire. L’utilisation de la DPA, conjuguée aux techniques de fluorescence en voltage imposé et de FRET (fluorescence resonance energy transfer), a permis de démontrer la position extracellulaire d’une partie de la boucle 12-13 et le fait que hSGLT1 forme des dimères dont les sous-unités sont unies par un pont disulfure. Un dernier projet a eu pour but de caractériser les courants stationnaires et pré-stationaires d’un membre de la famille des SGLTs, soit le cotransporteur Na+/myo-inositol humain hSMIT2 afin de proposer un modèle cinétique qui décrit son fonctionnement. Nous avons démontré que la phlorizine inhibe mal les courants préstationnaires suite à une dépolarisation, et la présence de courants de fuite qui varient en fonction du temps, du potentiel membranaire et des substrats. Un algorithme de recuit simulé a été mis au point afin de permettre la détermination objective de la connectivité et des différents paramètres associés à la modélisation cinétique.

Optimisation des horaires des agents et du routage des appels dans les centres d’appels

Nous étudions la gestion de centres d'appels multi-compétences, ayant plusieurs types d'appels et groupes d'agents. Un centre d'appels est un système de files d'attente très complexe, où il faut généralement utiliser un simulateur pour évaluer ses performances. Tout d'abord, nous développons un simulateur de centres d'appels basé sur la simulation d'une chaîne de Markov en temps continu (CMTC), qui est plus rapide que la simulation conventionnelle par événements discrets. À l'aide d'une méthode d'uniformisation de la CMTC, le simulateur simule la chaîne de Markov en temps discret imbriquée de la CMTC. Nous proposons des stratégies pour utiliser efficacement ce simulateur dans l'optimisation de l'affectation des agents. En particulier, nous étudions l'utilisation des variables aléatoires communes. Deuxièmement, nous optimisons les horaires des agents sur plusieurs périodes en proposant un algorithme basé sur des coupes de sous-gradients et la simulation. Ce problème est généralement trop grand pour être optimisé par la programmation en nombres entiers. Alors, nous relaxons l'intégralité des variables et nous proposons des méthodes pour arrondir les solutions. Nous présentons une recherche locale pour améliorer la solution finale. Ensuite, nous étudions l'optimisation du routage des appels aux agents. Nous proposons une nouvelle politique de routage basé sur des poids, les temps d'attente des appels, et les temps d'inoccupation des agents ou le nombre d'agents libres. Nous développons un algorithme génétique modifié pour optimiser les paramètres de routage. Au lieu d'effectuer des mutations ou des croisements, cet algorithme optimise les paramètres des lois de probabilité qui génèrent la population de solutions. Par la suite, nous développons un algorithme d'affectation des agents basé sur l'agrégation, la théorie des files d'attente et la probabilité de délai. Cet algorithme heuristique est rapide, car il n'emploie pas la simulation. La contrainte sur le niveau de service est convertie en une contrainte sur la probabilité de délai. Par après, nous proposons une variante d'un modèle de CMTC basé sur le temps d'attente du client à la tête de la file. Et finalement, nous présentons une extension d'un algorithme de coupe pour l'optimisation stochastique avec recours de l'affectation des agents dans un centre d'appels multi-compétences.

An algorithm for identifying agent-k-linked allocations in economies with indivisibilities

We consider envy-free (and budget-balanced) rules that are least manipulable with respect to agents counting or with respect to utility gains. Recently it has been shown that for any profile of quasi-linear preferences, the outcome of any such least manipulable envy-free rule can be obtained via agent-k-linked allocations. This note provides an algorithm for identifying agent-k-linked allocations.

Problèmes de tournées de véhicules avec contraintes de chargement

Cette thèse s’intéresse aux problèmes de tournées de véhicules où l’on retrouve des contraintes de chargement ayant un impact sur les séquences de livraisons permises. Plus particulièrement, les items placés dans l’espace de chargement d’un véhicule doivent être directement accessibles lors de leur livraison sans qu’il soit nécessaire de déplacer d’autres items. Ces problèmes sont rencontrés dans plusieurs entreprises de transport qui livrent de gros objets (meubles, électroménagers). Le premier article de cette thèse porte sur une méthode exacte pour un problème de confection d’une seule tournée où un véhicule, dont l’aire de chargement est divisée en un certain nombre de piles, doit effectuer des cueillettes et des livraisons respectant une contrainte de type dernier entré, premier sorti. Lors d’une collecte, les items recueillis doivent nécessairement être déposés sur le dessus de l’une des piles. Par ailleurs, lors d’une livraison, les items doivent nécessairement se trouver sur le dessus de l’une des piles. Une méthode de séparation et évaluation avec plans sécants est proposée pour résoudre ce problème. Le second article présente une méthode de résolution exacte, également de type séparation et évaluation avec plans sécants, pour un problème de tournées de véhicules avec chargement d’items rectangulaires en deux dimensions. L’aire de chargement des véhicules correspond aussi à un espace rectangulaire avec une orientation, puisque les items doivent être chargés et déchargés par l’un des côtés. Une contrainte impose que les items d’un client soient directement accessibles au moment de leur livraison. Le dernier article aborde une problème de tournées de véhicules avec chargement d’items rectangulaires, mais où les dimensions de certains items ne sont pas connus avec certitude lors de la planification des tournées. Il est toutefois possible d’associer une distribution de probabilités discrète sur les dimensions possibles de ces items. Le problème est résolu de manière exacte avec la méthode L-Shape en nombres entiers.

A robust algorithm for segmenting fluorescence images and its application to single-molecule counting

La microscopie par fluorescence de cellules vivantes produit de grandes quantités de données. Ces données sont composées d’une grande diversité au niveau de la forme des objets d’intérêts et possèdent un ratio signaux/bruit très bas. Pour concevoir un pipeline d’algorithmes efficaces en traitement d’image de microscopie par fluorescence, il est important d’avoir une segmentation robuste et fiable étant donné que celle-ci constitue l’étape initiale du traitement d’image. Dans ce mémoire, je présente MinSeg, un algorithme de segmentation d’image de microscopie par fluorescence qui fait peu d’assomptions sur l’image et utilise des propriétés statistiques pour distinguer le signal par rapport au bruit. MinSeg ne fait pas d’assomption sur la taille ou la forme des objets contenus dans l’image. Par ce fait, il est donc applicable sur une grande variété d’images. Je présente aussi une suite d’algorithmes pour la quantification de petits complexes dans des expériences de microscopie par fluorescence de molécules simples utilisant l’algorithme de segmentation MinSeg. Cette suite d’algorithmes a été utilisée pour la quantification d’une protéine nommée CENP-A qui est une variante de l’histone H3. Par cette technique, nous avons trouvé que CENP-A est principalement présente sous forme de dimère.

Les algorithmes de haute résolution en tomographie d'émission par positrons : développement et accélération sur les cartes graphiques

La tomographie d’émission par positrons (TEP) est une modalité d’imagerie moléculaire utilisant des radiotraceurs marqués par des isotopes émetteurs de positrons permettant de quantifier et de sonder des processus biologiques et physiologiques. Cette modalité est surtout utilisée actuellement en oncologie, mais elle est aussi utilisée de plus en plus en cardiologie, en neurologie et en pharmacologie. En fait, c’est une modalité qui est intrinsèquement capable d’offrir avec une meilleure sensibilité des informations fonctionnelles sur le métabolisme cellulaire. Les limites de cette modalité sont surtout la faible résolution spatiale et le manque d’exactitude de la quantification. Par ailleurs, afin de dépasser ces limites qui constituent un obstacle pour élargir le champ des applications cliniques de la TEP, les nouveaux systèmes d’acquisition sont équipés d’un grand nombre de petits détecteurs ayant des meilleures performances de détection. La reconstruction de l’image se fait en utilisant les algorithmes stochastiques itératifs mieux adaptés aux acquisitions à faibles statistiques. De ce fait, le temps de reconstruction est devenu trop long pour une utilisation en milieu clinique. Ainsi, pour réduire ce temps, on les données d’acquisition sont compressées et des versions accélérées d’algorithmes stochastiques itératifs qui sont généralement moins exactes sont utilisées. Les performances améliorées par l’augmentation de nombre des détecteurs sont donc limitées par les contraintes de temps de calcul. Afin de sortir de cette boucle et permettre l’utilisation des algorithmes de reconstruction robustes, de nombreux travaux ont été effectués pour accélérer ces algorithmes sur les dispositifs GPU (Graphics Processing Units) de calcul haute performance. Dans ce travail, nous avons rejoint cet effort de la communauté scientifique pour développer et introduire en clinique l’utilisation des algorithmes de reconstruction puissants qui améliorent la résolution spatiale et l’exactitude de la quantification en TEP. Nous avons d’abord travaillé sur le développement des stratégies pour accélérer sur les dispositifs GPU la reconstruction des images TEP à partir des données d’acquisition en mode liste. En fait, le mode liste offre de nombreux avantages par rapport à la reconstruction à partir des sinogrammes, entre autres : il permet d’implanter facilement et avec précision la correction du mouvement et le temps de vol (TOF : Time-Of Flight) pour améliorer l’exactitude de la quantification. Il permet aussi d’utiliser les fonctions de bases spatio-temporelles pour effectuer la reconstruction 4D afin d’estimer les paramètres cinétiques des métabolismes avec exactitude. Cependant, d’une part, l’utilisation de ce mode est très limitée en clinique, et d’autre part, il est surtout utilisé pour estimer la valeur normalisée de captation SUV qui est une grandeur semi-quantitative limitant le caractère fonctionnel de la TEP. Nos contributions sont les suivantes : - Le développement d’une nouvelle stratégie visant à accélérer sur les dispositifs GPU l’algorithme 3D LM-OSEM (List Mode Ordered-Subset Expectation-Maximization), y compris le calcul de la matrice de sensibilité intégrant les facteurs d’atténuation du patient et les coefficients de normalisation des détecteurs. Le temps de calcul obtenu est non seulement compatible avec une utilisation clinique des algorithmes 3D LM-OSEM, mais il permet également d’envisager des reconstructions rapides pour les applications TEP avancées telles que les études dynamiques en temps réel et des reconstructions d’images paramétriques à partir des données d’acquisitions directement. - Le développement et l’implantation sur GPU de l’approche Multigrilles/Multitrames pour accélérer l’algorithme LMEM (List-Mode Expectation-Maximization). L’objectif est de développer une nouvelle stratégie pour accélérer l’algorithme de référence LMEM qui est un algorithme convergent et puissant, mais qui a l’inconvénient de converger très lentement. Les résultats obtenus permettent d’entrevoir des reconstructions en temps quasi-réel que ce soit pour les examens utilisant un grand nombre de données d’acquisition aussi bien que pour les acquisitions dynamiques synchronisées. Par ailleurs, en clinique, la quantification est souvent faite à partir de données d’acquisition en sinogrammes généralement compressés. Mais des travaux antérieurs ont montré que cette approche pour accélérer la reconstruction diminue l’exactitude de la quantification et dégrade la résolution spatiale. Pour cette raison, nous avons parallélisé et implémenté sur GPU l’algorithme AW-LOR-OSEM (Attenuation-Weighted Line-of-Response-OSEM) ; une version de l’algorithme 3D OSEM qui effectue la reconstruction à partir de sinogrammes sans compression de données en intégrant les corrections de l’atténuation et de la normalisation dans les matrices de sensibilité. Nous avons comparé deux approches d’implantation : dans la première, la matrice système (MS) est calculée en temps réel au cours de la reconstruction, tandis que la seconde implantation utilise une MS pré- calculée avec une meilleure exactitude. Les résultats montrent que la première implantation offre une efficacité de calcul environ deux fois meilleure que celle obtenue dans la deuxième implantation. Les temps de reconstruction rapportés sont compatibles avec une utilisation clinique de ces deux stratégies.

A heuristic algorithm for the Capacitated Vehicle Routing Problem with Synchronized Pick-ups and Drop-offs : a case study for medications delivery and supervision in DR Congo

Dans des contextes de post-urgence tels que le vit la partie occidentale de la République Démocratique du Congo (RDC), l’un des défis cruciaux auxquels font face les hôpitaux ruraux est de maintenir un niveau de médicaments essentiels dans la pharmacie. Sans ces médicaments pour traiter les maladies graves, l’impact sur la santé de la population est significatif. Les hôpitaux encourent également des pertes financières dues à la péremption lorsque trop de médicaments sont commandés. De plus, les coûts du transport des médicaments ainsi que du superviseur sont très élevés pour les hôpitaux isolés ; les coûts du transport peuvent à eux seuls dépasser ceux des médicaments. En utilisant la province du Bandundu, RDC pour une étude de cas, notre recherche tente de déterminer la faisabilité (en termes et de la complexité du problème et des économies potentielles) d’un problème de routage synchronisé pour la livraison de médicaments et pour les visites de supervision. Nous proposons une formulation du problème de tournées de véhicules avec capacité limitée qui gère plusieurs exigences nouvelles, soit la synchronisation des activités, la préséance et deux fréquences d’activités. Nous mettons en œuvre une heuristique « cluster first, route second » avec une base de données géospatiales qui permet de résoudre le problème. Nous présentons également un outil Internet qui permet de visualiser les solutions sur des cartes. Les résultats préliminaires de notre étude suggèrent qu’une solution synchronisée pourrait offrir la possibilité aux hôpitaux ruraux d’augmenter l’accessibilité des services médicaux aux populations rurales avec une augmentation modique du coût de transport actuel.