gsufsort: constructing suffix arrays, LCP arrays and BWTs for string collections

Area of Science:

• Bioinformatics
• Computational Biology
• String Algorithms

Background:

• Suffix array construction is crucial for string processing tasks.
• Efficient algorithms for string collections are less developed than for single strings.
• Related data structures like LCP array and BWT are essential for many applications.

Purpose of the Study:

• Introduce gsufsort, an open-source software for suffix array construction.
• Provide a linear-time (O(N)) solution for string collections.
• Support large FASTA, FASTQ, and text files with multiple strings.

Main Methods:

• Implementation of the gSACA-K algorithm in ANSI/C.
• Development of a tool named gsufsort.
• Utilizing linear-time suffix array construction for collections.

Main Results:

• gsufsort achieves O(N) time complexity for suffix array and related structure construction.
• The tool demonstrates excellent performance across various string types.
• Supports efficient processing of large multi-string files.

Conclusions:

• gsufsort is a fast, portable, and lightweight tool.
• Enables efficient suffix array and data structure construction for string collections.
• Offers a valuable resource for bioinformatics and other string-intensive fields.