Dissertations / Theses on the topic 'Combinatorial nature'

Depuis plus de 80 ans, le métabolisme spécialisé nous fournit de nombreuses molécules utilisées en médecine, en particulier comme anti-infectieux. Aujourd’hui, avec l’augmentation mondiale de la résistance aux antimicrobiens, de nouveaux antibiotiques sont indispensables. Une des réponses à cette pénurie grave pourrait provenir de la biologie synthétique. Dans le domaine du métabolisme spécialisé, la biologie synthétique est utilisée en particulier pour la biosynthèse de métabolites non naturels. Parmi les métabolites spécialisés, les peptides non ribosomiques constituent une cible attrayante, car ils nous ont déjà fourni des molécules à haute valeur clinique (ex. les antibiotiques vancomycine et daptomycine). De plus, la plupart sont synthétisés par des enzymes multimodulaires appelées synthétases de peptides non ribosomiques (NRPS), et sont diversifiés davantage par des enzymes de décoration. Ainsi, ces voies de biosynthèse se prêtent particulièrement à la biosynthèse combinatoire, consistant à combiner des gènes de biosynthèse provenant de divers groupes de gènes ou, dans le cas des NRPS, à combiner des modules ou domaines pour créer de nouvelles enzymes. Cependant, si plusieurs études ont établi la faisabilité de telles approches, de nombreux obstacles subsistent avant que les approches combinatoires de biosynthèse soient totalement efficaces pour la synthèse de nouveaux métabolites. Les travaux présentés ici s’inscrivent dans le cadre d’un projet visant à comprendre les facteurs limitant les approches de biosynthèse combinatoire basées sur les NRPS, en utilisant une approche de biologie synthétique. Nous avons choisi de travailler avec les NRPS responsables de la biosynthèse des pyrrolamides. En effet, ces NRPS sont constitués uniquement de modules et de domaines autonomes, et donc particulièrement adaptés aux manipulations génétiques et biochimiques. La caractérisation du groupe de gènes de biosynthèse du pyrrolamide anthelvencine constitue la première partie de cette thèse et nous a fourni de nouveaux gènes pour notre étude. La deuxième partie a consisté à construire de vecteurs intégratifs modulaires, outils essentiels pour la construction et l’assemblage de cassettes génétiques. La dernière partie présente la reconstruction du groupe de gènes du pyrrolamide congocidine, basée sur la construction et l’assemblage de cassettes de gènes synthétiques. Dans l’ensemble, ces travaux ouvrent la voie à de futures expériences de biosynthèse combinatoire, expériences qui devraient contribuer à une meilleure compréhension du fonctionnement précis des NRPS
For more than 80 years, specialized metabolism has provided us with many molecules used in medicine, especially as anti-infectives. Yet today, with the rise of antimicrobial resistance worldwide, new antibiotics are crucially needed. One of the answers to this serious shortage could arise from synthetic biology. In the field of specialized metabolism, synthetic biology is used in particular to biosynthesize unnatural metabolites. Among specialized metabolites, non-ribosomal peptides constitute an attractive target as they have already provided us with clinically valuable molecules (e.g. the vancomycin and daptomycin antibiotics). In addition, most are synthesized by multimodular enzymes called non-ribosomal peptide synthetases (NRPS) and further diversified by tailoring enzymes. Thus, such biosynthetic pathways are particularly amenable to combinatorial biosynthesis, which consists in combining biosynthetic genes coming from various gene clusters or, in the case of NRPSs, combining modules or domains to create a new enzyme. Yet, if several studies have established the feasibility of such approaches, many obstacles remain before combinatorial biosynthesis approaches are fully effective for the synthesis of new metabolites. The work presented here is part of a project aiming at understanding the limiting factors impeding NRPS-based combinatorial biosynthesis approaches, using a synthetic biology approach. We chose to work with the NRPSs involved in the biosynthesis of pyrrolamides. Indeed, these NRPS are solely constituted of stand-alone modules and domains, and thus, particularly amenable to genetic and biochemical manipulations. The characterization of the biosynthetic gene cluster of the pyrrolamide anthelvencin constitutes the first part of this thesis, and provided us with new genes for our study. The second part involved the construction of modular integrative vectors, essential tools for the construction and assembly of gene cassettes. The final part presents the successful refactoring of the congocidine pyrrolamide gene cluster, based on the construction and assembly of synthetic gene cassettes. Altogether, this work paves the way for future combinatorial biosynthesis experiments that should help deciphering the detailed functioning of NRPSs

