Submitted by Anderson Silva (avargas@icict.fiocruz.br) on 2012-09-19T13:39:08Z No. of bitstreams: 1 renato_s_junior_ioc_bp_0048_2011.pdf: 2131023 bytes, checksum: c67826382b4b8b6c00b329a3f8c712d2 (MD5) / Made available in DSpace on 2012-09-19T13:39:08Z (GMT). No. of bitstreams: 1 renato_s_junior_ioc_bp_0048_2011.pdf: 2131023 bytes, checksum: c67826382b4b8b6c00b329a3f8c712d2 (MD5) Previous issue date: 2011 / Universidade Federal Fluminense. Centro de Estudos Gerais. Instituto de Biologia. Niteroi, RJ, Brasil / A família Trypanosomatidae inclui parasitas de uma grande variedade de vertebrados, invertebrados (principalmente insetos), plantas e algumas espécies de protozoários, sendo, depois do nematóides, os de maior distribuição de hospedeiros na natureza. No presente trabalho, um novo isolado foi obtido por coprocultivo de trato intestinal de Leptoglossus stigma Herb, 1784 (Hemiptera, Coreidae), capturado no município de Itaguaí/RJ. O isolado original e três clones (obtidos por citometria de fluxo) foram depositados na "Coleção de Flagelados do Laboratório de Transmissores de Leishmanioses." Um clone foi caracterizado por diversas abordagens em comparação com espécies de referência de diferentes gêneros. Foi analisado o crescimento em meio de cultivo em intervalos de 24 h, entre 48-144 h, a diferenciação celular e a morfometria dos principais estágios evolutivos encontrados. A análise de isoenzimas foi realizada utilizando-se os seguintes sistemas: GPI, PGM, 6PGDH, HK, ACON, MPI, FUM, IDH, MDH e ACON. RAPD-PCR foi realizado utilizando-se 6 iniciadores, conjuntamente com outros tripanosomatídeos. Os dados destas análises foram processados numericamente e submetidos à análise computacional utilizando-se o coeficiente de associação Jaccard e o algoritmo de agrupamento UPGMA. Realizou-se seqüenciamento do amplicon do gene de SSU rRNA e o fragmento analisado foi alinhado com vinte e uma seqüencias depositadas no GenBank, gerando uma árvore filogenética resultante do pareamento. O conjunto de resultados deste trabalho sugere que a amostra obtida constitui nova espécie, pertencendo a um novo gênero, nomeada Vickermania itaguaiensis. / The Trypanosomatidae family includes parasites of a wide variety of vertebrates, invertebrates (mainly insects), plants and some species of protozoa, and after the nematodes, the highest distribution of hosts in nature. In this study, an isolate was obtained by coproculture from Leptoglossus stigma Herb, 1784 (Hemiptera, Coreidae) intestinal tract, captured in the city of Itaguaí/RJ. The original isolate and clones (obtained by flow cytometry) were deposited in the "Coleção de Flagelados do Laboratório de Transmissores de Leishmaniose". One clone was characterized by several approaches in comparison with the reference species of different genus. Growth was analyzed in culture medium at 24 h intervals between 48-144 h, cell differentiation and morphometric parameters of the main evolutionary stages matches. The isoenzyme analysis was performed using the following systems: GPI, PGM, 6PGDH, HK, ACON, MPI, FUM, IDH, MDH and ACON. RAPD-PCR was performed using 6 primers, together with other trypanosomatids. The analysis of these data were numerically processed and submitted to computer analysis using the Jaccard association coefficient and UPGMA clustering algorithm. We carried out sequencing of the amplicon from SSU rRNA gene and the fragment analyzed was aligned with twenty-one sequences deposited in GenBank, generating a phylogenetic tree resulting from the pairing. The result set of this work suggests that the sample obtained represents a new species belonging to a new genus, named Vickermania itaguaiensis.

