Search

Orientador: João Meidanis Tese (doutorado) - Universidade Estadual de Campinas, Instituto de Computação 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

Orientador: João Meidanis Dissertação (mestrado) - Universidade Estadual de Campinas, Instituto de Computação Resumo: Contexto: A classificação de espécies começou sendo determinada pelas características fenotípicas dos organismos. Logo que o DNA foi descoberto, o sistema de classificação passou também a utilizar-se das características genotípicas. Ao longo dos últimos anos, avanços científicos permitiram que fossem sequenciados genomas completos. A cada ano, o número de genomas completamente sequenciados aumenta, e, com isso, é cada vez maior o número de trabalhos que tentam utilizar-se do maior número possível de genes para comparar dois ou mais organismos com o objetivo de melhor entender o relacionamento entre as diversas espécies. Experimento: Este trabalho executa comparações de pares de cromossomos de um grupo de 10 genomas completos da família Vibrionaceae e um genoma completo da bactéria Escherichia coli como externo ao grupo. As homologias entre as proteínas são determinadas através da base de famílias Protein Clusters (NCBI). A seguir, arvores ultramétricas e a classificação COG das proteínas são utilizadas para resolver as paralogias correspondentes. Após isto, as proteínas únicas, que representam os eventos de perda e ganho de genes, são eliminadas, de forma a igualar o conteúdo dos cromossomos. Tipicamente, 50% das proteínas originais do pares de organismos de mesma família 'sobrevivem" para serem utilizadas no cálculo da distância de rearranjo. Menos proteínas sobrevivem nas comparações com a bactéria externa ao grupo. A distância total é calculada pela soma do número de proteínas eliminadas e da distância de ordenação, medida através da distância de rearranjo dos cromossomos. Resultados: As comparações produziram matrizes de distâncias utilizadas para inferir árvores filogenéticas através do algoritmo Neighbor-Joining (NJ). As árvores filogenéticas encontradas mostraram-se congruentes em topologia com a árvore produzida pelo gene 16S rRNA. Isto mostra que a comparação de genomas completos é uma proposta sensata. Os desafios agora são aperfeiçoar os detalhes. O material suplementar (Apêndice A) contém uma implementação computacional dos experimentos Abstract: Context: Species classification was originally determined by phenotypic characteristics. With the advent of DNA sequencing, the classification system started using genotypes as well. Over the last decades, scientific progress allowed complete sequencing of genomes. Each year, the number of genomes completely sequenced increases, and with it, the number of works trying to use as much genes as possible to compare two or more organisms, in order to get a better understand of the relationship between several species. Experiment: This work executes a pairwise chromosome comparison from a set of 10 complete genomes from the Vibrionaceae family and one complete Escherichia coli genome as an outgroup. In our experiment, the homologies between proteins are assessed using the Protein Clusters (NCBI) database. In the next step, paralogies are resolved using ultrametric trees and COG classification. In the sequel, the loss and gain events are treated, thus, proteins present in only one chromosome from the pair are eliminated, in order to equalize the set of families in both chromosomes. Typically, 50% of the original proteins survive in comparisons between organisms of the same family (comparisons with the outgroup yield less survivors). The total distance is calculated by adding the number of eliminated proteins with the order distance, which is measured by the rearrangement distance beetween the chromosomes. Results: Genome comparison produces distance matrices used to infer the phylogenetic trees through the Neighbor-Joining (NJ) algorithm. The phylogenetic trees generated are congruent regarding the topology with the tree inferred using the 16S rRNA gene. Also, in order to run a deeper investigation, the experiment was executed with some variations such as not resolving the paralogies using ultrametric trees or only classifying proteins using COG database. Supplemental material (Appendix A) contains the experiment computational implementation Mestrado Biologia Computaçional Mestre em Ciência da Computação

