Zero-sum problems in finite cyclic groups

The purpose of this thesis is to investigate some open problems in the area of combinatorial number theory referred to as zero-sum theory. A zero-sequence in a finite cyclic group G is said to have the basic property if it is equivalent under group automorphism to one which has sum precisely IGI when this sum is viewed as an integer. This thesis investigates two major problems, the first of which is referred to as the basic pair problem. This problem seeks to determine conditions for which every zero-sequence of a given length in a finite abelian group has the basic property. We resolve an open problem regarding basic pairs in cyclic groups by demonstrating that every sequence of length four in Zp has the basic property, and we conjecture on the complete solution of this problem. The second problem is a 1988 conjecture of Kleitman and Lemke, part of which claims that every sequence of length n in Zn has a subsequence with the basic property. If one considers the special case where n is an odd integer we believe this conjecture to hold true. We verify this is the case for all prime integers less than 40, and all odd integers less than 26. In addition, we resolve the Kleitman-Lemke conjecture for general n in the negative. That is, we demonstrate a sequence in any finite abelian group isomorphic to Z2p (for p ~ 11 a prime) containing no subsequence with the basic property. These results, as well as the results found along the way, contribute to many other problems in zero-sum theory.

Bio-inspired optimization & sampling technique for side-chain packing in MCCE

The prediction of proteins' conformation helps to understand their exhibited functions, allows for modeling and allows for the possible synthesis of the studied protein. Our research is focused on a sub-problem of protein folding known as side-chain packing. Its computational complexity has been proven to be NP-Hard. The motivation behind our study is to offer the scientific community a means to obtain faster conformation approximations for small to large proteins over currently available methods. As the size of proteins increases, current techniques become unusable due to the exponential nature of the problem. We investigated the capabilities of a hybrid genetic algorithm / simulated annealing technique to predict the low-energy conformational states of various sized proteins and to generate statistical distributions of the studied proteins' molecular ensemble for pKa predictions. Our algorithm produced errors to experimental results within .acceptable margins and offered considerable speed up depending on the protein and on the rotameric states' resolution used.

The Salmon Algorithm - A New Population Based Search Metaheuristic

This thesis introduces the Salmon Algorithm, a search meta-heuristic which can be used for a variety of combinatorial optimization problems. This algorithm is loosely based on the path finding behaviour of salmon swimming upstream to spawn. There are a number of tunable parameters in the algorithm, so experiments were conducted to find the optimum parameter settings for different search spaces. The algorithm was tested on one instance of the Traveling Salesman Problem and found to have superior performance to an Ant Colony Algorithm and a Genetic Algorithm. It was then tested on three coding theory problems - optimal edit codes, optimal Hamming distance codes, and optimal covering codes. The algorithm produced improvements on the best known values for five of six of the test cases using edit codes. It matched the best known results on four out of seven of the Hamming codes as well as three out of three of the covering codes. The results suggest the Salmon Algorithm is competitive with established guided random search techniques, and may be superior in some search spaces.

Generator Matrix Based Search for Extremal Self-Dual Binary Error-Correcting Codes

Self-dual doubly even linear binary error-correcting codes, often referred to as Type II codes, are codes closely related to many combinatorial structures such as 5-designs. Extremal codes are codes that have the largest possible minimum distance for a given length and dimension. The existence of an extremal (72,36,16) Type II code is still open. Previous results show that the automorphism group of a putative code C with the aforementioned properties has order 5 or dividing 24. In this work, we present a method and the results of an exhaustive search showing that such a code C cannot admit an automorphism group Z6. In addition, we present so far unpublished construction of the extended Golay code by P. Becker. We generalize the notion and provide example of another Type II code that can be obtained in this fashion. Consequently, we relate Becker's construction to the construction of binary Type II codes from codes over GF(2^r) via the Gray map.

Relative Uncertainty and Additively Representable Set Rankings