Submitted by Anderson Silva (avargas@icict.fiocruz.br) on 2012-10-16T16:18:56Z No. of bitstreams: 1 ana_carolina_r_guimaraes_ioc_bcm_0008_2010.pdf: 7783704 bytes, checksum: c55aa365e04b94c51640b1937be9e63d (MD5) / Made available in DSpace on 2012-10-16T16:18:56Z (GMT). No. of bitstreams: 1 ana_carolina_r_guimaraes_ioc_bcm_0008_2010.pdf: 7783704 bytes, checksum: c55aa365e04b94c51640b1937be9e63d (MD5) Previous issue date: 2010 / Fundação Oswaldo Cruz. Instituto Oswaldo Cruz. Laboratório de Genômica Funcional e Bioinformática. Rio de Janeiro, RJ, Brasil / O estudo da reconstrução metabólica em diversos organismos expõe a existência de compostos cruciais para a sua sobrevivência. Dentre estes compostos, estão as enzimas, responsáveis pela catálise das reações bioquímicas em vias metabólicas. Diferentemente das enzimas homólogas, as enzimas análogas (também conhecidas como enzimas isofuncionais não homólogas) são capazes de catalisar as mesmas reações, mas sem apresentar similaridade de sequência significativa no nível primário e, possivelmente, com diferentes estruturas tridimensionais. Um estudo detalhado destas enzimas pode desvendar novos mecanismos catalíticos, adicionar informações sobre a origem e evolução de vias bioquímicas e revelar alvos potenciais para o desenvolvimento de drogas. Para muitas enfermidades causadas por parasitas, as opções terapêuticas permanecem ineficientes ou inexistentes, exigindo a busca de novos alvos. Estes podem ser proteínas específicas do parasita ausentes no hospedeiro ou compostos presentes em ambos, mas com estrutura tridimensional substancialmente diferente, como as enzimas análogas. A ferramenta AnEnPi, capaz de identificar, anotar e comparar enzimas homólogas e análogas, foi desenvolvida e utilizada para reconstruir computacionalmente as vias metabólicas de alguns organismos modelo, como os tripanossomatídeos. Uma análise mais focada no metabolismo de aminoácidos de Trypanosoma cruzi identificou alvos promissores para o desenvolvimento de novas drogas. Além disso, uma revisão do metabolismo geral de T. cruzi foi realizada em outras vias metabólicas, levando em consideração esta nova abordagem de busca por potenciais alvos terapêuticos. Uma vez que a estrutura tridimensional é importante no estudo de analogia, a ferramenta MHOLline foi utilizada para a obtenção de modelos 3D a partir de homólogos, análogos e proteínas específicas de T. cruzi versus Homo sapiens. As estratégias utilizadas nesse trabalho apóiam o conceito de análise estrutural, juntamente com a análise funcional de proteínas, como uma interessante metodologia computacional para detectar potenciais alvos para o desenvolvimento de novas drogas. / The study of metabolic reconstruction in different organisms exposes the existence of crucial compounds for its survival. Examples of these compounds are the enzymes that are responsible for the catalysis of biochemical reactions in metabolic pathways. Unlike the homologous enzymes, the analogous enzymes (also known as non- homologous isofunctional enzymes) are able to catalyze the same reactions, but without significant sequence similarity at the primary level and possibly with different three-dimensional structures. A detailed study of these enzymes may exhibit new catalytic mechanisms, add information about the origin and evolution of biochemical pathways and reveal potential targets for drug development. For many diseases caused by parasites, therapeutic options remain inefficient or nonexistent, requiring the search for new drug targets. These targets may be specific proteins of the parasite (absent in the host) or compounds present in the both organisms but with different three-dimensional structure, like analogous enzymes. The tool AnEnPi approach was able to identify, annotate and compare homologous and analogous enzymes. It was developed and used to reconstruct computationally the metabolic pathways of some model organisms such as trypanosomes. A more focused analysis on the amino acids metabolism of Trypanosoma cruzi identified promising targets for the development of new drugs. Furthermore, a review of the general metabolism of T. cruzi was carried out in other metabolic pathways, taking into account this new approach in the search for potential therapeutic targets. Since the three-dimensional structure is important in the study of analogy, the tool MHOLline was used to obtain 3D models for homologous, analogous and specific proteins of T. cruzi versus Homo sapiens. The strategies used in this study support the concept that structural analysis together with protein functional analysis could be an interesting computational methodology to detect potential targets for structure-based rational drug design.

