No description available.

While the use of microbial model systems in experimental evolution has made great contributions to our understanding of evolutionary processes, technological limitations and the problems of transparency they cause continue to inhibit their use in understanding even the most basic evolutionary phenomena. Conventional mathematical models are too constraining in that the range of genotypes and fitnesses must be designated at the outset, and so such models cannot be used to describe truly open-ended systems. In this thesis, I use Artificial Life technology to investigate patterns and mechanisms of evolution over short and long periods of time in a simulated chemostat-type system. The system may be rendered completely transparent, and is "open" in that genotypes with unique sequences and fitness arise unpredictably through mutation and selection. / The results demonstrate that Artificial Life technology is an open-ended, yet tractable system that may be used satisfactorily to investigate problems that he beyond the reach of current theory and biotechnology. (Abstract shortened by UMI.)

No description available.

Orientador: Zanoni Dias / Tese (doutorado) - Universidade Estadual de Campinas, Instituto de Computação / Made available in DSpace on 2018-08-20T03:52:46Z (GMT). No. of bitstreams: 1 Dias_UlissesMartins_D.pdf: 19168517 bytes, checksum: 463a6e15e1414ce37a0fe80f92de6b07 (MD5) Previous issue date: 2012 / Resumo: Esta tese aborda três aspectos da comparação entre genomas: primeiro, eventos de transposição; segundo, eventos de reversão e de reversão quase-simétrica; terceiro, estudo da distância entre genomas sem ligação com algum tipo específico de rearranjo. O estudo do primeiro aspecto, eventos de transposição, permitiu a criação de um novo algoritmo de aproximação na razão 1.375 e de modelos exatos usando programação em lógica com restrições para o problema da distância de transposição. Ambas as abordagens foram comparadas com outras semelhantes encontradas na literatura e, em ambos os casos, foi mostrado que o produto aqui apresentado é superior 'aqueles previamente conhecidos. Sob o segundo aspecto, eventos de reversões e de reversões quase-simétricas, houve avanços relacionados ao entendimento do processo de diferenciação das espécies na família Pseudomonadaceae e nos gêneros Mycobacterium, Shewanella e Xanthomonas com a criação de uma ferramenta de simulação capaz de gerar um histórico evolutivo com características semelhantes 'as observadas nos referidos grupos. Além disso, foram obtidos avanços em abordagens algorítmicas para o problema de construção de scaffolds usando um genoma de referência. De modo particular, foi obtida uma ferramenta superior 'as demais existentes na literatura para construção de scaffolds de genomas bacteriais. Ainda neste segundo aspecto, tratou-se do problema da distância de reversões quase-simétricas com a geração de um algoritmo guloso que fornece uma sequência de reversões quase-simétricas para ordenar qualquer permutação, além de algoritmos exatos para várias famílias específicas de permutações. No que diz respeito ao terceiro aspecto, foram desenvolvidas duas medidas que podem ser calculadas de forma eficiente (poucos segundos). Uma das medidas é adequada para genomas próximos e a outra é adequada para genomas distantes. Ambas foram avaliadas com genomas bacteriais reais, o que mostrou as vantagens e limitações de cada medida. Com esta tese, espera-se ter contribuído para a área de comparação de genomas em geral e, em particular, para a área de rearranjo de genomas / Abstract: In this PhD thesis, we work on three aspects of genome comparison: first, transposition events; second, inversion and almost-symmetric inversion events; third, whole-genome distance measures that are not connected to any specific kind of rearrangement event. The study of transposition events (first aspect) allowed us to create a new 1.375-approximation algorithm and some exact models using constraint logic programming. These approaches were compared to other published methods and in all cases our methods perform best. The second aspect of this thesis concerns inversion and almost-symmetric inversion events. In this regard, we developed a simulation tool for the study of symmetric inversions in bacterial genomes. Through this work we were able to contribute to the understanding of the evolutionary differentiation process in species of the following groups: the Pseudomonadaceae family, the Xanthomonas genus, the Shewanella genus, and the Mycobacterium genus. We used the knowledge acquired in building our simulation tool to establish a method that uses inversion signatures to generate draft genome sequence scaffolds using a complete genome as a reference. Apart from the practical applications of this research, we contribute to the computer science field by providing a theoretical framework for the almost-symmetric distance problem that can be improved in the future and can serve as a basis for approximation and heuristic algorithms. This framework is comprised of a greedy algorithm for any permutation, exact algorithms for specific families of permutation, and several lemmas and conjectures related to these problems. The third and last aspect of this thesis addresses the need for methods that can quickly and effectively compare large sets of genome sequences. We propose two new methods for efficiently determining whole genome sequence distance measures. One of them is aimed at comparing closely related genomes, and the other is meant to compare more distant genomes. Both measures were evaluated in order to find their limitations and their efficacy. It is our hope that thiswork represents a contribution to knowledge of the genome comparison field in general, and the genome rearrangement field, in particular / Doutorado / Ciência da Computação / Doutor em Ciência da Computação

