A Linear Algorithm For Efficient Representation of k-mer Sets Using De Bruijn Graphs

A fundamental operation in computational genomics is the reduction of input sequences into their constituent k-mers. Developing space-efficient methods to represent a collection of k-mers is crucial for enhancing the scalability of bioinformatics analyses. A common strategy is to transform the set of k-mers into a de Bruijn graph and then create a streamlined representation by identifying the smallest path cover. In this article, we introduce USTAR2, a novel algorithm for compressing k-mers. USTAR2 leverages node connectivity principles in the de Bruijn graph for more efficient path selection in constructing the path cover. We tested USTAR2 on real read datasets and compared it with several other tools. USTAR2 demonstrated superior performance in terms of compression, requiring less memory and being significantly faster (up to 96x). The code of USTAR2 is available at the repository https://github.com/CominLab/USTAR2.