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.

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, JUL 2021. (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, AUG 23 2019. (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, MAR 8 2019. (17/09105-0, 18/21509-2)