Enhanced Compression of k-Mer Sets with Counters via de Bruijn Graphs.

Area of Science:

• Computational genomics
• Bioinformatics
• Data compression

Background:

• Efficient representation of k-mer sets is vital for scalable bioinformatics.
• De Bruijn graphs (dBGs) are commonly used for k-mer set representation.
• Finding compact graph representations via smallest path cover is a key challenge.

Purpose of the Study:

• Introduce USTAR* (Unitig STitch Advanced constRuction), a novel tool for compressing k-mer sets and their counts.
• Improve upon existing methods for k-mer set compression.
• Enhance the scalability of bioinformatic analyses.

Main Methods:

• Leveraging the connectivity and density of de Bruijn graphs (dBGs).
• Developing an efficient path selection algorithm for constructing the path cover.
• Applying USTAR* to compress real-world read data sets.

Main Results:

• USTAR* achieves improved compression percentages ranging from 2.3% to 26.4% over the UST algorithm.
• Compression efficiency is dependent on the k-mer size.
• USTAR* demonstrates significant speed improvements, up to $$ times faster.

Conclusions:

• USTAR* offers a more efficient method for compressing k-mer sets and counts.
• The tool enhances scalability for computational genomics and bioinformatics.
• USTAR* represents a significant advancement in k-mer data representation and compression.