Submitted by Fabio Sobreira Campos da Costa (fabio.sobreira@ufpe.br) on 2017-04-24T14:03:12Z No. of bitstreams: 2 license_rdf: 1232 bytes, checksum: 66e71c371cc565284e70f40736c94386 (MD5) dissertacao-mestrado.pdf: 2772669 bytes, checksum: 25b575026c012270168ca5a4c397d063 (MD5)
Made available in DSpace on 2017-04-24T14:03:12Z (GMT). No. of bitstreams: 2 license_rdf: 1232 bytes, checksum: 66e71c371cc565284e70f40736c94386 (MD5) dissertacao-mestrado.pdf: 2772669 bytes, checksum: 25b575026c012270168ca5a4c397d063 (MD5) Previous issue date: 2015-07-29
CNPQ
N-Graphs is a multiple conclusion natural deduction with proofs as directed graphs, motivated by the idea of proofs as geometric objects and aimed towards the study of the geometry of Natural Deduction systems. Following that line of research, this work revisits the system under a purely combinatorial perspective, determining geometrical conditions on the graphs of proofs to explain its soundness criterion and proof growth during normalization. Applying recent developments in the fields of proof graphs, proof-nets and N-Graphs itself, we propose a linear time algorithm for proof verification of the full system, a result that can be related to proof-nets solutions from Murawski (2000) and Guerrini (2011), and a normalization procedure based on the notion of sub-N-Graphs, introduced by Carvalho, in 2014. We first present a new soundness criterion for meta-edges, along with the extension of Carvalho’s sequentization proof for the full system. For this criterion we define an algorithm for proof verification that uses a DFS-like search to find invalid cycles in a proof-graph. Since the soundness criterion in proof graphs is analogous to the proof-nets procedure, the algorithm can also be extended to check proofs in the multiplicative linear logic without units (MLL−) with linear time complexity. The new normalization proposed here combines a modified version of Alves’ (2009) original beta and permutative reductions with an adaptation of Carbone’s duplication operation on sub-N-Graphs. The procedure is simpler than the original one and works as an extension of both the normalization defined by Prawitz and the combinatorial study developed by Carbone, i.e. normal proofs enjoy the separation and subformula properties and have a structure that can represent how patterns lying in normal proofs can be recovered from the graph of the original proof with cuts.
N-Grafos é uma dedução natural de múltiplas conclusões onde provas são representadas como grafos direcionados, motivado pela idéia de provas como objetos geométricos e com o objetivo de estudar a geometria de sistemas de Dedução Natural. Seguindo esta linha de pesquisa, este trabalho revisita o sistema sob uma perpectiva puramente combinatorial, determinando condições geométricas nos grafos de prova para explicar seu critério de corretude e crescimento da prova durante a normalização. Aplicando desenvolvimentos recentes nos campos de grafos de prova, proof-nets e dos próprios N-Grafos, propomos um algoritmo linear para verificação de provas para o sistema completo, um resultado que pode ser comparado com soluções para roof-nets desenvolvidas por Murawski (2000) e Guerrini (2011), e um procedimento de normalização baseado na noção de sub-N-Grafos, introduzidas por Carvalho, em 2014. Apresentamos primeiramente um novo critério de corretude para meta-arestas, juntamente com a extensão para todo o sistema da prova da sequentização desenvolvida por Carvalho. Para este critério definimos um algoritmo para verificação de provas que utiliza uma busca parecida com a DFS (Busca em Profundidade) para encontrar ciclos inválidos em um grafo de prova. Como o critério de corretude para grafos de provas é análogo ao procedimento para proof-nets, o algoritmo pode também ser estendido para validar provas em Lógica Linear multiplicativa sem units (MLL−) com complexidade de tempo linear. A nova normalização proposta aqui combina uma versão modificada das reduções beta e permutativas originais de Alves com uma adaptação da operação de duplicação proposta por Carbone para ser aplicada a sub-N-Grafos. O procedimento é mais simples do que o original e funciona como uma extensão da normalização definida por Prawitz e do estudo combinatorial desenvolvido por Carbone, i.e. provas em forma normal desfrutam das propriedades da separação e subformula e possuem uma estrutura que pode representar como padrões existentes em provas na forma normal poderiam ser recuperados a partir do grafo da prova original com cortes.

