Matchtigs: minimum plain text representation of k-mer sets

Area of Science:

• Bioinformatics
• Computational Biology
• Genomics

Background:

• K-mer sets are fundamental in bioinformatics for sequence analysis.
• Current methods for representing k-mer sets, such as unitigs, can be large and inefficient.
• Compressing these representations is crucial for handling large genomic datasets.

Purpose of the Study:

• To develop a polynomial algorithm for computing a minimum plain-text representation of k-mer sets.
• To introduce an efficient near-minimum greedy heuristic for k-mer set compression.
• To evaluate the performance of the proposed methods in terms of size reduction and query speed.

Main Methods:

• A novel polynomial-time algorithm for minimum plain-text representation of k-mer sets.
• An efficient greedy heuristic for near-minimum representation.
• Benchmarking against unitigs and previous methods on large model organism and bacterial pangenome datasets.
• Performance evaluation of downstream applications, specifically SSHash-Lite queries.

Main Results:

• Achieved up to 59% size reduction compared to unitigs and 26% over previous work.
• Reduced the number of strings by up to 97% compared to unitigs and 90% over previous work.
• Accelerated SSHash-Lite queries by up to 4.26× over unitigs and 2.10× over previous work.
• Demonstrated these improvements with only a minor increase in runtime.

Conclusions:

• The proposed algorithm and heuristic offer significant improvements in compressing k-mer sets.
• Smaller representations lead to substantial benefits in storage and computational efficiency for genomic data.
• The enhanced representation speeds up critical downstream bioinformatics tasks, making large-scale genomic analysis more feasible.