Direct construction of sparse suffix arrays with Libsais.

ABSTRACT:

Background

Pattern matching is a fundamental challenge in bioinformatics, especially in the fields of genomics, transcriptomics and proteomics. Efficient indexing structures, such as suffix arrays, are critical for searching large datasets. A sparse suffix array (SSA) retains only suffixes at every k-th position in the text, where k is the sparseness factor. While sparse suffix arrays offer significant memory savings compared to full suffix arrays, they typically still require the construction of a full suffix array prior to a sampling step, resulting in substantial memory overhead during the construction phase.

Results

We present an alternative method to directly construct the sparse suffix array using a simple, yet powerful text encoding. This encoding reduces the input te

SUBMITTER: Van de Vyver S 

PROVIDER: S-EPMC12535041 | biostudies-literature | 2025 Oct

REPOSITORIES: biostudies-literature