This paper proposes a definition of relative uncertainty aversion for decision models under complete uncertainty. It is shown that, for a large class of decision rules characterized by a set of plausible axioms, the new criterion yields a complete ranking of those rules with respect to the relative degree of uncertainty aversion they represent. In addition, we address a combinatorial question that arises in this context, and we examine conditions for the additive representability of our rules.

Directed evolution of human dihydrofolate reductase: towards a better understanding of binding at the active site

La dihydrofolate réductase humaine (DHFRh) est une enzyme essentielle à la prolifération cellulaire, ce qui en fait une cible de choix pour le traitement de différents cancers. À cet effet, plusieurs inhibiteurs spécifiques de la DHFRh, les antifolates, ont été mis au point : le méthotrexate (MTX) et le pemetrexed (PMTX) en sont de bons exemples. Malgré l’efficacité clinique certaine de ces antifolates, le développement de nouveaux traitements s’avère nécessaire afin de réduire les effets secondaires liés à leur utilisation. Enfin, dans l’optique d’orienter la synthèse de nouveaux composés inhibiteurs des DHFRh, une meilleure connaissance des interactions entre les antifolates et leur enzyme cible est primordiale. À l’aide de l’évolution dirigée, il a été possible d’identifier des mutants de la DHFRh pour lesquels l’affinité envers des antifolates cliniquement actifs se voyait modifiée. La mutagenèse dite ¬¬de saturation a été utilisée afin de générer des banques de mutants présentant une diversité génétique au niveau des résidus du site actif de l’enzyme d’intérêt. De plus, une nouvelle méthode de criblage a été mise au point, laquelle s’est avérée efficace pour départager les mutations ayant entrainé une résistance aux antifolates et/ou un maintient de l’activité enzymatique envers son substrat natif, soient les phénotypes d’activité. La méthode de criblage consiste dans un premier temps en une sélection bactérienne à haut débit, puis dans un second temps en un criblage sur plaques permettant d’identifier les meilleurs candidats. Plusieurs mutants actifs de la DHFRh, résistants aux antifolates, ont ainsi pu être identifiés et caractérisés lors d’études de cinétique enzymatique (kcat et IC50). Sur la base de ces résultats cinétiques, de la modélisation moléculaire et des données structurales de la littérature, une étude structure-activité a été effectuée. En regardant quelles mutations ont les effets les plus significatif sur la liaison, nous avons commencé à construire un carte moléculaire des contacts impliqués dans la liaison des ligands. Enfin, des connaissances supplémentaires sur les propriétés spécifiques de liaison ont put être acquises en variant l’inhibiteur testé, permettant ainsi une meilleure compréhension du phénomène de discrimination du ligand.

Mutagénèse semi-aléatoire au site actif de la DHFR humaine : création et caractérisation de variantes hautement résistantes au MTX.