Esta dissertação resultou na implementação de uma abordagem computacional para a análise comparativa entre informações de genomas completamente seqüenciados de bactérias associadas à planta. O sistema desenvolvido foi denominado de Probacter e é composto de um banco de dados relacional e de ferramentas computacionais para a análise de seqüências, teve por finalidade agrupar as informações disponíveis em vários bancos de dados em um único ambiente, oferecer uma padronização às informações disponibilizadas e fornecer ferramentas para análises comparativas e de seqüências. O banco de dados contém informações provenientes de diversas fontes, incluindo as bases GenBank, Swiss-Prot, TrEMBL, Interpro, COG e GO. As proteínas foram organizadas dentro de grupos, utilizando a metodologia de BBH (Bidirectional Best Hit) e a anotação padronizada de acordo com a classificação funcional anteriormente descrita para o Projeto Genoma de bactérias do gênero Xanthomonas. Cada entrada disponibilizada pelo sistema numa interface amigável corresponde a uma ficha contendo informações sobre o gene e a proteína por ele codificada, incluindo a categorização funcional, a predição de domínios, a seqüência de aminoácidos da proteína, a ligação com os grupos gerados pelo BBH, referências direta a outros bancos de dados, e as publicações científicas. O sistema oferece uma interface de busca comum a bancos de dados, utilizando consultas pré-definidas. Para consultas mais elaboradas, foi desenvolvida uma interface para ser utilizada sem que o usuário tenha conhecimento prévio de linguagens como SQL e/ou da arquitetura desta base. Ferramentas de alinhamento múltiplo ClustalW e T-Coffee e o programa BLASTP também foram integradas a este sistema, permitindo que sejam feitas comparações entre seqüências internas e externas ao banco. O ProBacter integra ferramentas de visualização gráfica, que permite disponibilizar o posicionamento dos genes pertencentes a grupos no genoma de cada organismo e que permite visualizar as ligações durante a formação dos grupos formados pelo BBH. Por fim, um campo aberto é disponibilizado para que seja possível a intervenção de usuários na anotação de novas informações em determinada entrada, sendo as informações novas oferecidas gravadas diretamente no banco de dados. / This dissertation offers a computation approach to comparative analysis between cmpletely sequenced genomes of plant-associated bacteria. The created system was denominated ProBacter and it is composed of a relational database and computational tools for sequence analysis. The database was created from a diverse data source, including information from GenBank, TrEMBL, Interpro, COG and GO. The proteins were organized into clusters through the BBH (Bidirectional Best Hits) methodology and categorized according to the functional classification of the Xanthomonas Genome Project. Each entry displayed by the system in a friendly user interface corresponds to an information sheet with the gene and protein sequence, functional category, domain prediction, and related scientific publications, in addition to the group that it belongs, and external links. The system offers a search interface similar to other database systems with pre-formatted queries. For advanced queries, the user has access to an interface that can be used without previous knowledge of the SQL language or ProBacters database arquiteture. The BLASTP program and two multiple sequence alignment tools, namely ClustalW and T-Coffee, were integrated into the system as well, allowing internal and external sequence comparison. In addition, the system makes available visualization tools capable of displaying the gene position inside a genome and BHH links of clusters. Also, the user is capable of adding new information for each gene in the system. ProBacters goal is to collect information available from a large source of databases into one computational environment, organize this information and offer comparative tools for sequence analysis.

