Perseus: uma nova técnica para tratar árvores de sufixo persistentes (2009)
- Authors:
- Autor USP: CARELO, CAIO CESAR MORI - ICMC
- Unidade: ICMC
- Sigla do Departamento: SCC
- Subjects: BIOINFORMÁTICA (MÉTODOS DE LABORATÓRIO;TÉCNICAS MOLECULARES); CIÊNCIA DA COMPUTAÇÃO (METODOLOGIA;TÉCNICAS); TECNOLOGIA DA INFORMAÇÃO
- Language: Português
- Abstract: 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 considerandogenomas 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çãoe á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
- Imprenta:
- Publisher place: São Carlos
- Date published: 2009
- Data da defesa: 31.08.2009
-
ABNT
CARÉLO, Caio Cesar Mori. Perseus: uma nova técnica para tratar árvores de sufixo persistentes. 2009. Dissertação (Mestrado) – Universidade de São Paulo, São Carlos, 2009. Disponível em: http://www.teses.usp.br/teses/disponiveis/55/55134/tde-19012010-103825/. Acesso em: 27 abr. 2024. -
APA
Carélo, C. C. M. (2009). Perseus: uma nova técnica para tratar árvores de sufixo persistentes (Dissertação (Mestrado). Universidade de São Paulo, São Carlos. Recuperado de http://www.teses.usp.br/teses/disponiveis/55/55134/tde-19012010-103825/ -
NLM
Carélo CCM. Perseus: uma nova técnica para tratar árvores de sufixo persistentes [Internet]. 2009 ;[citado 2024 abr. 27 ] Available from: http://www.teses.usp.br/teses/disponiveis/55/55134/tde-19012010-103825/ -
Vancouver
Carélo CCM. Perseus: uma nova técnica para tratar árvores de sufixo persistentes [Internet]. 2009 ;[citado 2024 abr. 27 ] Available from: http://www.teses.usp.br/teses/disponiveis/55/55134/tde-19012010-103825/
How to cite
A citação é gerada automaticamente e pode não estar totalmente de acordo com as normas
