Orientador : João Meidanis / Tese (doutorado) - Universidade Estadual de Campinas, Instituto de Matematica, Estatistica e Computação Cientifica / Made available in DSpace on 2018-08-03T14:23:48Z (GMT). No. of bitstreams: 1
Telles_GuilhermePimentel_D.pdf: 2708887 bytes, checksum: b728e7b5eaa59e830b3ce288b3c90dd6 (MD5)
Previous issue date: 2003 / 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
| Identifer | oai:union.ndltd.org:IBICT/oai:repositorio.unicamp.br:REPOSIP/276332 |
| Date | 12 December 2002 |
| Creators | Telles, Guilherme Pimentel, 1972- |
| Contributors | UNIVERSIDADE ESTADUAL DE CAMPINAS, Meidanis, João, 1960-, Laber, Eduardo Sany, Mandel, Arnaldo, Moura, Arnaldo Vieira, Stolfi, Jorge |
| Publisher | [s.n.], Universidade Estadual de Campinas. Instituto de Matemática, Estatística e Computação Científica |
| Source Sets | IBICT Brazilian ETDs |
| Language | Portuguese |
| Detected Language | Portuguese |
| Type | info:eu-repo/semantics/publishedVersion, info:eu-repo/semantics/doctoralThesis |
| Format | 90p. : il., application/octet-stream |
| Source | reponame:Repositório Institucional da Unicamp, instname:Universidade Estadual de Campinas, instacron:UNICAMP |
| Rights | info:eu-repo/semantics/openAccess |
Page generated in 0.0137 seconds