La dihydrofolate réductase humaine (DHFRh) est une enzyme essentielle à la prolifération cellulaire. Elle réduit le dihydrofolate en tétrahydrofolate, un co-facteur impliqué dans la biosynthèse des purines et du thymidylate. La DHFRh est une cible de choix pour des agents de chimiothérapie comme le méthotrexate (MTX), inhibant spécifiquement l’enzyme ce qui mène à un arrêt de la prolifération et ultimement à la mort cellulaire. Le MTX est utilisé pour le traitement de plusieurs maladies prolifératives, incluant le cancer. La grande utilisation du MTX dans le milieu clinique a mené au développement de mécanismes de résistance, qui réduisent l’efficacité de traitement. La présente étude se penche sur l’un des mécanismes de résistance, soit des mutations dans la DHFRh qui réduisent son affinité pour le MTX, dans le but de mieux comprendre les éléments moléculaires requis pour la reconnaissance de l’inhibiteur au site actif de l’enzyme. En parallèle, nous visons à identifier des variantes plus résistantes au MTX pour leur utilisation en tant que marqueurs de sélection en culture cellulaire pour des systèmes particuliers, tel que la culture de cellules hématopoïétiques souches (CHS), qui offrent des possibilités intéressantes dans le domaine de la thérapie cellulaire. Pour étudier le rôle des différentes régions du site actif, et pour vérifier la présence d’une corrélation entre des mutations à ces régions et une augmentation de la résistance au MTX, une stratégie combinatoire a été dévelopée pour la création de plusieurs banques de variantes à des résidus du site actif à proximité du MTX lié. Les banques ont été sélectionnées in vivo dans un système bactérien en utilisant des milieux de croissance contenant des hautes concentrations de MTX. La banque DHFRh 31/34/35 généra un nombre considérable de variantes combinatoires de la DHFRh hautement résistantes au MTX. Les variantes les plus intéressantes ont été testées pour leur potentiel en tant que marqueur de sélection dans plusieurs lignées cellulaires, dont les cellules hématopoïétiques transduites. Une protection complète contre les effets cytotoxiques du MTX a été observée chez ces cellules suite à leur infection avec les variantes combinatoires. Pour mieux comprendre les causes moléculaires reliées à la résistance au MTX, des études de structure tridimensionnelle de variantes liées au MTX ont été entreprises. La résolution de la structure de la double variante F31R/Q35E lié au MTX a révélé que le phénotype de résistance était attribuable à d’importantes différences entre le site actif de la double variante et de l’enzyme native, possiblement dû à un phénomème dynamique. Une compréhension plus générale de la reconnaissance et la résistance aux antifolates a été réalisée en comparant des séquences et des structures de variantes de la DHFR résistants aux antifolates et provenant de différentes espèces. En somme, ces travaux apportent de nouveaux éléments pour la comprehension des intéractions importantes entre une enzyme et un ligand, pouvant aider au développement de nouveaux antifolates plus efficaces pour le traitement de diverses maladies. De plus, ces travaux ont généré de nouveaux gènes de résistance pouvant être utilisés en tant que marqueurs de sélection en biologie cellulaire.

Le motif d’empaquetage le long du sillon: une nouvelle entité structurale récurrente dans les ARN ribosomiques

La plupart des molécules d’ARN doivent se replier en structure tertiaire complexe afin d’accomplir leurs fonctions biologiques. Cependant, les déterminants d’une chaîne de polynucléotides qui sont nécessaires à son repliement et à ses interactions avec d’autres éléments sont essentiellement inconnus. L’établissement des relations structure-fonction dans les grandes molécules d’ARN passe inévitablement par l’analyse de chaque élément de leur structure de façon individuelle et en contexte avec d’autres éléments. À l’image d’une construction d’immeuble, une structure d’ARN est composée d’unités répétitives assemblées de façon spécifique. Les motifs récurrents d’ARN sont des arrangements de nucléotides retrouvés à différents endroits d’une structure tertiaire et possèdent des conformations identiques ou très similaires. Ainsi, une des étapes nécessaires à la compréhension de la structure et de la fonction des molécules d’ARN consiste à identifier de façon systématique les motifs récurrents et d’en effectuer une analyse comparative afin d’établir la séquence consensus. L’analyse de tous les cas d’empaquetage de doubles hélices dans la structure du ribosome a permis l’identification d’un nouvel arrangement nommé motif d’empaquetage le long du sillon (AGPM) (along-groove packing motif). Ce motif est retrouvé à 14 endroits dans la structure du ribosome de même qu’entre l’ARN ribosomique 23S et les molécules d’ARN de transfert liées aux sites ribosomaux P et E. Le motif se forme par l’empaquetage de deux doubles hélices via leur sillon mineur. Le squelette sucre-phosphate d’une hélice voyage le long du sillon mineur de l’autre hélice et vice versa. Dans chacune des hélices, la région de contact comprend quatre paires de bases. L’empaquetage le plus serré est retrouvé au centre de l’arrangement où l’on retrouve souvent une paire de bases GU dans une hélice interagissant avec une paire de bases Watson-Crick (WC) dans l’autre hélice. Même si la présence des paires de bases centrales GU versus WC au centre du motif augmente sa stabilité, d’autres alternatives existent pour différents représentants du motif. L’analyse comparative de trois librairies combinatoires de gènes d’AGPM, où les paires de bases centrales ont été variées de manière complètement aléatoire, a montré que le contexte structural influence l’étendue de la variabilité des séquences de nucléotides formant les paires de bases centrales. Le fait que l’identité des paires de bases centrales puisse varier suggérait la présence d’autres déterminants responsables au maintien de l’intégrité du motif. L’analyse de tous les contacts entre les hélices a révélé qu’en dehors du centre du motif, les interactions entre les squelettes sucre-phosphate s’effectuent via trois contacts ribose-ribose. Pour chacun de ces contacts, les riboses des nucléotides qui interagissent ensemble doivent adopter des positions particulières afin d’éviter qu’ils entrent en collision. Nous montrons que la position de ces riboses est modulée par des conformations spécifiques des paires de bases auxquelles ils appartiennent. Finalement, un autre motif récurrent identifié à l’intérieur même de la structure de trois cas d’AGPM a été nommé « adenosine-wedge ». Son analyse a révélé que ce dernier est lui-même composé d’un autre arrangement, nommé motif triangle-NAG (NAG-triangle). Nous montrons que le motif « adenosine-wedge » représente un arrangement complexe d’ARN composé de quatre éléments répétitifs, c’est-à-dire des motifs AGPM, « hook-turn », « A-minor » et triangle-NAG. Ceci illustre clairement l’arrangement hiérarchique des structures d’ARN qui peut aussi être observé pour d’autres motifs d’ARN. D’un point de vue plus global, mes résultats enrichissent notre compréhension générale du rôle des différents types d’interactions tertiaires dans la formation des molécules d’ARN complexes.

