Um algoritmo para a construção de vetores de sufixo generalizados em memória externa (2013)
- Authors:
- Autor USP: LOUZA, FELIPE ALVES DA - ICMC
- Unidade: ICMC
- Sigla do Departamento: SCC
- Subjects: BIOINFORMÁTICA; ESTRUTURAS DE DADOS; COMPUTAÇÃO EM NUVEM; BANCO DE DADOS DISTRIBUÍDOS; SISTEMAS DE INFORMAÇÃO
- Keywords: Biological data; Dados biológicos; External memory; Generalized suffix array; Genome assembly; Indexação; Indexing; Memória externa; Montagem de genomas; Vetor de sufixo generalizado
- Language: Português
- Abstract: O vetor de sufixo é uma estrutura de dados importante utilizada em muitos problemas que envolvem cadeias de caracteres. Na literatura, muitos trabalhos têm sido propostos para a construção de vetores de sufixo em memória externa. Entretanto, esses trabalhos não enfocam conjuntos de cadeias, ou seja, não consideram vetores de sufixo generalizados. Essa limitação motiva esta dissertação, a qual avança no estado da arte apresentando o algoritmo eGSA, o primeiro algoritmo proposto para a construção de vetores de sufixo generalizados aumentado com o vetor de prefixo comum mais longo (LCP) e com a transformada de Burrows-Wheeler (BWT) em memória externa. A dissertação foi desenvolvida dentro do contexto de bioinformática, já que avanços tecnológicos recentes têm aumentado o volume de dados biológicos disponíveis, os quais são armazenados como cadeias de caracteres. O algoritmo eGSA foi validado por meio de testes de desempenho com dados reais envolvendo sequências grandes, como DNA, e sequências pequenas, como proteínas. Com relação aos testes comparativos com conjuntos de grandes cadeias de DNA, o algoritmo proposto foi comparado com o algoritmo correlato mais eficiente na literatura de construção de vetores de sufixo, o qual foi adaptado para construção de vetores generalizados. O algoritmo eGSA obteve um tempo médio de 3,2 a 8,3 vezes menor do que o algoritmo correlato e consumiu 50% menos de memória. Para conjuntos de cadeias pequenas de proteínas, foram realizados testes dedesempenho apenas com o eGSA, já que no melhor do nosso conhecimento, não existem trabalhos correlatos que possam ser adaptados. Comparado com o tempo médio para conjuntos de cadeias grandes, o eGSA obteve tempos competitivos para conjuntos de cadeias pequenas. Portanto, os resultados dos testes demonstraram que o algoritmo proposto pode ser aplicado eficientemente para indexar tanto conjuntos de cadeias grandes quanto conjuntos de cadeias pequenas
- Imprenta:
- Publisher place: São Carlos
- Date published: 2013
- Data da defesa: 17.12.2013
-
ABNT
LOUZA, Felipe Alves da. Um algoritmo para a construção de vetores de sufixo generalizados em memória externa. 2013. Dissertação (Mestrado) – Universidade de São Paulo, São Carlos, 2013. Disponível em: http://www.teses.usp.br/teses/disponiveis/55/55134/tde-26032014-100626/. Acesso em: 21 maio 2024. -
APA
Louza, F. A. da. (2013). Um algoritmo para a construção de vetores de sufixo generalizados em memória externa (Dissertação (Mestrado). Universidade de São Paulo, São Carlos. Recuperado de http://www.teses.usp.br/teses/disponiveis/55/55134/tde-26032014-100626/ -
NLM
Louza FA da. Um algoritmo para a construção de vetores de sufixo generalizados em memória externa [Internet]. 2013 ;[citado 2024 maio 21 ] Available from: http://www.teses.usp.br/teses/disponiveis/55/55134/tde-26032014-100626/ -
Vancouver
Louza FA da. Um algoritmo para a construção de vetores de sufixo generalizados em memória externa [Internet]. 2013 ;[citado 2024 maio 21 ] Available from: http://www.teses.usp.br/teses/disponiveis/55/55134/tde-26032014-100626/
How to cite
A citação é gerada automaticamente e pode não estar totalmente de acordo com as normas
