Busca avançada
Ano de início
Entree

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.

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 (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, . (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)
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, . (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., . (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, . (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, . (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, . (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., . (17/09105-0)