FroM Superstring to Indexing: a space-efficient index for unconstrained k-mer sets using the Masked Burrows-Wheeler...

Area of Science:

• Bioinformatics
• Computational Biology
• Genomics

Background:

• Genomic data is rapidly increasing in volume and complexity.
• Current k-mer-set indexes like SBWT and SSHash face limitations with small k values, sampled data, and high-diversity datasets due to their reliance on de Bruijn graphs.
• Scalable and versatile indexing methods are crucial for analyzing large genomic datasets.

Purpose of the Study:

• To develop a novel indexing method for arbitrary k-mer sets that overcomes the limitations of existing approaches.
• To provide efficient membership and compressed dictionary queries with theoretical guarantees.
• To establish a robust and scalable framework for diverse bioinformatics applications.

Main Methods:

• Introduction of FMSI (Fast Masked Superstring Index), a superstring-based index.
• Utilizes the Masked Burrows-Wheeler Transform (MBWT), an extension of the classical Burrows-Wheeler Transform incorporating position masking.
• Evaluated FMSI across various k values and dataset types, including genomic, pangenomic, and metagenomic data.

Main Results:

• FMSI demonstrates superior query space efficiency, using 2-3x less memory than state-of-the-art methods.
• Maintains competitive query times, outperforming even space-optimized SBWT by 2-3x in speed.
• Achieves consistent performance across different k values and dataset types.

Conclusions:

• Superstring-based indexing, exemplified by FMSI, provides a robust, scalable, and versatile framework for arbitrary k-mer sets.
• FMSI significantly advances the efficiency of genomic data indexing and analysis.
• The developed method is suitable for a wide range of bioinformatics applications.