Please use this identifier to cite or link to this item: http://repositorio.unicamp.br/jspui/handle/REPOSIP/276089
Full metadata record
DC FieldValueLanguage
dc.contributor.CRUESPUNIVERSIDADE ESTADUAL DE CAMPINASpt_BR
dc.identifier(Broch.)pt_BR
dc.descriptionOrientador: João Meidanispt_BR
dc.descriptionTese (doutorado) - Universidade Estadual de Campinas, Instituto de Computaçãopt_BR
dc.format.extent195p. : il.pt_BR
dc.format.mimetypeapplication/octet-streampt_BR
dc.languagePortuguêspt_BR
dc.typeTESEpt_BR
dc.titleAnalise algebrica de problemas de rearranjo em genomas : algoritmos e complexidadept_BR
dc.title.alternativeAlgebraic analysis of genome rearrangement problems : algorithms and complexitypt_BR
dc.contributor.authorGomes Mira, Cleber Valgaspt_BR
dc.contributor.advisorMeidanis, João, 1960-pt_BR
dc.contributor.institutionUniversidade Estadual de Campinas. Instituto de Computaçãopt_BR
dc.contributor.nameofprogramPrograma de Pós-Graduação em Ciência da Computaçãopt_BR
dc.subjectBiologia computacionalpt_BR
dc.subjectPermutações (Matemática)pt_BR
dc.subjectOrdenação (Computadores)pt_BR
dc.subject.otherlanguageComputational biologyen
dc.subject.otherlanguagePermutationsen
dc.subject.otherlanguageSorting (Computer science)en
dc.description.abstractResumo: O sucesso na obtenção de cadeias completas de DNA de alguns organismos tem incentivado a busca de novas técnicas computacionais capazes de analisar esse montante de informação para aplicá-lo na descoberta de novos remédios, aumento da produção de alimentos e investigação do processo de evolução dos seres vivos, entre outras aplicações. A comparação de seqüências de DNA (ou RNA) de diferentes espécies é uma das técnicas importantes para desvendar novas propriedades biológicas. Uma das maneiras de se comparar dois genomas é analisar como os dois se distinguem com base em certas mutações chamadas eventos de rearranjo em genomas. Nessa técnica de comparação, um genoma é modelado como uma seqüência de regiões que são conservadas em um conjunto de genomas. O problema de rearranjos em genomas consiste genericamente em encontrar, dados dois genomas como entrada e um conjunto de tipos de eventos de rearranjo permitidos, uma seqüência mínima de tais eventos de rearranjo que transforme um genoma em outro. No formalismo clássico de rearranjos em genomas, um genoma tem sido modelado como um conjunto de seqüências de inteiros. Cada número inteiro representa um gene e o seu sinal representa a orientação do gene no genoma. O problema de rearranjos em genomas nesse modelo é analisado de forma geral por meio de diversos diagramas e grafos que representam certas propriedades do par de genomas na entrada do problema. Neste trabalho, usamos um novo modelo para rearranjos em genomas proposto por Meidanis e Dias [39]: o formalismo algébrico. Em vez de se basear na análise de diagramas, o formalismo algébrico usa permutações na modelagem de genomas e, principalmente, utiliza resultados de grupos de permutações para analisar as propriedades de genomas e os efeitos de eventos de rearranjo. A motivação para o desenvolvimento do formalismo algébrico é a possibilidade de formalização de argumentos sobre rearranjos por meio de métodos algébricos, em vez da utilização de recursos gráficos como é feito no formalismo clássico. Esperamos que, por meio do desenvolvimento de um novo formalismo para o tratamento de problemas de rearranjos em genomas, algoritmos mais eficientes para a resolução desses problemas, ou maneiras mais simples de demonstrar alguns dos resultados clássicos na área sejam encontrados com maior facilidade. Nesse trabalho, apresentamos duas soluções simples e eficientes derivadas diretamente do formalismo algébrico para dois problemas de rearranjos em genomas (o problema de rearranjos em genomas por intercâmbio de blocos e reversões com sinais e o problema de rearranjo em genomas por fissões, fusões e reversões com sinais). Também discutimos e propomos um algoritmo polinomial para o problema de rearranjos em genomas por transposições generalizadas. Acreditamos que o sucesso na solução desses problemas possa ser estendido para outros problemas de rearranjos em genomas com a consolidação dos conceitos fundamentais do formalismo algébrico. Esperamos com essa tese convencer o leitor de que o formalismo algébrico é um modelo representativo e poderoso para tratar genomas compostos por cromossomos circulares e ao lidar com a atribuição de pesos a eventos de rearranjo. Por outro lado, não defendemos que o formalismo clássico seja simplesmente substituído pelo formalismo algébrico. Ambos os formalismos podem ser beneficiados por um processo semelhante, porém em menor escala, ao sucesso do desenvolvimento da Geometria Analítica e da Geometria Tradicionalpt
dc.description.abstractAbstract: The success in obtaining complete sequences of DNA of some species has encouraged the search for new computational techniques for the analysis of such huge amount of information. One hopes that the results of this research could be applied for the development of new medicines, increasing food crops productivity, better understanding of the evolutionary process in live beings, among other applications. One technique for the genome analysis is the comparison of DNA (or RNA) sequences from different species. Such a comparison may reveal the similarities and differences between the genomes, which could be used in phylogeny reconstruction for instance. Two genomes can be compared by the analysis of their differences based on mutational events called genome rearrangements. The genome rearrangement problem (also called a sorting problem) consists of finding a minimum sequence of rearrangement events that transforms one genome into another and the number of rearrangement events in the sequence is called the genomic distance. In the classical formalism for genome rearrangements, a genome is usually modeled by a set of sequences of integers. Each integer represents a gene and its sign stands for the orientation of the gene in the genome. The genome rearrangement problem in this model is analyzed generally with tools such as diagrams and graphs that convey the properties of the genomes in the problem input. We use instead a new model for genome rearrangements proposed by Meidanis and Dias [39]: the algebraic formalism. Instead of being based on the analysis of diagrams, the algebraic formalism uses permutations to model genomes and the results from permutation group theory for the analysis of the properties of genomes and the effects of rearrangement events. The motivation for the development of the algebraic formalism is the possibility of stating arguments more formally by means of algebraic methods than by using graphical resources as the classical formalism does. We hope that more efficient algorithms for genome rearrangement problems or simpler proofs for classical results in the area will be more easily found due to the development of a new formalism. We present a simple, efficient solution based on the algebraic formalism for two genome rearrangement problems (the problem of genome rearrangements by block-interchanges and signed reversals and the problem of genome rearrangements by fissions, fusions, and signed reversals). We also discuss and offer a solution for the problem of genome rearrangements by generalized transpositions. We believe that the success in solving those genome rearrangement problems could be extended to other problems by consolidating the fundamental concepts of the algebraic formalism. We hope that the reader will be convinced that the algebraic formalism is representative and powerful in dealing with circular chromosomes and modeling the assignment of weights to rearrangement events. On the other hand, we do not argue in favor of a substitution of the classical formalism by the algebraic formalism. Both of these formalisms could profit by a similar, even though on a smaller scale, success of the development of the Analytic Geometry and the Traditional Geometryen
dc.publisher[s.n.]pt_BR
dc.date.issued2007pt_BR
dc.identifier.citationGOMES MIRA, Cleber Valgas. Analise algebrica de problemas de rearranjo em genomas: algoritmos e complexidade. 2007. 195p. Tese (doutorado) - Universidade Estadual de Campinas, Instituto de Computação, Campinas, SP. Disponível em: <http://www.repositorio.unicamp.br/handle/REPOSIP/276089>. Acesso em: 10 ago. 2018.pt_BR
dc.description.degreelevelDoutoradopt_BR
dc.description.degreenameDoutor em Ciência da Computaçãopt_BR
dc.contributor.committeepersonalnameWalter, Maria Emilia Machado Tellespt_BR
dc.contributor.committeepersonalnameFigueiredo, Celina Miraglia Herrera dept_BR
dc.contributor.committeepersonalnameDias, Zanonipt_BR
dc.contributor.committeepersonalnameSouza, Cid Carvalho dept_BR
dc.date.defense2007-10-19T00:00:00Zpt_BR
dc.date.available2018-08-11T00:56:27Z-
dc.date.accessioned2018-08-11T00:56:27Z-
dc.description.provenanceMade available in DSpace on 2018-08-11T00:56:27Z (GMT). No. of bitstreams: 1 GomesMira_CleberValgas_D.pdf: 1443128 bytes, checksum: adcf8d553b49f20bbad0fc0f56cc2aba (MD5) Previous issue date: 2007en
dc.identifier.urihttp://repositorio.unicamp.br/jspui/handle/REPOSIP/276089-
Appears in Collections:IC - Tese e Dissertação

Files in This Item:
File SizeFormat 
GomesMira_CleberValgas_D.pdf1.41 MBAdobe PDFView/Open


Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.