In the last decade, dynamic combinatorial mass spectrometry (DCMS) with protein targets has emerged as a promising method for the identification of enzyme-inhibitors. 2-Oxoglutarate (2OG) oxygenases are involved in important biological processes related to many diseases; several human 2OG oxygenases are targeted for pharmaceutical intervention. This thesis describes inhibition studies on three 2OG oxygenases using DCMS and structure activity relation (SAR) studies. Disulphide based DCMS was used for the identification of N-oxalyl based lead inhibitors for the 2OG oxygenase AlkB from Escherichia coli. Crystallographic analyses of AlkB with a lead inhibitor assisted in the design of a second generation of inhibitors using N-oxalyl, pyridyl and quinolinyl scaffolds. Crystallographic and kinetic data of three potent and selective AlkB inhibitors validates the DCMS approach for the development of 2OG oxygenase inhibitors. The hypoxia inducible factor hydroxylase, prolyl hydroxylase domain 2 (PHD2), was then used as the model enzyme for the development of a novel DCMS approach employing the reversible reaction of boronic acids with diols to form boronate esters. The ‘boronate’ DCMS method was used to identify pyridyl- substituted lead compounds. Further modification of the pyridine scaffold, based on structural analyses, led to the development of highly potent and selective PHD2 inhibitors. To identify inhibitors for the fat mass and obesity associated protein (FTO), another 2OG oxygenase, an inhibition assay was developed. The inhibition assay was used in conjunction with a differential scanning fluorimetry (DSF) binding assay to identify isoquinolinyl and pyridyl inhibitor scaffolds, related to those used in the DCMS studies. FTO complexed structures of these compounds, and with a natural product anthraquinone, enabled the design and synthesis of new inhibitors that are both co-substrate and substrate competitors of FTO. One such compound proved to be a potent FTO inhibitor with improved selectivity over other 2OG oxygenases. Overall, the work validates the use of DCMS methods for the development of potent and selective inhibitors for 2OG oxygenases, and by implication of other enzyme families.

Cyanobacteria produce a myriad of structurally unique secondary metabolites with useful bioactive properties. Heterologous expression of a variety of microbial natural compounds has been used to harness their diversity and facilitate their combinatorial biosynthesis. However, these genetic techniques have not been developed for secondary metabolite-producing cyanobacteria. Therefore the genetically manipulable Escherichia coli and Synechocystis sp. PCC6803 were engineered in order to develop effective heterologous hosts and promoters for the expression of cyanobacterial-derived compounds. The phosphopanthetheinyl transferase (PPT), Sppt, from Synechocystis sp. PCC6803 was characterised to determine its ability to activate carrier proteins from secondary metabolite pathways. Despite in silico evidence which suggested Sppt was able to activate a wide range of carrier proteins, biochemical analysis revealed that it is dedicated for fatty acid synthesis. Consequently, E. coli and Synechocystis sp. PCC6803 were engineered to encode a broad-range PPT, from the filamentous cyanobacteria Nodularia spumigena NSOR10, for the activation of carrier proteins from nonribosomal peptide synthesis. Cyanobacterial natural product engineering was also explored with the characterisation of two relaxed specificity adenylation domains (A-domains) from the biosynthetic pathway of the toxin microcystin. The wide variety of microcystin compounds produced by cyanobacterial species suggests that multiple amino acids can be activated by the same A-domain. This was supported by preliminary ATP-[32P]PPi exchange assays and was subsequently harnessed in the production of a variety of dipeptides using two reconstituted modules in vitro. Transposition was investigated as a potential mechanism for the transfer of nonribosomal peptide synthetase gene clusters to heterologous hosts. This was performed via the characterisation of the putative transposase, Mat, physically linked with the microcystin synthetase gene cluster (mcyS). PCR screening, in silico analysis and nitrocellulose filter binding assays indicated that this transposase may have mediated mcyS gene cluster rearrangements but not entire gene cluster mobilisation between species. The potential role of transposases in the natural combinatorial biosynthesis of microcystin has evolutionary implications for the dynamic nature of cyanobacterial genomes and applications for use in the engineering of novel bioactive compounds. Therefore, the results from this study may provide a biotechnological platform for the transfer, expression and combinatorial biosynthesis of novel cyanobacterial-derived natural products.

