skip to main content
Idioma:
Tipo de recurso Mostra resultados com: Mostra resultados com: Índice

Perseus:uma nova técnica para tratar árvores de sufixo persistentes

Carelo, Caio Cesar Mori

Biblioteca Digital de Teses e Dissertações da USP; Universidade de São Paulo; Instituto de Ciências Matemáticas e de Computação 2009-08-31

Acesso online. A biblioteca também possui exemplares impressos.

  • Título:
    Perseus:uma nova técnica para tratar árvores de sufixo persistentes
  • Autor: Carelo, Caio Cesar Mori
  • Orientador: Ciferri, Cristina Dutra de Aguiar
  • Assuntos: Árvore De Sufixo; Bioinformática; Seqüencia De Nucleotídeos; Bioinformatics; Nucleotides Sequence; Suffix Tree
  • Notas: Dissertação (Mestrado)
  • Descrição: 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
  • DOI: 10.11606/D.55.2009.tde-19012010-103825
  • Editor: Biblioteca Digital de Teses e Dissertações da USP; Universidade de São Paulo; Instituto de Ciências Matemáticas e de Computação
  • Data de criação/publicação: 2009-08-31
  • Formato: Adobe PDF
  • Idioma: Português
Links
Voltar para lista de resultados
Ir para página anteriorAnterior Resultado  3 AvançarIr para próxima página

  • Realização: ABCD-USP USP   Logos de Redes Sociais: Freepik

Buscando em bases de dados remotas. Favor aguardar.