Generalized enhanced suffix array construction in external memory.

Area of Science:

• Bioinformatics
• Computational Biology
• Data Structures

Background:

• Suffix arrays and augmented data structures are crucial for efficient string processing.
• External memory construction of generalized suffix arrays is vital for large datasets exceeding internal memory.

Purpose of the Study:

• To present and analyze a new external memory algorithm for constructing generalized suffix arrays augmented with the longest common prefix array.
• To evaluate the algorithm's performance on large-scale string collections.

Main Methods:

• The algorithm combines buffers, induced sorting, and a heap to avoid direct string comparisons.
• External memory approach designed for datasets larger than available RAM.

Main Results:

• The algorithm, [Formula: see text], shows competitive performance against existing methods on real datasets up to 24 GB.
• Evaluated running time, efficiency, memory access, and optimization strategies.
• Demonstrated the impact of operating system disk caching on performance.

Conclusions:

• The algorithm is validated on diverse real-world datasets, proving its competitive performance.
• The algorithm efficiently constructs generalized suffix arrays and longest common prefix arrays.
• It can also construct the generalized Burrows-Wheeler transform with minimal overhead.