Partager le savoir du lexicographe: extraction et modélisation ontologique des savoirs lexicographiques

Cette recherche porte sur la lexicologie, la lexicographie et l’enseignement/apprentissage du lexique. Elle s’inscrit dans le cadre du projet Modélisation ontologique des savoirs lexicographiques en vue de leur application en linguistique appliquée, surnommé Lexitation, qui est, à notre connaissance, la première tentative d’extraction des savoirs lexicographiques — i.e. connaissances déclaratives et procédurales utilisées par des lexicographes — utilisant une méthode expérimentale. Le projet repose sur le constat que les savoirs lexicographiques ont un rôle crucial à jouer en lexicologie, mais aussi en enseignement/apprentissage du lexique. Dans ce mémoire, nous décrirons les méthodes et les résultats de nos premières expérimentations, effectuées à l’aide du Think Aloud Protocol (Ericsson et Simon, 1993). Nous expliquerons l’organisation générale des expérimentations et comment les savoirs lexicographiques extraits sont modélisés pour former une ontologie. Finalement, nous discuterons des applications possibles de nos travaux en enseignement du lexique, plus particulièrement pour la formation des maîtres.

Algorithmes pour la réconciliation d’un arbre de gènes avec un arbre d’espèces

Une réconciliation entre un arbre de gènes et un arbre d’espèces décrit une histoire d’évolution des gènes homologues en termes de duplications et pertes de gènes. Pour inférer une réconciliation pour un arbre de gènes et un arbre d’espèces, la parcimonie est généralement utilisée selon le nombre de duplications et/ou de pertes. Les modèles de réconciliation sont basés sur des critères probabilistes ou combinatoires. Le premier article définit un modèle combinatoire simple et général où les duplications et les pertes sont clairement identifiées et la réconciliation parcimonieuse n’est pas la seule considérée. Une architecture de toutes les réconciliations est définie et des algorithmes efficaces (soit de dénombrement, de génération aléatoire et d’exploration) sont développés pour étudier les propriétés combinatoires de l’espace de toutes les réconciliations ou seulement les plus parcimonieuses. Basée sur le processus classique nommé naissance-et-mort, un algorithme qui calcule la vraisemblance d’une réconciliation a récemment été proposé. Le deuxième article utilise cet algorithme avec les outils combinatoires décrits ci-haut pour calculer efficacement (soit approximativement ou exactement) les probabilités postérieures des réconciliations localisées dans le sous-espace considéré. Basé sur des taux réalistes (selon un modèle probabiliste) de duplication et de perte et sur des données réelles/simulées de familles de champignons, nos résultats suggèrent que la masse probabiliste de toute l’espace des réconciliations est principalement localisée autour des réconciliations parcimonieuses. Dans un contexte d’approximation de la probabilité d’une réconciliation, notre approche est une alternative intéressante face aux méthodes MCMC et peut être meilleure qu’une approche sophistiquée, efficace et exacte pour calculer la probabilité d’une réconciliation donnée. Le problème nommé Gene Tree Parsimony (GTP) est d’inférer un arbre d’espèces qui minimise le nombre de duplications et/ou de pertes pour un ensemble d’arbres de gènes. Basé sur une approche qui explore tout l’espace des arbres d’espèces pour les génomes considérés et un calcul efficace des coûts de réconciliation, le troisième article décrit un algorithme de Branch-and-Bound pour résoudre de façon exacte le problème GTP. Lorsque le nombre de taxa est trop grand, notre algorithme peut facilement considérer des relations prédéfinies entre ensembles de taxa. Nous avons testé notre algorithme sur des familles de gènes de 29 eucaryotes.

