UST

UST constructs a spectrum-preserving string set (SPSS) representation of k-mer sets to produce space-efficient, spectrum-preserving representations for genomic analysis and sequence assembly.

Key Features:

• Spectrum-Preserving String Set (SPSS): Converts k-mers into a compact SPSS that preserves the original k-mer spectrum in a smaller string set.
• Graph-Theoretical Foundation: Models k-mers using the compacted de Bruijn graph and formulates SPSS construction as the problem of finding the smallest path cover in that graph.
• Greedy Algorithm (UST): Implements a greedy algorithm named UST that produces representations smaller than traditional unitigs and closely approximates a theoretical lower bound on SPSS size.
• Theoretical Lower Bound: Establishes a proven lower bound on optimal SPSS size to quantify the approximation quality of the greedy algorithm.

Scientific Applications:

• UST-Compress: Uses the SPSS representation to losslessly compress k-mer sets, reducing disk space by roughly an order of magnitude compared to other lossless compression tools.
• UST-FM (Exact Static k-mer Membership Index): Constructs a static k-mer membership index that reduces index size by 10–44% compared to existing low-memory indices while supporting membership queries.

Methodology:

Transform the set of k-mers into an SPSS using a compacted de Bruijn graph framework, prove a lower bound on optimal SPSS size, and apply a greedy algorithm (UST) to approximate that bound.