Made available in DSpace on 2014-06-12T16:01:15Z (GMT). No. of bitstreams: 2 arquivo7278_1.pdf: 2063761 bytes, checksum: eaeb6780fe875052548e747b8a3af1a9 (MD5) license.txt: 1748 bytes, checksum: 8a4605be74aa9ea9d79846c1fba20a33 (MD5) Previous issue date: 2005
A regulação gênica está intimamente ligada com a transcrição de proteínas, e esse mecanismo é muito importante para o desenvolvimento dos seres vivos, pois é através dele que os organismos conseguem sintetizar proteínas. Um interessante problema da biologia moderna é o entendimento de mecanismos da regulação da transcrição. Muitos aspectos dessa regulação envolvem fatores de transcrição (proteínas ligantes ao DNA). Esses fatores regulam a expressão gênica pela conexão em posições específicas de regiões do genoma (conjunto de genes de uma espécie) que podem estar próximas ou não, como veremos em maiores detalhes oportunamente. Os fatores de transcrição conectam-se a subseqüências especificas de DNA, os promotores, que podem, com dificuldade, ser determinados por análises biológicas. Esse alto grau de dificuldade motiva os cientistas a procurarem meios computacionais mais rápidos e eficientes para solucionar o problema da busca pelos sítios de ligação dos promotores. O crescente aumento da disponibilidade de seqüências completas de genoma motiva tentativas de entender e modelar o mecanismo regulatório através de análises computacionais. A identificação de sítios de ligação envolve duas etapas principais: aprender modelos de sítios de ligação e buscar sítios em novas seqüências. Parte do trabalho foi desenvolver uma ferramenta para auxiliar os cientistas na busca por essas regiões especiais, os motifs, no genoma. Como desenvolvemos essa ferramenta usando Java, combinamos o fonema inglês da letra "J" com o sufixo "nom" da palavra "genom" para compor o nome da ferramenta e a chamamos de Jnom. A primeira tarefa é aprender modelos de sítios de ligação em potencial em um dado genoma. Usam-se exemplos de sítios de ligação verificados biologicamente e tenta-se encontrar sítios similares em outras regiões promotoras. Em seguida, é necessário descobrir uma seqüência de motifs em uma coleção de longas seqüências que são supostamente ligadas pelo mesmo fator. Neste caso, um motif encontrado indica um possível fator desconhecido que regula o conjunto de genes. A natureza combinatória dos fatores de transcrição é o mecanismo pelo qual as células dos seres superiores (eucariotes) atuam para controlar a expressão de conjuntos inteiros de genes. A intenção deste trabalho é investigar essa natureza combinante e tentar utilizar esse fato para melhorar o desempenho em relação a ferramentas existentes. O principal objetivo dessa pesquisa é construir uma ferramenta capaz de considerar a ação combinada dos fatores de transcrição através da seqüência de genes para encontrar novos motifs a partir de alguns já conhecidos

Orientador: Jacques Wainer
Tese (doutorado) - Universidade Estadual de Campinas, Instituto de Computação
Made available in DSpace on 2018-08-24T00:42:33Z (GMT). No. of bitstreams: 1 Passos_AlexandreTachard_D.pdf: 2615030 bytes, checksum: 93841a46120b968f6da6c9aea28953b7 (MD5) Previous issue date: 2013
Resumo: Em processamento de linguagem natural, e em aprendizado de máquina em geral, é comum o uso de modelos gráficos probabilísticos (probabilistic graphical models). Embora estes modelos sejam muito convenientes, possibilitando a expressão de relações complexas entre várias variáveis que se deseja prever dado uma sentença ou um documento, algoritmos comuns de aprendizado e de previsão utilizando estes modelos são frequentemente ineficientes. Por isso têm-se explorado recentemente o uso de relaxações usando programação linear deste problema de inferência. Esta tese apresenta duas contribuições para a teoria e prática de relaxações de programação linear para inferência em modelos probabilísticos gráficos. Primeiro, apresentamos um novo algoritmo, baseado na técnica de geração de colunas (dual à técnica dos planos de corte) que acelera a execução do algoritmo de Viterbi, a técnica mais utilizada para inferência em modelos lineares. O algoritmo apresentado também se aplica em modelos que são árvores e em hipergrafos. Em segundo mostramos uma nova relaxação linear para o problema de inferência conjunta, quando se quer acoplar vários modelos, em cada qual inferência é eficiente, mas em cuja junção inferência é NP-completa. Esta tese propõe uma extensão à técnica de decomposição dual (dual decomposition) que permite além de juntar vários modelos a adição de fatores que tocam mais de um submodelo eficientemente
Abstract: In natural language processing, and in general machine learning, probabilistic graphical models (and more generally structured linear models) are commonly used. Although these models are convenient, allowing the expression of complex relationships between many random variables one wants to predict given a document or sentence, most learning and prediction algorithms for general models are inefficient. Hence there has recently been interest in using linear programming relaxations for the inference tasks necessary when learning or applying these models. This thesis presents two contributions to the theory and practice of linear programming relaxations for inference in structured linear models. First we present a new algorithm, based on column generation (a technique which is dual to the cutting planes method) to accelerate the Viterbi algorithm, the most popular exact inference technique for linear-chain graphical models. The method is also applicable to tree graphical models and hypergraph models. Then we present a new linear programming relaxation for the problem of joint inference, when one has many submodels and wants to predict using all of them at once. In general joint inference is NP-complete, but algorithms based on dual decomposition have proven to be efficiently applicable for the case when the joint model can be expressed as many separate models plus linear equality constraints. This thesis proposes an extension to dual decomposition which allows also the presence of factors which score parts that belong in different submodels, improving the expressivity of dual decomposition at no extra computational cost
Doutorado
Ciência da Computação
Doutor em Ciência da Computação

