Felipe Alves da Louza

We present a simple grammar-based compression strategy derived from the factorization used in the DC3 suffix-sorting algorithm that supports fast substring extraction. The input string is partitioned into non-overlapping substrings of fixed length X, which are sorted and mapped to grammar productions. Each substring is then replaced by its lexicographic rank, producing a reduced string that is recursively processed until all substrings become distinct. Experiments on highly repetitive datasets show that two algorithms implementing this strategy support fast compression and decompression, and provide remarkably efficient random access and substring extraction without requiring full decompression. In these operations, they outperform classical methods such as Re-Pair, Block Trees, and GCIS, although at the cost of higher compression ratios. Nevertheless, for applications where extraction speed is critical, the proposed algorithms offer compelling practical alternatives.

We present an extension of the in-place BWT algorithm of Crochemore et al. [8] that enables the construction of the Lyndon array using O(1) extra space. Our approach incrementally maintains the lexicographic ranks of the suffixes during the right-to-left BWT construction and then derives the Lyndon array through a simple next-smaller-value procedure. Although not intended for practical use due to its quadratic running time, the method is conceptually simple and works for unbounded alphabets.

Este trabalho investiga estratégias para reduzir o consumo de memória durante a compressão de matrizes com suporte a operações algébricas diretamente sobre a representação comprimida. Em particular, mostramos como modificar o método mm-RePair [Ferragina et al., 2022] realizando a compressão de grandes matrizes de forma particionada, dividindo-as em blocos de linhas consecutivas, que são processados sequencialmente utilizando menos memória. O método proposto mantém o suporte a operações de multiplicação sobre os dados comprimidos e, embora provoque uma pequena piora na taxa de compressão, reduz significativamente o consumo de memória conforme o número de blocos aumenta, possibilitando a sua aplicação em situações em que a matriz é maior do que a memória disponível.

Finding shortest unique substrings (SUS) is a fundamental problem in string processing with applications in bioinformatics. In this paper, we present an algorithm for solving a variant of the SUS problem, the left-bounded shortest unique substrings (LSUS). This variant is particularly important in applications such as PCR primer design. Our algorithm runs in O(n) time using 2n memory words plus n bytes for an input string of length n. Experimental results with real and artificial datasets show that our algorithm is the fastest alternative in practice, being two times faster (on the average) than related works, while using a similar peak memory footprint.

DNA technologies have evolved significantly in the past years enabling the sequencing of a large number of genomes in a short time. Nevertheless, the underlying computational problem is hard, and many technical factors and limitations complicate obtaining the complete sequence of a genome. Many genomes are left in a draft state, in which each chromosome is represented by a set of sequences with partial information on their relative order. Recently, some approaches have been proposed to compare draft genomes by comparing paths in de Bruijn graphs, which are constructed by many practical genome assemblers. In this article we introduce gcBB, a method for comparing genomes represented as succinct colored de Bruijn graphs directly, without resorting to sequence alignments, by means of the entropy and expectation measures based on the Burrows-Wheeler Similarity Distribution. We also introduce an improved version of gcBB, called mgcBB, that improves the time performance considerably through the selection of different data structures. We have compared phylogenies of genomes obtained by other methods to those obtained with gcBB, achieving promising results.

Neste artigo apresentamos uma estrutura de dados compacta para o vetor de sufixos métrico (MSA), um índice baseado em permutações para consultas por similaridade. A estrutura proposta utiliza codificação de inteiros de tamanho variável para armazenar os valores do MSA, os quais são decodificados durante as consultas. A estrutura compacta é construída diretamente dos dados, sem a necessidade de computar o MSA para depois compactá-lo, o que permite a indexação de maiores volumes de dados. Em experimentos com dados de alta dimensionalidade extraídos de 20 milhões de imagens, nossa representação compacta utilizou 33% da memória total do método original, com aumento no tempo das consultas por um fator de 3,4.

We evaluate the influence of different alphabet orderings on the Lyndon factorization of a string. Experiments with Pizza&Chili datasets show that for most alphabet reorderings, the number of Lyndon factors is usually small, and the length of the longest Lyndon factor can be as large as the input string, which is unfavorable for algorithms and indexes that depend on the number of Lyndon factors. We present results with randomized alphabet permutations that can be used as a baseline to assess the effectiveness of heuristics and methods designed to modify the Lyndon factorization of a string via alphabet reordering.