Detalhes bibliográficos
| Ano de defesa: |
2009 |
| Autor(a) principal: |
Carelo, Caio Cesar Mori |
| Orientador(a): |
Não Informado pela instituição |
| Banca de defesa: |
Não Informado pela instituição |
| Tipo de documento: |
Dissertação
|
| Tipo de acesso: |
Acesso aberto |
| Idioma: |
por |
| Instituição de defesa: |
Biblioteca Digitais de Teses e Dissertações da USP
|
| Programa de Pós-Graduação: |
Não Informado pela instituição
|
| Departamento: |
Não Informado pela instituição
|
| País: |
Não Informado pela instituição
|
| Palavras-chave em Português: |
|
| Link de acesso: |
http://www.teses.usp.br/teses/disponiveis/55/55134/tde-19012010-103825/
|
Resumo: |
O avanço tecnológico dos laboratórios de biologia molecular tem proporcionado um grande aumento no volume de seqüências de nucleotídeos armazenadas em bancos de dados biológicos, introduzindo o desafio de pesquisar eficientemente estes dados. Neste contexto, a árvore de sufixo é um método de acesso utilizado por muitas aplicações que envolvem pesquisa em dados biológicos. Entretanto, o custo de construção das árvores de sufixo é alto devido ao tamanho da estrutura de indexação gerado e à necessidade da árvore de sufixo caber em memória principal para ser construída com complexidade linear em relação ao tempo. Esta dissertação propõe o Perseus, uma nova técnica para tratar árvores de sufixo persistentes. A técnica Perseus apresenta os seguintes diferenciais. Ela introduz uma abordagem que realiza a construção de árvores de sufixo persistentes cujos tamanhos podem exceder a capacidade da memória principal. Além disso, ela provê um algoritmo que constrói árvores de sufixo por meio do particionamento destas árvores somente quando necessário. Esta construção também permite que o usuário escolha quais subseqüências de uma seqüência devem ser indexadas, de acordo com os requisitos particulares de suas aplicações. Por fim, a técnica proposta também introduz um algoritmo de casamento exato que permite a busca por uma seqüência de consulta em árvores de sufixo que podem estar particionadas. A validação do Perseus foi realizada por meio de testes de desempenho considerando genomas de vários organismos, os quais possuem diferentes ordens de magnitude de tamanho. Os resultados obtidos foram comparados com a técnica Trellis+, a qual representa o estado da arte nesta linha de pesquisa. Os testes indicaram que o Perseus construiu árvores de sufixo mais rapidamente do que o Trellis+, reduzindo o tempo total gasto na construção em até 24%. Perseus também criou árvores de sufixo mais compactas, atingindo uma redução média de 27% no espaço de memória secundária utilizado. Já com relação ao tempo total gasto no processamento de consultas, Perseus sempre produziu os melhores resultados, respondendo consultas em média 49% mais rápido do que o seu principal concorrente. Com relação à indexação de subseqüências escolhidas pelo usuário, comparando os resultados obtidos com o Trellis+, os testes mostraram que Perseus proveu uma redução no tempo de construção de árvores de sufixo de 97% na média e uma redução no tempo gasto no processamento de consultas de genes de 93% na média |
