Busca avançada
Ano de início
Entree
(Referência obtida automaticamente do Web of Science, por meio da informação sobre o financiamento pela FAPESP e o número do processo correspondente, incluída na publicação pelos autores.)

Algorithms to compute the Burrows-Wheeler Similarity Distribution

Texto completo
Autor(es):
Louza, Felipe A. [1] ; Telles, Guilherme P. [2] ; Gog, Simon [3] ; Zhao, Liang [1]
Número total de Autores: 4
Afiliação do(s) autor(es):
[1] Univ Sao Paulo, Dept Comp & Math, Ribeirao Preto - Brazil
[2] Univ Estadual Campinas, Inst Comp, Campinas, SP - Brazil
[3] eBay Inc, San Jose, CA - USA
Número total de Afiliações: 3
Tipo de documento: Artigo Científico
Fonte: THEORETICAL COMPUTER SCIENCE; v. 782, p. 145-156, AUG 23 2019.
Citações Web of Science: 1
Resumo

The Burrows-Wheeler transform (BWT) is a well studied text transformation widely used in data compression and text indexing. The BWT of two strings can also provide similarity measures between them, based on the observation that the more their symbols are intermixed in the transformation, the more the strings are similar. In this article we present two new algorithms to compute similarity measures based on the BWT for string collections. In particular, we present practical and theoretical improvements to the computation of the Burrows-Wheeler Similarity Distribution for all pairs of strings in a collection. Our algorithms take advantage of the BWT computed for the concatenation of all strings, and use compressed data structures that allow reducing the running time with a small memory footprint, as shown by a set of experiments with real and artificial datasets. (C) 2019 Elsevier B.V. All rights reserved. (AU)

Processo FAPESP: 18/21509-2 - Transformada de Burrows-Wheeler e grafos de Bruijn sucintos
Beneficiário:Felipe Alves da Louza
Linha de fomento: Bolsas no Exterior - Estágio de Pesquisa - Pós-Doutorado
Processo FAPESP: 17/09105-0 - Ordenação de sufixos e medidas de similaridade entre cadeias
Beneficiário:Felipe Alves da Louza
Linha de fomento: Bolsas no Brasil - Pós-Doutorado
Processo FAPESP: 15/50122-0 - Fenômenos dinâmicos em redes complexas: fundamentos e aplicações
Beneficiário:Elbert Einstein Nehrer Macau
Linha de fomento: Auxílio à Pesquisa - Temático