Orientadores: Cid Carvalho de Souza, Pedro Jussieu de Rezende
Dissertação (mestrado) - Universidade Estadual de Campinas, Instituto de Computação
Made available in DSpace on 2018-08-26T19:18:58Z (GMT). No. of bitstreams: 1 Crepaldi_BrunoEspinosa_M.pdf: 13275684 bytes, checksum: aa236e6a56dd7ed5507276017c51b8fb (MD5) Previous issue date: 2014
Resumo: Considerado uma variação do problema da galeria de arte, o problema do posicionamento de antenas trata do posicionamento do menor número de antenas requerido para determinar se uma pessoa está dentro ou fora da galeria. Uma antena propaga uma chave única dentro de um ângulo específico de transmissão, de modo que o conjunto de chaves recebidas em um dado ponto do plano seja suficiente para decidir se ele pertence ou não ao polígono que representa a galeria. Para verificar esta propriedade de localização, uma fórmula Booleana deve ser produzida junto com o posicionamento de antenas. Dizemos que as antenas estão em posição natural se elas estão localizadas nos vértices ou nas arestas do polígono e transmitindo sinal no ângulo formado pelos lados deste último no ponto onde a antena está posicionada. O problema do posicionamento natural de antenas é NP-difícil. Nesta dissertação, apresentamos um algoritmo exato para resolvê-lo. Para tanto, propomos um modelo inicial de programação linear inteira para o problema que, ao ser computado por um resolvedor comercial, se mostrou capaz de encontrar soluções ótimas de instâncias correspondentes a polígonos com algumas dezenas de vértices. Em seguida, através de estudos de propriedades geométricas, são introduzidas várias melhorias no modelo matemático e também na forma de computá-lo. Como consequência desta pesquisa, desenvolvemos um algoritmo iterativo baseado em programação linear inteira com o qual conseguimos solucionar o problema para instâncias consideravelmente maiores. A eficiência do nosso algoritmo é certificada por resultados experimentais que compreendem as soluções ótimas de 720 instâncias de até 1000 vértices, incluindo polígono com buracos, as quais foram calculadas em menos de seis minutos em um computador desktop padrão
Abstract: Considered a variation of the art gallery problem, the wireless localization problem deals with the placement of the smallest number of broadcasting antennas required to determine if someone is inside or outside the gallery. Each antenna propagates a unique key within a certain antenna-specific angle of broadcast, so that the set of keys received at any given point is sufficient to determine whether that point is inside or outside the polygon that represents the gallery. To ascertain this localization property, a Boolean formula must be produced along with the placement of the antennas. We say that the antennas are in natural position if they are located at the vertices or the edges of the polygon and transmitting their signals in the angle formed by the sides of the polygon at the point where the antenna is positioned. The natural wireless localization problem is NP-hard. In this dissertation, we present an exact algorithm to solve it. To this end, we propose an initial integer linear programming model for the problem that, after being computed by a commercial solver, proved to be capable of finding optimal solutions for instances corresponding to polygons with tens of vertices. Then, through studies of geometric properties, several improvements are introduced in the mathematical model and also in the way of computing it. As a result of this research, we develop an iterative algorithm based on integer linear programming with which we can solve the problem for considerably larger instances. The efficiency of our algorithm is certified by experimental results comprising the solutions of 720 instances, including polygon with holes with up to 1000 vertices, in less than six minutes on a standard desktop computer
Mestrado
Ciência da Computação
Mestre em Ciência da Computação