Orientador: Zanoni Dias Tese (doutorado) - Universidade Estadual de Campinas, Instituto de Computação Resumo: O estudo de rearranjo de genomas tem o objetivo de auxiliar o entendimento da evolução. Através da análise dos eventos de mutação como inversões, transposições, fissões, fusões, entre outros, buscamos compreender as suas influências sobre o fenômeno da diferenciação das espécies. Dentro deste contexto, esta tese ataca dois temas distintos: a Enumeração de Traces e a Identificação de Breakpoints. Os algoritmos de ordenação de permutações por reversões orientadas produzem uma única solução ótima enquanto o conjunto de soluções é imenso. A enumeração de traces de soluções para este problema oferece um modo mais compacto de representar o conjunto completo de soluções ótimas. Dessa maneira, esta técnica fornece aos biólogos a possibilidade de análise de diversos cenários evolutivos. Neste trabalho, realizamos um estudo para melhora da eficiência do algoritmo de enumeração através da adoção de uma estrutura de dados mais simples. Devido ao caráter exponencial do problema, grandes permutações não podem ser processadas em um tempo satisfatório. Assim, com o objetivo de produzir cenários evolucionários alternativos para grandes permutações, propomos e avaliamos estratégias para a enumeração parcial de traces. Os pontos de quebra (ou breakpoints) são regiões que delimitam os segmentos conservados existentes nos cromossomos e denotam a ocorrência de rearranjos evolutivos. As técnicas de identificação de breakpoints têm a função de identificar tais pontos nas sequências dos cromossomos. Nesta tese, implementamos um método de detecção e refinamento de pontos de quebra proposto na literatura e o disponibilizamos como um pacote que pode ser utilizado por outros pesquisadores. Além disso, introduzimos uma nova metodologia de identificação de breakpoints baseada na análise da cobertura de hits observada nos alinhamentos de sequências intergênicas, provenientes dos genomas das espécies comparadas Abstract: The study of genome rearrangements helps biologists understand the evolution of species. The species differentiation phenomenon are derived by analyzing mutational events (inversions, transpositions, fissions, fusions, etc) and their effects. In this context, this work aims the study of two different subjects: Traces Enumeration and Breakpoint Identification. Algorithms that solve the problem of sorting oriented permutations through reversals output only one optimal solution, although the set of solutions can be huge. The enumeration of traces of solutions for this problem allows a compact representation of the set of all optimal solutions which sort a permutation. By using this technique, biologists can study many evolutionary scenarios. We carried out a study to improve the efficiency of the enumeration algorithm by adopting a simple data structure. Due to the exponential nature of the problem, large permutations cannot be processed at a satisfactory time. Thus, in order to produce alternative evolutionary scenarios for large permutations, we proposed and evaluated strategies for partial enumeration of traces. Breakpoints are regions that border conserved segments in the chromosomes and reflect the occurrence of evolutionary rearrangements. The techniques for breakpoint identification are meant to identify such points in the chromosome sequences. In this work, we implemented a method proposed in the literature, that performs detection and refinement of breakpoints. The implementation is available as a package to other researchers. Additionally, we introduced a new methodology for breakpoint identification based on the analysis of the hit coverage observed in the alignments of intergenic sequences Doutorado Ciência da Computação Doutor em Ciência da Computação

