Texto completo
| |
| Autor(es): |
Guilherme Pimentel Telles
Número total de Autores: 1
|
| Tipo de documento: | Tese de Doutorado |
| Imprenta: | Campinas, SP. |
| Instituição: | Universidade Estadual de Campinas (UNICAMP). Instituto de Computação |
| Data de defesa: | 2002-12-12 |
| Membros da banca: |
João Meidanis;
Eduardo Sany Laber;
Arnaldo Mandel;
Arnaldo Vieira Moura;
Jorge Stolfi
|
| Orientador: | João Meidanis |
| 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 (AU) | |
| Processo FAPESP: | 97/12126-4 - Modelos computacionais para mapas físicos de DNA |
| Beneficiário: | Guilherme Pimentel Telles |
| Modalidade de apoio: | Bolsas no Brasil - Doutorado |