2026-08-08T07:00:17Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:12805 2024-03-06T10:50:55Z ddc:004 open_access

Disk Compression of k-mer Sets Rahman, Amatur Chikhi, Rayan Medvedev, Paul de Bruijn graphs compression k-mer sets spectrum-preserving string sets K-mer based methods have become prevalent in many areas of bioinformatics. In applications such as database search, they often work with large multi-terabyte-sized datasets. Storing such large datasets is a detriment to tool developers, tool users, and reproducibility efforts. General purpose compressors like gzip, or those designed for read data, are sub-optimal because they do not take into account the specific redundancy pattern in k-mer sets. In our earlier work (Rahman and Medvedev, RECOMB 2020), we presented an algorithm UST-Compress that uses a spectrum-preserving string set representation to compress a set of k-mers to disk. In this paper, we present two improved methods for disk compression of k-mer sets, called ESS-Compress and ESS-Tip-Compress. They use a more relaxed notion of string set representation to further remove redundancy from the representation of UST-Compress. We explore their behavior both theoretically and on real data. We show that they improve the compression sizes achieved by UST-Compress by up to 27 percent, across a breadth of datasets. We also derive lower bounds on how well this type of compression strategy can hope to do. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Amatur Rahman and Rayan Chikhi and Paul Medvedev 2020 Is Part Of LIPIcs, Volume 172, 20th International Workshop on Algorithms in Bioinformatics (WABI 2020) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.WABI.2020.16 urn:nbn:de:0030-drops-128057 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.WABI.2020.16 eng https://creativecommons.org/licenses/by/3.0/legalcode