Actuellement, les technologies de séquençage ne permettent de lire la séquence d'un génome entier d'un individu, mais donnent les séquences de portions courtes de ce génome avec des erreurs. On doit ensuite procéder à un assemblage de ces séquences (que l'on appelle lectures ou "read" en anglais) pour retrouver la séquence du génome complet. Une version théorique de cette problématique est le problème de la plus courte superchaîne: étant donné un ensemble de mots (notre ensemble de lectures), on cherche à trouver le plus petit mot qui contient tous les autres comme sous-chaîne (le génome d'origine). Ce problème étudié depuis les années 60 est notoirement difficile à résoudre de manière exacte et approchée.L'assemblage nécessite certains pré-traitements des lectures, comme par exemple la correction des erreurs dues au séquençage dans les lectures (au sens où on cherche à enlever les erreurs). Certains logiciels de correction (ou d'autres pré-traitements) utilisent une structure d'indexation des séquences pour repérer les erreurs. Or, après la correction, cette structure de données est perdue et l'assemblage n'utilise plus que les lectures corrigées. Dans cette thèse, on se demande comment utiliser les structures d'indexation pour faciliter ou améliorer la qualité de l'assemblage.Dans un premier temps, on a montré qu'à partir d'une structure d'indexation, on pouvait rapidement reconstruire les graphes utilisés dans les algorithmes d'assemblage (graphe de Bruijn, graphe de Bruijn contracté, graphe de chevauchements). De plus, on a mis en évidence un nouveau graphe, le graphe hiérarchique de chevauchements ou "Hierarchical Overlap Graph", qui résume les informations des graphes classiques de l'assemblage.Dans un deuxième temps, on s'est demandé comment une structure d'indexation pouvait aider à résoudre directement le problème théorique de la plus courte superchaîne. Pour cela, on a étudié les solutions que l'algorithme glouton donnait à ce problème (leur approximation, leur combinatoire, ...) et à plusieurs de ces variantes (cas des mots renversés et complémentaires, cas de superchaîne cyclique, cas de couverture par un ensemble de superchaînes). Ceci a permis de résoudre plusieurs questions concernant la complexité et l'approximabilité de ces problèmes. En particulier, l'algorithme glouton permet de résoudre en temps linéaire la question de la plus petite couverture par des chaînes cycliques. Même si l'algorithme glouton est le plus simple et un des plus étudiés pour ces problèmes, il n'en reste pas moins un mystère. Notre étude a permis de mettre en évidence un nouveau graphe, le graphe des superchaînes ou "Superstring Graph", qui correspond à un plongement des solutions de l'algorithme glouton dans la structure d'indexation qu'est l'arbre des suffixes. Autrement dit, le graphe des superchaînes synthétise l'ensemble des solutions gloutonnes dans un espace linéaire.Enfin, on s'est intéressé aux algorithmes des meilleurs assembleurs utilisés en pratique (IDBA, SPAdes) qui ont permis d'améliorer l'assemblage de lectures courtes en utilisant plusieurs graphes d'assemblage. Nous avons montré tout d'abord que le graphe des superchaînes permet de stocker plus d'informations que ces assembleurs et avec une complexité en espace bien plus faible. Ensuite, il ressort que l'algorithme glouton pour une variante du problème de plus courte superchaîne donne des séquences qui incluent les contigs trouvés pour ces algorithmes. Ces résultats permettent de lier l'assemblage pratique et les problèmes de superchaînes, et donnent un cadre théorique fort pour étudier ces algorithmes heuristiques. / Whole genome can not be read by the current sequencing technologies. Instead, the output is short sequences which are portions with errors of the whole genome. One must then proceed to an assembly of these sequences (called read) to find the sequence of the complete genome. A theoretical version of this problem is the problem of the shortest superstring: given a set of words (own set of reads), we try to find the shortest string that contains all others as substring (the genome of origin). Studied since the 60s, this problem is notoriously difficult to solve by both exactly and approximate methods.Genome assembly requires some reads preprocessing, such as the correction of errors introduced by the sequencing. Some correction softwares (or other pre-treatments) use an indexing data structure of the sequences to localize errors. However, after the correction, this data structure is lost and the assembly uses only the corrected reads. In this thesis, we wonder how to use indexing structures to facilitate or to improve the quality of the genome assembly.First, we show that the graphs used in assembly algorithms could quickly rebuild from an indexing structure (de Bruijn graph, contracted de Bruijn graph and overlap graph). In addition, we present a new graph which summarizes the information of conventional assembly graphs and that we call the hierarchical overlap graph.Secondly, we wondered how an indexing data structure could directly help to solve the theoretical problem of the shortest superstring. For this purpose, we study the solutions that the greedy algorithm gives to this problem (their approximation, their combinatorics, ...) and many of these variants (reverse complement case, cyclic superstring case, case cover by a set of superstrings). This has solved several questions about the complexity and the approximation of these problems. In particular, the greedy algorithm solves in linear time the question of the shortest cyclic cover of strings. Although the greedy algorithm is the simplest and one of the most studied of these problems, it remains a mystery. Our study has highlighted a new graph, the superstring graph, which corresponds to a dip from solutions of the greedy algorithm in the index structure that is the suffix tree. In other words, the superstring graph summarizes all the greedy solutions in a linear space.Finally, attention has turned to the algorithms of the best assemblers used in practice (IDBA, Spades), which have improved the assembly of short reads using several assembly graphs. We show firstly that the superstring graph can store more information than these assemblers and with a complexity in much smaller space. Then, it is apparent that the greedy algorithm for a variant of the shorter superstring problem provides sequences which include the contigs found for these algorithms. These results link the assembly in practice and the superstring problems, and give a strong theoretical framework for studying these heuristic algorithms.