Utiliser la liaison peptidique dans des systèmes dynamiques covalents est très difficile en raison de sa stabilité intrinsèque. Dans ce travail, une nouvelle méthodologie pour échanger fragments peptidiques dans des conditions biocompatibles est décrite. Légères modifications du groupe amine d'un résidu de cystéine en peptides modèle permettent l'activation spécifique de cette jonction peptidique pour des réactions d'échange covalent. Grâce à un mécanisme de ligation chimique native réversible, fragments peptidiques sont échangés en solution aqueuse à pH physiologique et en présence de dithiothréitol (DTT), avec des demi-temps d'équilibration de 2 à 10 heures. Différentes possibles applications biologiques de cette nouvelle réaction réversible à peptides et glycopeptides sont aussi proposées
The possibility to use the peptide bond in dynamic covalent systems is very challenging because of its intrinsic stability. In this work, a novel methodology to exchange peptide fragments in bio-compatible conditions is described. The introduction of small modifications to the N-terminus of a cysteine residue in model peptides allows for the specific activation of that peptide bond for exchange reactions. Through a reverse Native Chemical Ligation (NCL) mechanism, peptide fragments were scrambled in aqueous solution at physiological pH and in the presence of dithiothreitol (DTT), with half-times of equilibration in the 2-10 h range. Additionally, possible biological applications of this new reversible reaction to both peptides and glycopeptides are proposed

Submitted by Maicon Juliano Schmidt (maicons) on 2015-03-30T11:51:21Z No. of bitstreams: 1 Carlos Eduardo de Jesus Guimarães Oliveira.pdf: 1236896 bytes, checksum: ef9d04e6f25aee7908b56a622411bc74 (MD5)
Made available in DSpace on 2015-03-30T11:51:21Z (GMT). No. of bitstreams: 1 Carlos Eduardo de Jesus Guimarães Oliveira.pdf: 1236896 bytes, checksum: ef9d04e6f25aee7908b56a622411bc74 (MD5) Previous issue date: 2014-01-31
Nenhuma
Este trabalho apresenta um algoritmo de otimização baseado na metaheurística dos Sistemas Imunológicos Artificiais, princípios de Teoria dos Jogos, Co-evolução e Paralelização. Busca-se a combinação adequada dos conceitos de Teoria dos Jogos, Co-evolução e Paralelização aplicados ao algoritmo AISO (Artificial Immune System Optimization) para resolução do Problema de Alocação de Berços (PAB). Dessa maneira, o algoritmo é formalizado a partir das técnicas citadas, formando o PCAISO-GT: Parallel Coevolutionary Artificial Immune System Optimization with Game Theory. Inicialmente, foram realizados experimentos visando à sintonia dos parâmetros empregados nas diferentes versões da ferramenta desenvolvida. Com base nas melhores configurações identificadas, foram realizados experimentos de avaliação através da solução de um conjunto de instâncias do PAB. Os resultados obtidos permitiram a indicação da versão co-evolutiva associada à teoria dos jogos como a melhor para solução do problema em estudo.
This paper presents an optimization algorithm based on metaheuristic of Artificial Immune Systems, principles of Game Theory, Co-evolution and parallelization. The objective is find the appropriate combination of the concepts of Game Theory, Co-evolution and Parallelization applied to AISO algorithm (Artificial Immune System Optimization) for solving the Berth Allocation Problem (BAP). Thus, the algorithm is formalized from the above mentioned techniques, forming the PCAISO-GT: Parallel Coevolutionary Artificial Immune System Optimization with Game Theory. Initially, experiments aiming to tune the parameters were performed using different versions of the tool developed. Based on the identified best settings, evaluation experiments were carried out by solving a set of instances of the PAB. The results obtained allowed the appointment of co-evolutionary version associated with game theory as the best solution to the problem under study.