Modèle de structuration des relations lexicales fondé sur le formalisme des fonctions lexicales

Thèse réalisée en cotutelle avec l'Université Paris Diderot (Paris 7)

Évaluation de deux méthodes d’identification des liens lexicaux : méthode manuelle et méthode statistique

Ce mémoire présente une évaluation des différentes méthodes utilisées en lexicographie afin d’identifier les liens lexicaux dans les dictionnaires où sont répertoriées des collocations. Nous avons ici comparé le contenu de fiches du DiCo, un dictionnaire de dérivés sémantiques et de collocations créé selon les principes de la lexicologie explicative et combinatoire, avec les listes de cooccurrents générées automatiquement à partir du corpus Le Monde 2002. Notre objectif est ici de proposer des améliorations méthodologiques à la création de fiches de dictionnaire du type du DiCo, c’est-à-dire, des dictionnaires d’approche qualitative, où la collocation est définie comme une association récurrente et arbitraire entre deux items lexicaux et où les principaux outils méthodologiques utilisés sont la compétence linguistique de ses lexicographes et la consultation manuelle de corpus de textes. La consultation de listes de cooccurrents est une pratique associée habituellement à une approche lexicographique quantitative, qui définit la collocation comme une association entre deux items lexicaux qui est plus fréquente, dans un corpus, que ce qui pourrait être attendu si ces deux items lexicaux y étaient distribués de façon aléatoire. Nous voulons mesurer ici dans quelle mesure les outils utilisés traditionnellement dans une approche quantitative peuvent être utiles à la création de fiches lexicographiques d’approche qualitative, et de quelle façon leur utilisation peut être intégrée à la méthodologie actuelle de création de ces fiches.

Études structurales d’interactions protéine/protéine impliquées dans l’érythropoïèse

