Ordenação de sufixos e medidas de similaridade entre cadeias

• Processo: 17/09105-0
• Modalidade de apoio: Bolsas no Brasil - Pós-Doutorado
• Data de Início da vigência: 01 de agosto de 2017
• Data de Término da vigência: 13 de agosto 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
• 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
• Vinculado ao auxílio: 15/50122-0 - Fenômenos dinâmicos em redes complexas: fundamentos e aplicações, AP.TEM
• Bolsa(s) vinculada(s): 18/21509-2 - Transformada de Burrows-Wheeler e grafos De Bruijn sucintos, BE.EP.PD
• Assunto(s): Recuperação da informação
• Palavra(s)-Chave do Pesquisador: conjuntos de cadeias | similaridade entre cadeias | transformada de Burrows-Wheeler | Recuperação de Informação

Resumo

A ordenação de sufixos é um problema fundamental em processamento de cadeias de caracteres presente em muitas aplicações de Bioinformática, Recuperação de informação e Mineração de textos. Esse problema está relacionado com a construção do vetor de sufixos e com a transformada de Burrows-Wheeler, os quais desempenham um papel importante em métodos de indexação de cadeias (e.g. FM-índice) e compressão de dados (e.g. bzip). Na literatura, muitos trabalhos têm sido propostos para construir o vetor de sufixos de uma única cadeia e obter a transformada de Burrows-Wheeler. Entretanto, em muitas situações estamos interessados em processar conjuntos de cadeias e obter diretamente a transformada de Burrows-Wheeler, isto é, sem construir o vetor de sufixos. Poucas soluções têm sido propostas para esses problemas. Dessa forma, o principal objetivo desse projeto é investigar o cálculo direto da transformada de Burrows-Wheeler para conjuntos de cadeias. Além disso, pretende-se investigar medidas de similaridades que utilizam a transformada de Burrows-Wheeler para comparar e classificar cadeias de caracteres.

Publicações científicas

(8)

(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)

LOUZA, FELIPE A.; TELLES, GUILHERME P.; HOFFMANN, STEVE; CIFERRI, CRISTINA D. A.. Generalized enhanced suffix array construction in external memory. Algorithms for Molecular Biology, v. 12, DEC 7 2017. (11/23904-7, 17/09105-0, 11/15423-9)

NOGUEIRA NUNES, DANIEL SAAD; LOUZA, FELIPE A.; GOG, SIMON; AYALA-RINCON, MAURICIO; NAVARRO, GONZALO; BILGIN, A; MARCELLIN, MW; SERRASAGRISTA, J; STORER, JA. A Grammar Compression Algorithm based on Induced Suffix Sorting. 2018 DATA COMPRESSION CONFERENCE (DCC 2018), v. N/A, p. 10-pg., 2018-01-01. (17/09105-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)

LOUZA, FELIPE A.; MHASKAR, NEERJA; SMYTH, W. F.. A new approach to regular & indeterminate strings. THEORETICAL COMPUTER SCIENCE, v. 854, p. 105-115, JAN 16 2021. (17/09105-0)

LOUZA, FELIPE A.; SMYTH, W. F.; MANZINIC, GIOVANNI; TELLES, GUILHERME P.. Lyndon array construction during Burrows-Wheeler inversion. JOURNAL OF DISCRETE ALGORITHMS, v. 50, p. 2-9, MAY 2018. (17/09105-0)

LOUZA, FELIPE A.; TELLES, GUILHERME P.; GOG, SIMON; ZHAO, LIANG; GAGIE, T; MOFFAT, A; NAVARRO, G; CUADROSVARGAS, E. Computing Burrows-Wheeler Similarity Distributions for String Collections. STRING PROCESSING AND INFORMATION RETRIEVAL, SPIRE 2018, v. 11147, p. 12-pg., 2018-01-01. (17/09105-0)