Fractional hitting sets for efficient multiset sketching
Abstract The exponential increase in publicly available sequencing data and genomic resources necessitates the development of highly efficient methods for data processing and analysis. Locality-sensitive hashing techniques have successfully transformed large datasets into smaller, more manageable sk...
Saved in:
| Main Authors: | , , , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
BMC
2025-02-01
|
| Series: | Algorithms for Molecular Biology |
| Subjects: | |
| Online Access: | https://doi.org/10.1186/s13015-024-00268-0 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1823863268038410240 |
|---|---|
| author | Timothé Rouzé Igor Martayan Camille Marchet Antoine Limasset |
| author_facet | Timothé Rouzé Igor Martayan Camille Marchet Antoine Limasset |
| author_sort | Timothé Rouzé |
| collection | DOAJ |
| description | Abstract The exponential increase in publicly available sequencing data and genomic resources necessitates the development of highly efficient methods for data processing and analysis. Locality-sensitive hashing techniques have successfully transformed large datasets into smaller, more manageable sketches while maintaining comparability using metrics such as Jaccard and containment indices. However, fixed-size sketches encounter difficulties when applied to divergent datasets. Scalable sketching methods, such as sourmash, provide valuable solutions but still lack resource-efficient, tailored indexing. Our objective is to create lighter sketches with comparable results while enhancing efficiency. We introduce the concept of Fractional Hitting Sets, a generalization of Universal Hitting Sets, which cover a specified fraction of the k-mer space. In theory and practice, we demonstrate the feasibility of achieving such coverage with simple but highly efficient schemes. By encoding the covered k-mers as super-k-mers, we provide a space-efficient exact representation that also enables optimized comparisons. Our novel tool, supersampler, implements this scheme, and experimental results with real bacterial collections closely match our theoretical findings. In comparison to sourmash, supersampler achieves similar outcomes while utilizing an order of magnitude less space and memory and operating several times faster. This highlights the potential of our approach in addressing the challenges presented by the ever-expanding landscape of genomic data. supersampler is an open-source software and can be accessed at https://github.com/TimRouze/supersampler . The data required to reproduce the results presented in this manuscript is available at https://github.com/TimRouze/supersampler/experiments . |
| format | Article |
| id | doaj-art-4dc648b018e94260b2f4d59e5dab1ae0 |
| institution | Kabale University |
| issn | 1748-7188 |
| language | English |
| publishDate | 2025-02-01 |
| publisher | BMC |
| record_format | Article |
| series | Algorithms for Molecular Biology |
| spelling | doaj-art-4dc648b018e94260b2f4d59e5dab1ae02025-02-09T12:12:24ZengBMCAlgorithms for Molecular Biology1748-71882025-02-0120112510.1186/s13015-024-00268-0Fractional hitting sets for efficient multiset sketchingTimothé Rouzé0Igor Martayan1Camille Marchet2Antoine Limasset3G5 - SeqBio, Institut pasteur, Université Paris CitéUMR9189 CRIStAL, Univ Lille, CNRS, CentraleUMR9189 CRIStAL, Univ Lille, CNRS, CentraleUMR9189 CRIStAL, Univ Lille, CNRS, CentraleAbstract The exponential increase in publicly available sequencing data and genomic resources necessitates the development of highly efficient methods for data processing and analysis. Locality-sensitive hashing techniques have successfully transformed large datasets into smaller, more manageable sketches while maintaining comparability using metrics such as Jaccard and containment indices. However, fixed-size sketches encounter difficulties when applied to divergent datasets. Scalable sketching methods, such as sourmash, provide valuable solutions but still lack resource-efficient, tailored indexing. Our objective is to create lighter sketches with comparable results while enhancing efficiency. We introduce the concept of Fractional Hitting Sets, a generalization of Universal Hitting Sets, which cover a specified fraction of the k-mer space. In theory and practice, we demonstrate the feasibility of achieving such coverage with simple but highly efficient schemes. By encoding the covered k-mers as super-k-mers, we provide a space-efficient exact representation that also enables optimized comparisons. Our novel tool, supersampler, implements this scheme, and experimental results with real bacterial collections closely match our theoretical findings. In comparison to sourmash, supersampler achieves similar outcomes while utilizing an order of magnitude less space and memory and operating several times faster. This highlights the potential of our approach in addressing the challenges presented by the ever-expanding landscape of genomic data. supersampler is an open-source software and can be accessed at https://github.com/TimRouze/supersampler . The data required to reproduce the results presented in this manuscript is available at https://github.com/TimRouze/supersampler/experiments .https://doi.org/10.1186/s13015-024-00268-0k-merSubsamplingSketchingJaccardContainmentMetagenomics |
| spellingShingle | Timothé Rouzé Igor Martayan Camille Marchet Antoine Limasset Fractional hitting sets for efficient multiset sketching Algorithms for Molecular Biology k-mer Subsampling Sketching Jaccard Containment Metagenomics |
| title | Fractional hitting sets for efficient multiset sketching |
| title_full | Fractional hitting sets for efficient multiset sketching |
| title_fullStr | Fractional hitting sets for efficient multiset sketching |
| title_full_unstemmed | Fractional hitting sets for efficient multiset sketching |
| title_short | Fractional hitting sets for efficient multiset sketching |
| title_sort | fractional hitting sets for efficient multiset sketching |
| topic | k-mer Subsampling Sketching Jaccard Containment Metagenomics |
| url | https://doi.org/10.1186/s13015-024-00268-0 |
| work_keys_str_mv | AT timotherouze fractionalhittingsetsforefficientmultisetsketching AT igormartayan fractionalhittingsetsforefficientmultisetsketching AT camillemarchet fractionalhittingsetsforefficientmultisetsketching AT antoinelimasset fractionalhittingsetsforefficientmultisetsketching |