Orientador: João Meidanis Dissertação (mestrado) - Universidade Estadual de Campinas, Instituto de Computação Resumo: Uma das principais formas de se medir a distância evolutiva entre espécies é avaliando-se quão transformado um genoma foi em relação a outro. Tais transformações são conhecidas como rearranjos de genoma. Neste trabalho estaremos analisando o rearranjo chamado de transposição, evento que troca de posição dois blocos consecutivos de genes de um mesmo cromossomo. Mais especificamente, buscamos encontrar o número mínimo de transposições que transforma um cromos somo em outro, valor conhecido como distância de transposição. Matematicamente, consideramos os cromossomos como permutações e o problema de se transformar uma permutação em outra pode ser visto como uma ordenação. Em nosso estudo, introduzimos uma operação de remoção de elementos, ferramenta ainda pouco explorada no estudo da distância de transposição, mas que nos possibilitou obter um limite superior para a distância de transposição. Também sugerimos novas formas de se utilizar a remoção de elementos e a análise de subseqüências de permutações. Como forma de se tentar obter novos conhecimentos sobre o problema da distância de transposição, consideramos a variação do problema em que somente transposições de prefixo são permitidas. Zanoni Dias propôs um algoritmo polinomial que transforma qualquer permutação de comprimento n em sua reversa em f3n/41 passos, porém sem uma prova completa. Modificamos esse algoritmo, mantendo o número de passos, e apresentamos uma prova completa da correção do algoritmo modificado. Ainda no problema de distância de transposição de prefixo, analisamos as permutações cujas distâncias se igualam ao limite inferior de distância de pontos de quebra. Tais permutações são fáceis de serem ordenadas por transposições de prefixo em tempo polinomial, pois possuem ordenação ótima única e bem definida. Ao final chegamos à conclusão que as permutações que são fáceis de se ordenar no problema de transposições de prefixo também são fáceis no problema de transposições, o que prova que a variação do problema auxilia no estudo do problema original Abstract: One of the main ways of measuring the evolution distance among species is to evaluate how large chunks have moved when comparing two genomes. Such changes are know as genome rearrangements. In this work we analyze a rearrangement event called transposition that changes the position of two consecutive blocks of genes in a chromosome. More specifically, we look for the minimum number of transpositions needed to transform a chromosome into another. This value is called the transposition distance. Mathematically, chromosomes are regarded as permutations and changing one genome into another can be seen as a sorting problem. In our study, we introduce an operation of element removal from permutations, which has not been fully explored, but allowed us to find an upper bound for the transposition distance. We also suggest new ways of making use of element removal and the analysis of permutation subsequences. In the hope of obtaining new knowledge about the problem of transposition distance, we considered the variation of the problem where we allow prefix transpositions only. Zanoni Dias developed a polynomial algorithm that changes any permutation into its reverse using f3n/41 steps, but without a proof of its correctness. We have modified this algorithm, keeping the number of steps, and presented a complete proof of the correction of the modified algorithm. Still about the prefix transposition distance, we have analyzed those permutations whose distance equals the breakpoint lower bound. Such permutations are easily sorted by prefix transpositions in polynomial time, since they have a unique and well-defined optimum sorting. Finally, we concluded that the permutations that are easily sorted in the prefix transposition problem are also easily sorted in the transposition problem, which proves that the variation of the problem helps the study of the original problem Mestrado Mestre em Ciência da Computação

