Minimum Unique Substrings as a Context-Aware k-mer Alternative for Genomic Sequence Analysis

Fixed-length k-mers have long been the standard in sequence analysis. However, they impose a uniform resolution across heterogeneous genomes, often resulting in significant redundancy and a loss of contextual sensitivity. To address these limitations, we introduce Minimum Unique Substrings (MUSs), which are variable-length sequence units that adapt to the local complexity of the genome. MUSs function as context-aware markers that naturally define repeat boundaries by extending only until uniqueness is achieved. We build upon the theoretical relationship between MUSs and maximal repeats, extending this framework to sequencing reads by establishing a read-consistent definition of uniqueness. We present a linear-time ([O] (n)) algorithm based on a generalized suffix tree and introduce the concept of "outposts." These outposts act as anchors for uniqueness, enabling precise localization of MUS boundaries within the sequencing data. Empirical studies of E. coli K-12 and human HiFi reads reveal distinct distributions in MUS lengths that reflect their respective genomic architectures. The compact bacterial genome produces a highly dense set of MUSs with a narrow length distribution (averaging 30.44 bp). In contrast, the repeat-rich human genome requires longer substrings to resolve uniqueness, resulting in an increased mean length (36.08 bp) and a broader distribution that delineates complex repetitive elements. The MUS framework achieves 100% unique coverage with an average length of 36.08 bp, surpassing the 69% coverage of k = 61. By reducing the total number of tokens by over 99%, it provides higher resolution and superior data compression compared to fixed-length k-mer sampling. These results demonstrate that MUSs provide a biologically meaningful, context-sensitive alternative to k-mers, with direct applications in genome assembly, repeat characterization, and comparative genomics.