Le développement hématopoïétique est régulé par l’action combinée de facteurs de transcription lignée spécifiques et de la machinerie transcriptionnelle de base, permettant ainsi l’expression de gènes en temps et lieu appropriés. Les travaux présentés dans cette thèse portent sur l’étude structurale et fonctionnelle d’interactions décisives pour la régulation de l’expression de gènes et impliquant des domaines de transactivation (TAD). En effet, les interactions faisant intervenir les TAD d’activateurs permettent de réguler l’activation de la transcription de façon spécifique. La première étude présentée dans cette thèse relate l'identification et la caractérisation d'une nouvelle interaction entre deux facteurs de transcription : le facteur hématopoïétique GATA-1 et la protéine suppresseur de tumeur p53. En combinant des études in vitro par titrage calorimétrique en condition isotherme (ITC) et par spectroscopie RMN et des études in vivo, nous avons identifié et caractérisé cette nouvelle interaction. Il s'avère que le TAD de p53 et le domaine de liaison à l’ADN de GATA-1 sont les domaines minimaux requis pour la formation de ce complexe. L'inhibition de la voie p53 par GATA-1 s’est avérée être la conséquence majeure de cette interaction, permettant ainsi le maintien en vie des précurseurs érythrocytaires via l’inhibition de l’apoptose. Un deuxième type d’interaction a fait l’objet d’études : l’interaction entre divers TAD et la machinerie transcriptionnelle de base, plus spécifiquement avec le Facteur général de Transcription IIH (TFIIH). La structure des complexes constitués par la sous-unité Tfb1/p62 du facteur TFIIH en interaction avec le TAD viral de VP16 d’une part, et avec le TAD humain du facteur érythrocytaire « Erythroid Krüppel-like factor» (EKLF) d’autre part, ont été résolues par spectroscopie RMN. La structure du complexe Tfb1/VP16 a révélée que le mode de liaison de VP16 à Tfb1 est similaire au mode de liaison du TAD de p53 avec le même partenaire. En effet, les TAD de VP16 et de p53 forment tous deux une hélice α de 9 résidus en interaction avec Tfb1. En dépit de partager avec p53 et VP16 le même site de liaison sur Tfb1/p62, la structure RMN du complexe EKLF/Tfb1 démontre que le mode d’interaction de ce TAD se distingue du mode de liaison canonique des activeurs transcriptionnels. Etonnamment, EKLF adopte un mécanisme de liaison semblable au mécanisme de liaison du facteur général de transcription TFIIEα avec p62, leurs conformations demeurent étendues en interaction avec Tfb1/p62. En se basant sur nos données structurales, nous avons identifié un résidu dans le TAD d'EKLF décisif pour la formation du complexe EKLF/p62 : le Trp73. La mutation de cet acide aminé perturbe son interaction avec Tfb1PH/p62PH et réduit significativement l'activité transcriptionnelle d'EKLF dans les érythrocytes.

Représentations du sens lexical en lexicologie explicative et combinatoire : étude de trois formalisations spécifiques

Cette étude porte sur les différentes formalisations du sens linguistique dans le cadre de la théorie Sens-Texte (TST) ; elle s’intéresse notamment à la représentation sémantique, la représentation la plus importante dans la modélisation du sens d’énoncés et d’unités lexicales de la langue. Cette étude a trois objectifs : premièrement, décrire trois formalisations de la représentation sémantique existant dans la TST – les réseaux sémantiques, les définitions lexicographiques et les définitions de la BDéf (des définitions très formalisées) ; deuxièmement, identifier les disparités et les décalages entre les formalisations choisies ; troisièmement, proposer des modifications aux formalisations existantes pour réduire au maximum ces disparités.

A lexical semantic study of Dene Suliné, an Athabaskan language

Cette thèse constitue une étude systématique du lexique du déné sųłiné, une langue athabaskane du nord-ouest canadien. Elle présente les définitions et les patrons de combinatoire syntaxique et lexicale de plus de 200 unités lexicales, lexèmes et phrasèmes, qui représentent une partie importante du vocabulaire déné sųłiné dans sept domaines: les émotions, le caractère humain, la description physique des entités, le mouvement des êtres vivants, la position des entités, les conditions atmospheriques et les formations topologiques, en les comparant avec le vocubulaire équivalent de l'anglais. L’approche théorique choisie est la Théorie Sens-Texte (TST), une approche formelle qui met l’accent sur la description sémantique et lexicographique empiriques. La présente recherche relève d'importantes différences entre le lexique du déné sųłiné et celui de l'anglais à tous les niveaux: dans la correspondence entre la représentation conceptuelle, considérée (quasi-)extralinguistique, et la structure sémantique; dans les patrons de lexicalisation des unités lexicales, et dans les patrons de combinatoire syntaxique et lexicale, qui montrent parfois des traits propres au déné sųłiné intéressants.