Direct construction of sparse suffix arrays with Libsais

Area of Science:

• Bioinformatics
• Computational Biology
• Data Structures

Background:

• Pattern matching is crucial for genomics, transcriptomics, and proteomics.
• Suffix arrays are key indexing structures for large datasets.
• Sparse suffix arrays (SSAs) reduce memory but typically require full suffix array construction first, causing high overhead.

Purpose of the Study:

• To present a novel method for direct sparse suffix array construction.
• To reduce memory usage and construction time for SSAs.
• To improve the efficiency of pattern matching in large biological datasets.

Main Methods:

• Developed a text encoding method to group characters and reduce input text length.
• Extended the Libsais library to directly construct SSAs from the encoded text.
• Implemented a subsampling strategy for higher sparseness factors.

Main Results:

• Achieved 50-75% reduction in memory usage and construction time for SSAs (k=3, 4) on nucleotide and amino acid datasets.
• Demonstrated similar performance gains for sparseness factors up to 8, depending on alphabet size.
• The method is particularly effective for small alphabets common in bioinformatics.

Conclusions:

• Introduced an efficient method for constructing sparse suffix arrays.
• Text transformation and direct SSA construction via Libsais significantly improve execution time and memory usage.
• The approach reduces input text and SSA length by a factor of k.