Made available in DSpace on 2016-06-02T19:02:39Z (GMT). No. of bitstreams: 1 2372.pdf: 3456814 bytes, checksum: 7894f1e8062bb948621e2d222d01e3b0 (MD5) Previous issue date: 2008-11-06 / Financiadora de Estudos e Projetos / The Molecular Evolution of the living organisms is a slow process that occurs over the years producing mutations and recombinations at the genetic material, i.e. at the DNA. The mutations can occur as nucleotide remotion, insertion and/or substitution at the DNA chain. The Directed Molecular Evolution is an in vitro process that tries to improve biological functions of specific molecules producing mutations at the molecule s genetic material, mimicking the natural process of evolution. Many technics that simulate in vitro molecular evolution, among them the DNA shuffling, have been used aiming to improve specific properties of a variety of commercially important products as pharmaceutical proteins, vaccines and enzymes used in industries. The original DNA shuffling methodology can be sumarized by the following steps: 1) selection of the parental sequences; 2) random fragmentation of the parental sequences by an enzyme; 3) repeated cycles of PCR (Polymerase Chain Reaction), in order to reassemble the DNA fragments produced in the previous step; 4) PCR amplification of the reassembled sequences obtained in step 3). The DNA shuffling technic success can be measured by the number of recombinat molecules found at the DNA shuffling library obtained, since these recombinant molecules potentially have improved functionalities in relation to their parent since their sequence may accumulate beneficial mutations originated from distinct parent sequences. Nowadays some few models can be found in the literature whose purpose is to suggest optimization to this process aiming the increase of the genetic diversity of the DNA shuffling library obtained. This research work presents a comparative study of four models used to predict/estimate the DNA shuffling results. In addition a computational tool for simulating the DNA shuffling proccess is proposed and implemented in an environment where other functionalities related to the analyses of the parental sequences and the resulting sequences from the DNA shuffling library is also implemented. / A Evolução Molecular dos organismos vivos é um processo lento que ocorre ao longo dos anos e diz respeito às mutações e recombinações sofridas por um determinado organismo em seu material genético, ou seja, em seu DNA. As mutações ocorrem na forma de remoções, inserções e/ou substituições de nucleotídeos ao logo da cadeia de DNA. A Evolução Molecular Direta é um processo laboratorial, ou seja, in vitro, que visa melhorar funções biológicas específicas de moléculas por meio de mutações/recombinações em seu material genético, imitando o processo natural de evolução. Diversas técnicas que simulam a evolução molecular em laboratório, entre elas a técnica de DNA shuffling, têm sido amplamente utilizadas na tentativa de melhorar determinadas propriedades de uma variedade de produtos comercialmente importantes como vacinas, enzimas industriais e substâncias de interesse famacológico. A metodologia original de DNA shuffling pode ser sumarizada pelas seguintes etapas: 1) seleção dos genes de interesse, dito parentais; 2) fragmentação enzimática dos genes; 3) ciclos de PCR (Polymerase Chain Reaction), para que ocorra a remontagem dos fragmentos; 4) amplificação das seqüências remontadas cujo tamanho é igual a dos parentais. O sucesso ou não da técnica de DNA shuffling pode ser medido pelo número de moléculas recombinantes encontradas na biblioteca de DNA shuffling obtida, uma vez que estas podem apresentar melhorias funcionais em relação aos parentais pelo fato de, possivelmente, acumularem em sua seqüência mutações benéficas presentes em parentais distintos. Atualmente podem ser encontradas na literatura algumas poucas modelagens computacionais capazes de sugerir otimizações para o processo, com vistas em aumentar a diversidade genética da biblioteca resultante. O presente trabalho apresenta um estudo comparativo de quatros modelos para predição/estimativa de resultados de experimentos de DNA shuffling encontrados na literatura bem como a proposta e implementação de uma ferramenta computacional de simulação para o processo de DNA shuffling. A ferramenta de simulação foi implementada em um ambiente que disponibiliza outras funcionalidades referentes à análise das seqüências a serem submetidas ao shuffling bem como ferramentas para análise das seqüências resultantes do processo.

