Von Neumann-Morgenstern Stable Sets in Matching Problems

The following properties of the core of a one well-known: (i) the core is non-empty; (ii) the core is a lattice; and (iii) the set of unmatched agents is identical for any two matchings belonging to the core. The literature on two-sided matching focuses almost exclusively on the core and studies extensively its properties. Our main result is the following characterization of (von Neumann-Morgenstern) stable sets in one-to-one matching problem only if it is a maximal set satisfying the following properties : (a) the core is a subset of the set; (b) the set is a lattice; (c) the set of unmatched agents is identical for any two matchings belonging to the set. Furthermore, a set is a stable set if it is the unique maximal set satisfying properties (a), (b) and (c). We also show that our main result does not extend from one-to-one matching problems to many-to-one matching problems.

Matching Markets under (In)complete Information

We are the first to introduce incomplete information to centralized many-to-one matching markets such as those to entry-level labor markets or college admissions. This is important because in real life markets (i) any agent is uncertain about the other agents' true preferences and (ii) most entry-level matching is many-to-one (and not one-to-one). We show that for stable (matching) mechanisms there is a strong and surprising link between Nash equilibria under complete information and Bayesian Nash equilibria under incomplete information. That is,given a common belief, a strategy profile is a Bayesian Nash equilibrium under incomplete information in a stable mechanism if and only if, for any true profile in the support of the common belief, the submitted profile is a Nash equilibrium under complete information at the true profile in the direct preference revelation game induced by the stable mechanism. This result may help to explain the success of stable mechanisms in these markets.

Dissecting cell cycle protein complexes using the pptimized yeast cytosine deaminase protein-fragment complementation assay “You too can play with an edge”

Les protéines sont les produits finaux de la machinerie génétique. Elles jouent des rôles essentiels dans la définition de la structure, de l'intégrité et de la dynamique de la cellule afin de promouvoir les diverses transformations chimiques requises dans le métabolisme et dans la transmission des signaux biochimique. Nous savons que la doctrine centrale de la biologie moléculaire: un gène = un ARN messager = une protéine, est une simplification grossière du système biologique. En effet, plusieurs ARN messagers peuvent provenir d’un seul gène grâce à l’épissage alternatif. De plus, une protéine peut adopter plusieurs fonctions au courant de sa vie selon son état de modification post-traductionelle, sa conformation et son interaction avec d’autres protéines. La formation de complexes protéiques peut, en elle-même, être déterminée par l’état de modifications des protéines influencées par le contexte génétique, les compartiments subcellulaires, les conditions environmentales ou être intrinsèque à la croissance et la division cellulaire. Les complexes protéiques impliqués dans la régulation du cycle cellulaire sont particulièrement difficiles à disséquer car ils ne se forment qu’au cours de phases spécifiques du cycle cellulaire, ils sont fortement régulés par les modifications post-traductionnelles et peuvent se produire dans tous les compartiments subcellulaires. À ce jour, aucune méthode générale n’a été développée pour permettre une dissection fine de ces complexes macromoléculaires. L'objectif de cette thèse est d'établir et de démontrer une nouvelle stratégie pour disséquer les complexes protéines formés lors du cycle cellulaire de la levure Saccharomyces cerevisiae (S. cerevisiae). Dans cette thèse, je décris le développement et l'optimisation d'une stratégie simple de sélection basée sur un essai de complémentation de fragments protéiques en utilisant la cytosine déaminase de la levure comme sonde (PCA OyCD). En outre, je décris une série d'études de validation du PCA OyCD afin de l’utiliser pour disséquer les mécanismes d'activation des facteurs de transcription et des interactions protéine-protéines (IPPs) entre les régulateurs du cycle cellulaire. Une caractéristique clé du PCA OyCD est qu'il peut être utilisé pour détecter à la fois la formation et la dissociation des IPPs et émettre un signal détectable (la croissance des cellules) pour les deux types de sélections. J'ai appliqué le PCA OyCD pour disséquer les interactions entre SBF et MBF, deux facteurs de transcription clés régulant la transition de la phase G1 à la phase S. SBF et MBF sont deux facteurs de transcription hétérodimériques composés de deux sous-unités : une protéine qui peut lier directement l’ADN (Swi4 ou Mbp1, respectivement) et une protéine commune contenant un domain d’activation de la transcription appelée Swi6. J'ai appliqué le PCA OyCD afin de générer un mutant de Swi6 qui restreint ses activités transcriptionnelles à SBF, abolissant l’activité MBF. Nous avons isolé des souches portant des mutations dans le domaine C-terminal de Swi6, préalablement identifié comme responsable dans la formation de l’interaction avec Swi4 et Mbp1, et également important pour les activités de SBF et MBF. Nos résultats appuient un modèle où Swi6 subit un changement conformationnel lors de la liaison à Swi4 ou Mbp1. De plus, ce mutant de Swi6 a été utilisé pour disséquer le mécanisme de régulation de l’entrée de la cellule dans un nouveau cycle de division cellulaire appelé « START ». Nous avons constaté que le répresseur de SBF et MBF nommé Whi5 se lie directement au domaine C-terminal de Swi6. Finalement, j'ai appliqué le PCA OyCD afin de disséquer les complexes protéiques de la kinase cycline-dépendante de la levure nommé Cdk1. Cdk1 est la kinase essentielle qui régule la progression du cycle cellulaire et peut phosphoryler un grand nombre de substrats différents en s'associant à l'une des neuf protéines cycline régulatrice (Cln1-3, Clb1-6). Je décris une stratégie à haut débit, voir à une échelle génomique, visant à identifier les partenaires d'interaction de Cdk1 et d’y associer la cycline appropriée(s) requise(s) à l’observation d’une interaction en utilisant le PCA OyCD et des souches délétées pour chacune des cyclines. Mes résultats nous permettent d’identifier la phase(s) du cycle cellulaire où Cdk1 peut phosphoryler un substrat particulier et la fonction potentielle ou connue de Cdk1 pendant cette phase. Par exemple, nous avons identifié que l’interaction entre Cdk1 et la γ-tubuline (Tub4) est dépendante de Clb3. Ce résultat est conforme au rôle de Tub4 dans la nucléation et la croissance des faisceaux mitotiques émanant des centromères. Cette stratégie peut également être appliquée à l’étude d'autres IPPs qui sont contrôlées par des sous-unités régulatrices.

Semiautomatic Detection of Scoliotic Rib Borders From Posteroanterior Chest Radiographs

3-D assessment of scoliotic deformities relies on an accurate 3-D reconstruction of bone structures from biplanar X-rays, which requires a precise detection and matching of anatomical structures in both views. In this paper, we propose a novel semiautomated technique for detecting complete scoliotic rib borders from PA-0° and PA-20° chest radiographs, by using an edge-following approach with multiple-path branching and oriented filtering. Edge-following processes are initiated from user starting points along upper and lower rib edges and the final rib border is obtained by finding the most parallel pair among detected edges. The method is based on a perceptual analysis leading to the assumption that no matter how bent a scoliotic rib is, it will always present relatively parallel upper and lower edges. The proposed method was tested on 44 chest radiographs of scoliotic patients and was validated by comparing pixels from all detected rib borders against their reference locations taken from the associated manually delineated rib borders. The overall 2-D detection accuracy was 2.64 ± 1.21 pixels. Comparing this accuracy level to reported results in the literature shows that the proposed method is very well suited for precisely detecting borders of scoliotic ribs from PA-0° and PA-20° chest radiographs.