Le traitement informatique des objets qui nous entourent, naturels ou créés par l'homme, demande toujours de passer par une phase de traduction en entités traitables par des programmes. Le choix de ces représentations abstraites est toujours crucial pour l'efficacité des traitements et est le terrain d'améliorations constantes. Mais il est un autre aspect émergeant : le lien entre l'objet à représenter et "sa" représentation n'est pas forcément bijectif ! Ainsi la nature ambiguë de certaines structures discrètes pose problème pour la modélisation ainsi que le traitement et l'analyse à l'aide d'un programme informatique. Le langage dit ``naturel'', et sous sa forme en particulier de représentation textuelle, en est un exemple. Le sujet de cette thèse consiste à explorer cette question, que nous étudions à l'aide de méthodes combinatoires et géométriques. Ces méthodes nous permettent de formaliser le problème d'extraction d'information dans des grands réseaux d'entités ainsi que de construire des représentations géométriques utiles pour le traitement du langage naturel. Dans un premier temps, nous commençons par démontrer des propriétés combinatoires des graphes de séquences intervenant de manière implicite dans les modèles séquentiels. Ces propriétés concernent essentiellement le problème inverse de trouver une séquence représentant un graphe donné. Les algorithmes qui en découlent nous permettent d'effectuer une comparaison expérimentale de différents modèles séquentiels utilisés en modélisation du langage. Dans un second temps, nous considérons une application pour le problème d'identification d'entités nommées. A la suite d'une revue de solutions récentes, nous proposons une méthode compétitive basée sur la comparaison de structures de graphes de connaissances et moins coûteuse en annotations d'exemples dédiés au problème. Nous établissons également une analyse expérimentale d'influence d'entités à partir de relations capitalistiques. Cette analyse suggère l'élargissement du cadre d'application de l'identification d'entités à des bases de connaissances de natures différentes. Ces solutions sont aujourd'hui utilisées au sein d'une librairie logicielle dans le secteur bancaire. Ensuite, nous développons une étude géométrique de représentations de mots récemment proposées, au cours de laquelle nous discutons une conjecture géométrique théoriquement et expérimentalement. Cette étude suggère que les analogies du langage sont difficilement transposables en propriétés géométriques, et nous amène a considérer le paradigme de la géométrie des distances afin de construire de nouvelles représentations. Enfin, nous proposons une méthodologie basée sur le paradigme de la géométrie des distances afin de construire de nouvelles représentations de mots ou d'entités. Nous proposons des algorithmes de résolution de ce problème à grande échelle, qui nous permettent de construire des représentations interprétables et compétitives en performance pour des tâches extrinsèques. Plus généralement, nous proposons à travers ce paradigme un nouveau cadre et piste d'explorations pour la construction de représentations en apprentissage machine
The automated treatment of familiar objects, either natural or artifacts, always relies on a translation into entities manageable by computer programs. The choice of these abstract representations is always crucial for the efficiency of the treatments and receives the utmost attention from computer scientists and developers. However, another problem rises: the correspondence between the object to be treated and "its" representation is not necessarily one-to-one! Therefore, the ambiguous nature of certain discrete structures is problematic for their modeling as well as their processing and analysis with a program. Natural language, and in particular its textual representation, is an example. The subject of this thesis is to explore this question, which we approach using combinatorial and geometric methods. These methods allow us to address the problem of extracting information from large networks of entities and to construct representations useful for natural language processing.Firstly, we start by showing combinatorial properties of a family of graphs implicitly involved in sequential models. These properties essentially concern the inverse problem of finding a sequence representing a given graph. The resulting algorithms allow us to carry out an experimental comparison of different sequential models used in language modeling.Secondly, we consider an application for the problem of identifying named entities. Following a review of recent solutions, we propose a competitive method based on the comparison of knowledge graph structures which is less costly in annotating examples dedicated to the problem. We also establish an experimental analysis of the influence of entities from capital relations. This analysis suggests to broaden the framework for applying the identification of entities to knowledge bases of different natures. These solutions are used today in a software library in the banking sector.Then, we perform a geometric study of recently proposed representations of words, during which we discuss a geometric conjecture theoretically and experimentally. This study suggests that language analogies are difficult to transpose into geometric properties, and leads us to consider the paradigm of distance geometry in order to construct new representations.Finally, we propose a methodology based on the paradigm of distance geometry in order to build new representations of words or entities. We propose algorithms for solving this problem on some large scale instances, which allow us to build interpretable and competitive representations in performance for extrinsic tasks. More generally, we propose through this paradigm a new framework and research leadsfor the construction of representations in machine learning