Submitted by Pedro Rafael Costa null (costapr@ibb.unesp.br) on 2016-08-29T12:34:19Z No. of bitstreams: 1 Tese-PedroRafaelCosta.pdf: 3405758 bytes, checksum: db4d115ece49bde1fd0f2a7768c97377 (MD5) / Approved for entry into archive by Ana Paula Grisoto (grisotoana@reitoria.unesp.br) on 2016-08-30T17:27:57Z (GMT) No. of bitstreams: 1 costa_pr_dr_bot.pdf: 3405758 bytes, checksum: db4d115ece49bde1fd0f2a7768c97377 (MD5) / Made available in DSpace on 2016-08-30T17:27:57Z (GMT). No. of bitstreams: 1 costa_pr_dr_bot.pdf: 3405758 bytes, checksum: db4d115ece49bde1fd0f2a7768c97377 (MD5) Previous issue date: 2016-08-23 / Conselho Nacional de Desenvolvimento Científico e Tecnológico (CNPq) / Fundação de Amparo à Pesquisa do Estado de São Paulo (FAPESP) / Uma grande variedade de sequências de RNA presentes nos transcriptomas mas com funções ainda desconhecidas tem estimulado o desenvolvimento de técnicas experimentais e computacionais que colaborem na determinação do papel dessas moléculas. Entretanto, a compreensão dos mecanismos de ação de uma dada molécula de RNA envolve não somente a determinação de sua estrutura de mínima energia livre, mas também o estudo do comportamento de suas conformações metaestáveis. Os algoritmos existentes para predição da estrutura de moléculas de RNA ignoram armadilhas cinéticas que podem levar a formação de estruturas subótimas e utilizam modelos termodinâmicos incompletos, muitas vezes ignorando a formação de estruturas mais complexas, como os pseudonós. Nesse trabalho apresentamos um algoritmo para simulação do dobramento cotranscricional para o estudo dos efeitos da conformação espacial da molécula de RNA na cinética da transcrição. A partir da determinação das conformações permitidas, o algoritmo estabelece uma série de reações de transição entre esses estados, com valores das taxas de ocorrência ponderados através de uma distribuição de probabilidade de Boltzmann baseada na variação de energia livre de Gibbs desses estados. As energias livres das estruturas secundárias são determinadas segundo o modelo dos primeiros vizinhos e dois algoritmos foram implementados para o cálculo da energia livre dos pseudonós. Finalmente, simulações de Monte Carlo baseadas no algoritmo de Gillespie foram realizadas para determinação do caminho de dobramento da molécula. Exemplos de aplicações demonstram o potencial do programa desenvolvido. / The discovery of a wide variety of RNA sequences present in transcriptomes with unknown function has stimulated the development of experimental and computational techniques to determine the function of these molecules. However, understanding the activities of a given RNA molecule involves not only finding its minimum free energy structure, but also studying its metastable structures. The methodologies available for predicting RNA structure ignore kinetic traps that can lead to formation of suboptimal structures and are based in over-simplified thermodynamic models. These methodologies usually can not predict RNA conformations with more complex topologies, such as pseudoknots. In this work we present a computational model for cotranscriptional folding that considers the influence of RNA structures during transcription elongation. After determining the allowed conformations for the sequence of interest, the algorithm established a series of allowed reactions between these structures. The reactions rates are weighted by the Boltzmann factor based on Gibbs free energy variation between the states. The free energies for secondary structures were estimated by the nearest-neighbor model, and two algorithms were implemented to calculate the free energy of pseudoknots. Finally, Monte Carlo simulations based on the Gillespie algorithm were performed to find out the RNA folding path. We show using examples the potential of the software developed. / FAPESP: 2012/19377-4. / CNPq: 152838/2012-0

