Busca avançada
Ano de início
Entree
Conteúdo relacionado

Transformada de Burrows-Wheeler e grafos De Bruijn sucintos

Processo: 18/21509-2
Modalidade de apoio:Bolsas no Exterior - Estágio de Pesquisa - Pós-Doutorado
Data de Início da vigência: 15 de dezembro de 2018
Data de Término da vigência: 14 de março de 2019
Área de conhecimento:Ciências Exatas e da Terra - Ciência da Computação - Metodologia e Técnicas da Computação
Pesquisador responsável:Zhao Liang
Beneficiário:Felipe Alves da Louza
Supervisor: Giovanni Manzini
Instituição Sede: Faculdade de Filosofia, Ciências e Letras de Ribeirão Preto (FFCLRP). Universidade de São Paulo (USP). Ribeirão Preto , SP, Brasil
Instituição Anfitriã: Consiglio Nazionale delle Ricerche (CNR), Itália  
Vinculado à bolsa:17/09105-0 - Ordenação de sufixos e medidas de similaridade entre cadeias, BP.PD
Assunto(s):Recuperação da informação   Algoritmos
Palavra(s)-Chave do Pesquisador:Algoritmos | estruturas de dados sucintas | grafos de bruijn | Processamento de Textos | transformada de Burrows-Wheeler | Recuperação de Informação

Resumo

O projeto de pós-doutorado desenvolvido pelo candidato investiga algoritmos para calcular a Transformada de Burrows-Wheeler (BWT), e medidas de similaridade entre textos baseadas na BWT. Recentemente, Egidi, Louza, Manzini e Telles [7] introduziram um algoritmo para calcular em memória externa a BWT o vetor LCP para conjuntos de textos, e descreveram como calcular o vetor de documentos (DA) em conjunto com a BWT. Os autores também introduziram um algoritmo para construir o grafo de Bruijn diretamente em uma representação sucinta utilizando a BWT e o vetor DA. O objetivo desse projeto é implementar a construção do vetor DA em memória externa, e apresentar o primeiro algoritmo prático para construir o grafo de Bruijn sucinto para grandes conjuntos de textos.

Matéria(s) publicada(s) na Agência FAPESP sobre a bolsa:
Mais itensMenos itens
Matéria(s) publicada(s) em Outras Mídias ( ):
Mais itensMenos itens
VEICULO: TITULO (DATA)
VEICULO: TITULO (DATA)

Publicações científicas
(Referências obtidas automaticamente do Web of Science e do SciELO, por meio da informação sobre o financiamento pela FAPESP e o número do processo correspondente, incluída na publicação pelos autores)
EGIDI, LAVINIA; LOUZA, FELIPE A.; MANZINI, GIOVANNI. Space Efficient Merging of de Bruijn Graphs and Wheeler Graphs. ALGORITHMICA, . (17/09105-0, 18/21509-2)
LOUZA, FELIPE A.; TELLES, GUILHERME P.; GOG, SIMON; ZHAO, LIANG. Algorithms to compute the Burrows-Wheeler Similarity Distribution. THEORETICAL COMPUTER SCIENCE, v. 782, p. 145-156, . (17/09105-0, 18/21509-2, 15/50122-0)
EGIDI, LAVINIA; LOUZA, FELIPE A.; MANZINI, GIOVANNI; TELLES, GUILHERME P.. External memory BWT and LCP computation for sequence collections with applications. Algorithms for Molecular Biology, v. 14, . (17/09105-0, 18/21509-2)