Orientador: João Meidanis / Tese (doutorado) - Universidade Estadual de Campinas, Instituto de Computação / Made available in DSpace on 2018-08-21T17:01:05Z (GMT). No. of bitstreams: 1 Feijao_PedroCipriano_D.pdf: 1943126 bytes, checksum: 4c547e8c568bbd0f2eb8235dfde05524 (MD5) Previous issue date: 2012 / Resumo: Rearranjo de genomas é o nome dado a eventos onde grandes blocos de DNA trocam de posição durante o processo evolutivo. Com a crescente disponibilidade de sequências completas de DNA, a análise desse tipo de eventos pode ser uma importante ferramenta para o entendimento da genômica evolutiva. Vários modelos matemáticos de rearranjo de genomas foram propostos ao longo dos últimos vinte anos. Nesta tese, desenvolvemos dois novos modelos. O primeiro foi proposto como uma definição alternativa ao conceito de distância de breakpoint. Essa distância é uma das mais simples medidas de rearranjo, mas ainda não há um consenso quanto à sua definição para o caso de genomas multi-cromossomais. Pevzner e Tesler deram uma definição em 2003 e Tannier et al. a definiram de forma diferente em 2008. Nesta tese, nós desenvolvemos uma outra alternativa, chamada de single-cut-or-join (SCJ). Nós mostramos que, no modelo SCJ, além da distância, vários problemas clássicos de rearranjo, como a mediana de rearranjo, genome halving e pequena parcimônia são fáceis, e apresentamos algoritmos polinomiais para eles. O segundo modelo que apresentamos é o formalismo algébrico por adjacências, uma extensão do formalismo algébrico proposto por Meidanis e Dias, que permite a modelagem de cromossomos lineares. Esta era a principal limitação do formalismo original, que só tratava de cromossomos circulares. Apresentamos algoritmos polinomiais para o cálculo da distância algébrica e também para encontrar cenários de rearranjo entre dois genomas. Também mostramos como calcular a distância algébrica através do grafo de adjacências, para facilitar a comparação com outras distâncias de rearranjo. Por fim, mostramos como modelar todas as operações clássicas de rearranjo de genomas utilizando o formalismo algébrico / Abstract: Genome rearrangements are events where large blocks of DNA exchange places during evolution. With the growing availability of whole genome data, the analysis of these events can be a very important and promising tool for understanding evolutionary genomics. Several mathematical models of genome rearrangement have been proposed in the last 20 years. In this thesis, we propose two new rearrangement models. The first was introduced as an alternative definition of the breakpoint distance. The breakpoint distance is one of the most straightforward genome comparison measures, but when it comes to defining it precisely for multichromosomal genomes, there is more than one way to go about it. Pevzner and Tesler gave a definition in a 2003 paper, and Tannier et al. defined it differently in 2008. In this thesis we provide yet another alternative, calling it single-cut-or-join (SCJ). We show that several genome rearrangement problems, such as genome median, genome halving and small parsimony, become easy for SCJ, and provide polynomial time algorithms for them. The second model we introduce is the Adjacency Algebraic Theory, an extension of the Algebraic Formalism proposed by Meidanis and Dias that allows the modeling of linear chromosomes, the main limitation of the original formalism, which could deal with circular chromosomes only. We believe that the algebraic formalism is an interesting alternative for solving rearrangement problems, with a different perspective that could complement the more commonly used combinatorial graph-theoretic approach. We present polynomial time algorithms to compute the algebraic distance and find rearrangement scenarios between two genomes. We show how to compute the rearrangement distance from the adjacency graph, for an easier comparison with other rearrangement distances. Finally, we show how all classic rearrangement operations can be modeled using the algebraic theory / Doutorado / Ciência da Computação / Doutor em Ciência da Computação