Orientador: Ney Lemke / Resumo: Uma grande variedade de sequências de RNA presentes nos transcriptomas mas com funções ainda desconhecidas tem estimulado o desenvolvimento de técnicas experimentais e computacionais que colaborem na determinação do papel dessas moléculas. Entretanto, a compreensão dos mecanismos de ação de uma dada molécula de RNA envolve não somente a determinação de sua estrutura de mínima energia livre, mas também o estudo do comportamento de suas conformações metaestáveis. Os algoritmos existentes para predição da estrutura de moléculas de RNA ignoram armadilhas cinéticas que podem levar a formação de estruturas subótimas e utilizam modelos termodinâmicos incompletos, muitas vezes ignorando a formação de estruturas mais complexas, como os pseudonós. Nesse trabalho apresentamos um algoritmo para simulação do dobramento cotranscricional para o estudo dos efeitos da conformação espacial da molécula de RNA na cinética da transcrição. A partir da determinação das conformações permitidas, o algoritmo estabelece uma série de reações de transição entre esses estados, com valores das taxas de ocorrência ponderados através de uma distribuição de probabilidade de Boltzmann baseada na variação de energia livre de Gibbs desses estados. As energias livres das estruturas secundárias são determinadas segundo o modelo dos primeiros vizinhos e dois algoritmos foram implementados para o cálculo da energia livre dos pseudonós. Finalmente, simulações de Monte Carlo baseadas no algoritmo de Gillespie foram ... (Resumo completo, clicar acesso eletrônico abaixo) / Abstract: The discovery of a wide variety of RNA sequences present in transcriptomes with unknown function has stimulated the development of experimental and computational techniques to determine the function of these molecules. However, understanding the activities of a given RNA molecule involves not only finding its minimum free energy structure, but also studying its metastable structures. The methodologies available for predicting RNA structure ignore kinetic traps that can lead to formation of suboptimal structures and are based in over-simplified thermodynamic models. These methodologies usually can not predict RNA conformations with more complex topologies, such as pseudoknots. In this work we present a computational model for cotranscriptional folding that considers the influence of RNA structures during transcription elongation. After determining the allowed conformations for the sequence of interest, the algorithm established a series of allowed reactions between these structures. The reactions rates are weighted by the Boltzmann factor based on Gibbs free energy variation between the states. The free energies for secondary structures were estimated by the nearest-neighbor model, and two algorithms were implemented to calculate the free energy of pseudoknots. Finally, Monte Carlo simulations based on the Gillespie algorithm were performed to find out the RNA folding path. We show using examples the potential of the software developed. / Doutor

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

A árvore de sufixos é uma estrutura dados, que representa em espaço linear todos os fatores de uma palavra, com diversos exemplos de aplicações práticas. Neste trabalho, definimos uma estrutura mais geral: a árvore de Ukkonen. Provamos para ela diversas propriedades combinatórias, dentre quais, a minimalidade em um sentido preciso. Acreditamos que a apresentação aqui oferecida, além de mais geral que as árvores de sufixo, tem a vantagem de oferecer uma descrição explícita da topologia da árvore, de seus vértices, arestas e rótulos, o que não vimos em nenhum outro trabalho. Como aplicações, apresentamos também a árvore esparsa de sufixos (que armazena apenas um subconjunto dos sufixos) e a árvore de k-fatores (que armazena apenas os segmentos de comprimento k, ao invés dos sufixos) definidas como casos particulares das árvores de Ukkonen. Propomos para as árvores esparsas um novo algoritmo de construção com tempo O(n) e espaço O(m), onde n é tamanho da palavra e m é número de sufixos. Para as árvores de k-fatores, propomos um novo algoritmo online com tempo e espaço O(n), onde n é o tamanho da palavra. / The suffix tree is a data structure that represents, in linear space, all factors of a given word, with several examples of practical applications. In this work, we define a more general structure: the Ukkonen\'s tree. We prove many properties for it, among them, its minimality in a precise sense. We believe that this presentation, besides being more general than the suffix trees, has the advantage of offering an explicit description of the tree topology, its vertices, edges and labels, which was not seen in any other work. As applications, we also presents the sparse suffix tree (which stores only a subset of the suffixes) and the k-factor tree (which stores only the substrings of length k, instead of the suffixes), both defined as Ukkonen\'s tree special cases. We propose a new construction algorithm for the sparse suffix trees with time O(n) and space O(m), where n is the size of the word and m is the number of suffixes. For the k-factor trees, we propose a new online algorithm with time and space O(n), where n is the size of the word.

