A space-efficient construction of the Burrows-Wheeler transform for genomic data.

Area of Science:

• Computational Biology
• Bioinformatics
• Data Structures

Background:

• Exact string matching algorithms are vital in computational biology.
• Suffix trees and suffix arrays are common data structures for these tasks.
• Growing sequence databases necessitate more space-efficient exact matching approaches.

Purpose of the Study:

• To develop a more space-efficient algorithm for constructing compressed suffix arrays (CSAs).
• To reduce memory requirements for CSA construction, particularly for small alphabets like nucleotide sequences.
• To demonstrate the practicality of the new CSA construction and querying implementation using real genome data.

Main Methods:

• Implementation of a novel compressed suffix array (CSA) construction algorithm.
• Focus on achieving asymptotic time and space bounds for CSA construction.
• Utilizing the Burrows-Wheeler transform as the basis for the CSA.

Main Results:

• The new implementation achieves asymptotic bounds for CSA construction and querying.
• It uses 1/2 (1+|summation|)(1+epsilon) bits per character for small alphabets, a 2x space reduction for nucleotide sequences compared to prior methods.
• Experimental results on publicly available genome data validate the approach's efficiency.

Conclusions:

• The developed CSA construction algorithm offers significant space savings for biological sequence data.
• This advancement makes large-scale sequence analysis more feasible by reducing memory footprint.
• The practical performance on genome data confirms the utility of this space-efficient approach.