A randomized parallel algorithm for efficiently finding near-optimal universal hitting sets

DOI10.1007/978-3-030-45257-5_3MaRDI QIDQ5041795zbMATH OpenOpenAlexFDO

Authors Barış Ekim, Bonnie Berger, Yaron Orenstein

Publication date 14 October 2022

Published in Lecture Notes in Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/978-3-030-45257-5_3

zbMATH Keywords

parallelizationrandomizationuniversal hitting sets

Mathematics Subject Classification ID

Parallel algorithms in computer science (68W10) Randomized algorithms (68W20) Protein sequences, DNA sequences (92D20)

Recommendations

• Lower density selection schemes via small universal hitting sets with short remaining path length
• Fast spaced seed hashing
• Compression of Multiple k-Mer Sets by Iterative SPSS Decomposition
• Effective parallel multicore-optimized k-mers counting algorithm
• The minimal hitting set generation problem: algorithms and computation

Cites work

• A proof of Golomb's conjecture for the de Bruijn graph
• Approximation algorithms for combinatorial problems
• Minimizing the number of bootstrappings in fully homomorphic encryption
• On the ratio of optimal integral and fractional covers

Cited in

(4)

• DeepMinimizer: a differentiable framework for optimizing sequence-specific minimizer schemes
• Lower density selection schemes via small universal hitting sets with short remaining path length
• Fractional hitting sets for efficient and lightweight genomic data sketching
• The mod-minimizer: a simple and efficient sampling algorithm for long k-mers

Describes a project that uses

Uses Software

• KMC

This page was built for publication: A randomized parallel algorithm for efficiently finding near-optimal universal hitting sets

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5041795)