Construímos uma deformação integrável da ação de espinores puros no espaço AdS5×S5 baseada na teoria de perturbação homológica. Mostramos que o modelo resultante descreve uma corda movendo-se em um superespaço eta. Nesse sentido, estabelecemos um mapa entre operadores de vértices na cohomologia da carga BRST em AdS5×S5 e o superespaço / We construct an integrable deformation of the AdS5×S5 pure spinor action based on homological perturbation theory. We show that the resulting model describes a pure spinor string moving in an eta-target superspace. In that sense, we establish a one-to one map between vertex operators in the cohomology of the undeformed BRST charge and the eta-target space.

Construímos uma deformação integrável da ação de espinores puros no espaço AdS5×S5 baseada na teoria de perturbação homológica. Mostramos que o modelo resultante descreve uma corda movendo-se em um superespaço eta. Nesse sentido, estabelecemos um mapa entre operadores de vértices na cohomologia da carga BRST em AdS5×S5 e o superespaço / We construct an integrable deformation of the AdS5×S5 pure spinor action based on homological perturbation theory. We show that the resulting model describes a pure spinor string moving in an eta-target superspace. In that sense, we establish a one-to one map between vertex operators in the cohomology of the undeformed BRST charge and the eta-target space.

A simple two scale compactification scheme for the E(8) x E(8) heterotic string is studied. The internal space used is a direct product of two compact spaces, each with its own length scale. Compactification on the smaller 4-dimensional (4d) manifold is carried out to obtain 6d theories with simple supersymmetry (SUSY). Assuming the background torsion vanishes, we show that this manifold must be K3. Compactification on K3 is studied in detail. Also analyzed are the two possible torsion-free compactifications on the orbifold K3$ sp prime$ (the limit of the manifold K3). The compactification from 6d to 4d on the larger scale 2d manifold results in Grand Unified Theories (GUT's) with broken SUSY. We show that it is not possible to generate a realistic theory using our scheme. Strings exclude what is conceivable from the perspective of point field theories: getting a realistic GUT from a 6d theory with simple SUSY.

Thesis (Ph. D.)--University of Texas at Austin, 2008. / Vita. Includes bibliographical references.

Made available in DSpace on 2014-06-11T19:32:10Z (GMT). No. of bitstreams: 0 Previous issue date: 2011-11-10Bitstream added on 2014-06-13T19:21:26Z : No. of bitstreams: 1 zuniga_hg_dr_ift.pdf: 1022667 bytes, checksum: 4bb9cc5ce799137c7e017ee6d1a8f284 (MD5) / Fundação de Amparo à Pesquisa do Estado de São Paulo (FAPESP) / Primeiro vamos dar uma breve revisão sobre o artigo de Nekrasov “ Lectures on curved beta-gamma systems, pure spinors, and anomalies”, a fim de mostrar que o formalismo de espinor puro é livre de anomalia quando a origem é removido do espaço espinor puro. Desta forma, damos uma nova proposta para os operadores de imagem no formalismo de espinor puro mínimo. Nós calculamos amplitudes de espalhamento a nível de árvore, realizando a integração no espaço espinor puro como uma integral de Cauchy tipo multidimensional. A amplitude é escrita em termos de variáveis do espaço de espinor puro projetivo, o que é muito útil na hora de relacionar rigorosamente as versões mínima e não mínima do formalismo de espinor puro. A linguagem natural para relacionar esses formalismos é o isomorfismo de Cech-Dolbeault. Além disso, o cociclo de Dolbeault correspondente à amplitude de espalhamento a nível de árvore deve ser avaliada no espaço compacto SO(10)/SU(5) em vez de tudo o espaço de espinor puro, o que significa que a origem é removido neste espaço. Nós também obtimos uma relação entre a função de Green para um campo escalar sem massa em dez dimensões e as amplitude de espalhamento a nível de árvore. Os fatores globais constantes nas amplitudes de espalhamento são muito importante, porque eles precisam satisfazer as condições de unitariedade e S-dualidade [66]. Estes coeficientes não tinham sido computados no formalismo espinor puro, devido à dificuldade para resolver as integrais no espaço de espinores puro. Nós calculamos estas integrais usando o formalismo de espinor puro não mínimo. Assim, encontramos os coeficientes das amplitudes de um e dois-“loop” para quatro pontos sem massa. Contrastando com as dificuldades matemáticas no formalismo RNS, em que o desconhecimento das normalizações... / First, we give a brief review about the Nekrasov’s paper “Lectures on curved betagamma systems, pure spinors, and anomalies” in order to show the pure spinor formalism is anomaly free when the origin is removed from the pure spinor space. In this way we give a new proposal for the “picture lowering” operators in the minimal pure spinor formalism. We compute the tree level scattering amplitude by performing the integration over the pure spinor space as a multidimensional Cauchy-type integral. The amplitude is written in terms of the projective pure spinor variables, which turns out to be useful to relate rigorously the minimal and non-minimal versions of the pure spinor formalism. The natural language for relating these formalisms is the Cech-Dolbeault isomorphism. Moreover, the Dolbeault cocycle corresponding to the three-level scattering amplitude must be evaluated in SO(10)/SU(5) instead of the whole pure spinor space, which means that the origin is removed from this space. We also relate the Green’s function for the massless scalar field in ten dimensions to the tree-level scattering amplitude and comment about the scattering amplitude at higher orders. The overall constan factors in the scattering amplitudes are very important because they need to satisfy the unitarity and S-duality conditions [66]. These coefficients have not been computed in the pure spinor formalism due to the difficulty to solve the integrals on the pure spinors space. We compute these integrals by using the non-minimal pure spinor formalism. So, we find the coefficients of the massless one and two-loop four-point amplitude from first principles. Contrasting with the mathematical difficulties in the RNS formalism where unknown normalizations of chiral determinant formulæ force the two-loop coefficient to be... (Complete abstract click electronic access below)

Orientador: Nathan Jacob Berkovits / Banca: Fernando Pablo Devecchi / Banca: José Abdalla Helayel Neto / Banca: José Francisco Gomes / Banca: Rogério Rosenfeld / Resumo: Nesta tese, são derivadas as equações de movimento efetivas da supercorda tipo II, assim como os vínculos da supergravidade tipo II. Os resultados são obtidos acoplando a supercorda tipo II, descrita no formalismo híbrido desenvolvido por Berkovits, ao super-espaço curvo N = 2 e exigindo invariância superconforme N = (2, 2) perturbativamente na folha de mundo. Todos os cálculos são realizados diretamente no super-espaço N = 2, como consequência imediata do formalismo utilizado. A análise no nível de árvore mostra que os vínculos derivados quebram a invariância conforme e SU(2). O dilaton, que não acopla classicamente, será o campo compensador e as simetrias da folha de mundo exigem que este seja representado por multipleto vetorial e um multipleto hypertensorial. Em particular, mostramos que a supercorda seleciona um gauge particular, onde a matéria é fixa e não o compensador. As equações de movimento para o compensador são derivadas no nível de árvore e confirmadas extendendo a análise em 1 loop / Abstract: In this thesis, the effective equations of motion of type II superstring has been derived, as well as the type II supergravity constraints. The results are obtained by coupling type II superstring (described in Berkovits' formalism) to N = 2 curved superspace and imposing perturbatively N = (2,2) superconformal invariance on the worldsheet. The computations are carried out in N = 2 superspace, as an immediate consequence of the utilized formalism. The analysis at tree level shows that the derived constraints break conformal invariance and SU(2). The dilaton, that doesn't couple classically, will be the compensator field, and the worldsheet symmetries require that it is represented by a vector and a hypertensorial multiplet. In particular, we show that superstring selects a particular gauge where the matter is fixed, not the compensator. The compensator's equations of motion are derived at tree level and confirmed extending the analysis to one loop / Doutor

Orientador: Nathan Jacob Berkovits / Banca: Vladimir Demyanovich Pershin / Banca: Victor de Oliveira Rivelles / Resumo: Neste trabalho nós revisamos o formalismo de Green-Schwarz (GS) da supercorda e discutimos os seus problemas e vantagens com relação ao formalismo de Ramond-Neveu-Schwarz (RNS). Nós demonstramos, entre outras coisas, que o formalismo de Green-Schwarz possui supersimetria manifesta no espaço-tempo, mas que não pode ser quantizado covariantemente, exatamente o oposto do que ocorre em RNS. Então nós finalmente estudamos o formalismo recém criado de espinores puros, que incorpora as boas propriedades dos formalismos anteriores sem incluir seus defeitos / Abstract: n this work we review the Green-Schwarz (GS) formalism of the superstring and discuss its problems and advantages with respect to the Ramond-Neveu-Schwarz (RNS) formalism. We show, among other things, that the GS formalism has manifest spacetime supersymmetry, but at the same time it cannot be covariantly quantized, exactly the opposite of what happens in the RNS formalism. Then we finally study the recently developed pure spinor formalism, which has the good properties of the previous two without having their problems / Mestre

京都大学 / 新制・課程博士 / 博士(理学) / 甲第22992号 / 理博第4669号 / 新制||理||1670(附属図書館) / 京都大学大学院理学研究科物理学・宇宙物理学専攻 / (主査)教授 高柳 匡, 教授 青木 慎也, 教授 田中 貴浩 / 学位規則第4条第1項該当 / Doctor of Science / Kyoto University / DFAM

No description available.