Bitpacking techniques for indexing genomes: II. Enhanced suffix arrays

Area of Science:

• Bioinformatics
• Computational Biology
• Genomic Data Analysis

Background:

• Suffix arrays and enhanced suffix arrays (ESAs) are crucial for genomic search applications.
• ESAs offer fast search speeds but require substantial memory for auxiliary data.
• This study focuses on compressing ESAs to improve genomic search efficiency and reduce memory footprints.

Purpose of the Study:

• To explore compression techniques for enhanced suffix arrays (ESAs).
• To accelerate genomic search and minimize memory requirements for large-scale genome data.
• To evaluate the impact of different compression strategies on search performance and space efficiency.

Main Methods:

• Evaluation of bitpacking and bytecoding techniques for integer compression within ESAs.
• Implementation and testing of exception guide arrays for efficient retrieval of auxiliary information.
• Integration of discriminating character arrays to minimize memory accesses during genomic search.
• Analysis of combined compression strategies including integrated data storage.

Main Results:

• Bytecoding with an exception guide array proved to be the fastest method for auxiliary information retrieval across multiple genomes.
• A discriminating character array further accelerated genomic searching by reducing memory accesses.
• Integrating storage of auxiliary and discriminating character arrays led to additional speed improvements.
• The proposed compression methods were evaluated on the fly, chicken, and human genomes.

Conclusions:

• The combined approach of exception guide arrays, discriminating character arrays, and integrated data storage offers substantial speedups for genomic searching.
• This integrated compression strategy provides a 2- to 3-fold increase in search speed compared to bytecoding alone.
• The optimized ESA is 20% faster and 40% more space-efficient than an uncompressed ESA, demonstrating significant performance gains.