Orientador : João Meidanis Tese (doutorado) - Universidade Estadual de Campinas, Instituto de Computação Resumo: Nesta tese apresentamos um algoritmo quase-linear para construir árvores PQR e o esquema para clustering de seqüências expressas que foi usado no projeto SUCEST (Sugarcane EST project).Uma árvore PQR é uma estrutura de dados capaz de resolver o problema dos uns consecutivos e outros problemas, como mapeamento físico de DNA, reconhecimento de grafos intervalo, otimização de circuitos lógicos e recuperação de dados. As árvores PQR são uma generalização das árvores PQ de Booth e Lueker e estão fundamentadas em propriedades algébricas sólidas. O algoritmo que apresentamos nesta tese se baseia nessas propriedades e é formado por um conjunto pequeno de padrões que modificam a árvore. Nosso algoritmo é mais eficiente que o algoritmo quadrático proposto originalmente por Meidanis e Munuera ao definir as árvores PQR e, embora não seja linear como o algoritmo para construir árvores PQ, acreditamos que ele contribui em direção a uma solução definitiva para o problema dos uns consecutivos. Clustering é o problema de categorização de um conjunto de objetos quando nem o número nem a composição das categorias é conhecido antecipadamente. Seqüências expressas ou ESTs (expressed sequence tags) são amostras de genes ativos extraídas das células de um organismo. Em um projeto genoma EST são obtidas milhares dessas seqüências que serão usadas como fonte para investigações por cientistas interessados nos processos celulares do organismo. O clustering de seqüências expressas é necessário para avaliar e reduzir a redundância do conjunto de ESTs. Nesta tese apresentamos o esquema de clustering usado no projeto da cana-de-açúcar, que produziu aproximadamente 300.000 ESTs. O esquema que apresentamos substituiu um esquema pré-existente e se caracteriza por uma limpeza prévia intensiva dos ESTs e pelo uso de um montador de genomas para agrupá-los. Acreditamos que este esquema possa ser utilizado em outros projetos do gênero Abstract: In this thesis we introduce an almost-linear algorithm for building PQR trees and the method for expressed sequence tags clustering used in the SUCEST project (Sugarcane EST Project). A PQR tree is a structure that can be used to solve many problems, as the consecutive ones problem, DNA physical mapping, interval graphs recognition and data retrieval. PQR trees are a generalization of Booth and Lueker's PQ trees, and are founded on solid algebraic properties. The algorithm we present in this work is based on such properties and is composed by a small set of well-organized patterns. Our algorithm is more efficient than the quadratic one proposed by Meidanis and Munuera, who defined the PQR trees, and, although not linear as the algorithm for PQ trees construction, we believe that it contributes for a definite solution for the consecutive ones problem. Clustering is the problem of categorizing a set of objects when neither the number of categories nor the composition of the categories is known. Expressed sequence tags (ESTs) are samples from active genes extracted from cells of an organism. In an EST project, thousands of ESTs are produced and used as a source for research. Clustering ESTs is necessary to reduce the redundancy in the set of sequences. In this thesis we introduce the method used in the Sugarcane EST Project, that produced almost 300,000 sequences. The method we introduce in this work replaced another one that had problems. Our scheme include an intensive trimming of the ESTs and the use of a genome assembler for the whole set of sequences. We believe that our scheme may be used in other EST projects Doutorado Doutor em Ciência da Computação

Orientador : João Carlos Setubal Dissertação (mestrado) - Universidade Estadual de Campinas, Instituto de Computação Resumo: Este trabalho apresenta a bioinformática desenvolvida e usada nos projetos genoma XyIelIa fastidiosa e Xanthomonas. O objetivo geral da bioinformática nesses projetos é armazenar, organizar, analisar e disponibilizar os dados biológicos oriundos dos aboratórios de seqüenciamento. Em particular, são apresentados dois sistemas de software usados para a montagem e para a anotação de genomas de bactérias. A dissertação contém também um capítulo detalhando fundamentos de biologia molecular e de técnicas de seqüenciamento de DNA Mestrado Mestre em Ciência da Computação

Orientador : João Carlos Setubal Tese (doutorado) - Universidade Estadual de Campinas, Instituto de Computação Resumo: Com o crescente número de genomas seqüenciados e publicados, surge a necessidade de se analisar as seqüências geradas, com o objetivo de se entender melhor caracterizações funcionais dos organismos estudados, assim como aspectos evolutivos. Um projeto genoma de um organismo, em especial de um procarioto, consiste essencialmente de três grandes fases: o seqüenciamento, a anotação e a análise. A última etapa, por sua vez, consiste na tentativa de se obter uma visão global do genoma a partir da anotação e a partir de outras análises, como por exemplo a comparação com outros genomas. E é nesse contexto, comparação de genomas, que esta tese se insere. Nosso trabalho propõe metodologias para comparação detalhada de dois genomas, tanto no nível de DNA, quanto no de seus genes, assim como a implementação dessas metodologias. O principal objetivo é fornecer ao usuário um conjunto de ferramentas para caracterização funcional do organismo estudado, servindo também como ferramental auxiliar na anotação Abstract: With increasing availability of published genome sequences, we need to analyse them in order to understand functional and evolutionary issues of the organisms. A genome project, in particular for prokaryotes, consists of three main phases: sequencing, annotation and analysis. The last phase consists of getting an overview of the genome from the annotation and other analysis, like comparison to other genomes, for example. This thesis is about genome comparison. We propose methodologies for detailed comparison of two genomes, at the DNA and their genes levels. The main goal is to provide a set of tools for functional characterization of organisms, serving also as an auxiliar tool for annotation Doutorado Doutor em Ciência da Computação