A fosforilação de proteínas é o tipo de modificação pós-traducional mais recorrente nas vias de sinalização, desempenhando papel central numa vasta gama de eventos celulares. Um completo entendimento das circunstâncias que coordenam o evento de fosforilação permanece como um desafio para a ciência, a despeito do crescente número de abordagens e estudos realizados no assunto. Um mecanismo largamente descrito e aceito como essencial para coordenar a fosforilação de proteínas é a existência de sequências de aminoácidos que facilitam a fosforilação, conhecidos como consensos de fosforilação. Nesse modelo, cada proteína quinase reconhece sítios de fosforilação se os mesmos estiverem inseridos em uma sequência específica de resíduos na estrutura primária do substrato. Porém, com o crescente volume de dados sobre fosforilação, é possível notar a existência de sítios que são validados experimentalmente como fosforilados por uma determinada proteína quinase, que não apresentam o consenso de fosforilação. Neste trabalho, foi testada e comprovada a hipótese de que estes sítios de fosforilação sem consenso sequencial apresentam resíduos localizados em regiões da estrutura terciária adjacentes ao sítio de fosforilação, cuja as características estereoquímicas mimetizam um peptídeo substrato contendo o consenso de fosforilação. Para essa avaliação, utilizando substratos da PKA, foi constatado que mais de 90% dos sítios de fosforilação que não apresentam o consenso na estrutura primária, apresentam essa disposição na estrutura terciária. Resíduos distantes na estrutura primária se apresentam próximos espacialmente na estrutura tridimensional, em uma conformação semelhante a de um sítio com o consenso de fosforilação. Com isso nós propomos a existência de sítios conformacionais de fosforilação. Para confirmar que esses sítios conformacionais poderiam ser cruciais no reconhecimento do substrato, foram construídos modelos da interação da proteína quinase com os substratos, visando demonstrar a viabilidade da interação dos resíduos formadores do consenso conformacional com a proteína quinase de maneira análoga a de um substrato com o consenso de fosforilação. Para a comprovação experimental do fenômeno, foi utilizado o modelo de fosforilação da -Tubulina, no qual foi constatada uma fosforilação no resíduo T253 que depende da atuação dos resíduos K163 e K164 para a interação com a proteína quinase, confirmando a coerência do modelo proposto. Diante da novidade da proposta, dos estudos computacionais feitos e da validação conseguida, torna-se clara a relevância de se estudar a estrutura tridimensional dos substratos de fosforilação, não só como uma forma de aprofundar os conhecimentos gerais na área de fosforilação, mas também como uma alternativa com potencial de ser explorada no desenvolvimento de novas tecnologias / Protein phosphorylation is the most frequent type of post-translational modification in signaling pathway, developing a key role in a wide range of cell events. The full understanding of the circumstances that coordinate the phosphorylation event remains a challenge for science, despite the growing number of approaches and studies on the subject. A broadly described and accepted mechanism as essential for the coordination of protein phosphorylation is the existence of amino acids sequences that contribute to phosphorylation occurrence, known as phosphorylation consensus. In this model, each protein kinase is able to recognize phosphorylation sites inserted in a specific sequence on the primary structure. However, as the data about phosphorylation sites increases, it is possible to notice that there are sites that are validated experimentally as phosphorylated by a particular protein kinase, which do not have the consensus phosphorylation. In this work, it was tested and proved that phosphorylation sites without the sequence consensus presents anchors residues, that are close to the phosphorylation site on the tertiary structure, creating a structural conformation that mimics the stereochemical features of a substrate peptide containing the phosphorylation consensus. For this evaluation, using substrates of PKA, it was found that more than 90% of phosphorylation sites that have no consensus on the primary structure, presented this kind of disposition on the tertiary structure. Distant residues in the primary structure are spatially close on the three-dimensional structure, in a conformation similar to a phosphorylation site containing the consensus. Thus we proposed the existence of conformational phosphorylation sites. To confirm that these conformational sites could be crucial in substrate recognition, it was built kinase-substrate models, aiming to demonstrate the feasibility of residues forming the conformational consensus on the substrate to interact with the kinase analogously to a substrate with consensus phosphorylation. For experimental verification of this phenomenon, we used the phosphorylation model of -Tubulin, in which we observed a phosphorylation at residue T253 that depends of residues K163 and K164 to interact with the protein kinase, confirming the consistency of proposed model. Faced with the novelty of the proposal, the computational data and the experimental validation, it becomes clear the importance of studying the three dimensional structure of phosphorylation sites, not only as a way of achieving deeper knowledge on phosphorylation field, but also as a potential prospect to be explored on the development of new technologies