A near-tight lower bound on the density of forward sampling schemes
Bioinformatics · 26.12.2024 · 41 (1)
DOI: 10.1093/bioinformatics/btae736 ↗Kurz gefasst
Fachartikel in der Zeitschrift Bioinformatics, online erschienen am 12.12.2024. Verfasst von Bryce Kille und 4 weiteren Autor:innen. Beteiligte Einrichtung: Department of Computer Science, Rice University, Houston, TX 77005, United States. Hauptthemen laut MEDLINE: Algorithms. Die Arbeit wurde bisher 8-mal zitiert (Crossref) und nennt 32 Literaturangaben. Der Volltext ist frei zugänglich (Open Access, CC BY 4.0). Gefördert von: NIAID NIH HHS, National Institute of Allergy and Infectious Diseases, National Library of Medicine Training Program in Biomed-ical Informatics and Data Science.
Abstract (Originalsprache)
Motivation Sampling k-mers is a ubiquitous task in sequence analysis algorithms. Sampling schemes such as the often-used random minimizer scheme are particularly appealing as they guarantee at least one k-mer is selected out of every w consecutive k-mers. Sampling fewer k-mers often leads to an increase in efficiency of downstream methods. Thus, developing schemes that have low density, i.e. have a small proportion of sampled k-mers, is an active area of research. After over a decade of consistent efforts in both decreasing the density of practical schemes and increasing the lower bound on the best possible density, there is still a large gap between the two. Results We prove a near-tight lower bound on the density of forward sampling schemes, a class of schemes that generalizes minimizer schemes. For small w and k, we observe that our bound is tight when k≡1(mod w). For large w and k, the bound can be approximated by 1w+k⌈w+kw⌉. Importantly, our lower bound implies that existing schemes are much closer to achieving optimal density than previously known. For example, with the current default minimap2 HiFi settings w = 19 and k = 19, we show that the best known scheme for these parameters, the double decycling-set-based minimizer of Pellow et al. is at most 3% denser than optimal, compared to the previous gap of at most 50%. Furthermore, when k≡1(mod w) and the alphabet size σ goes to ∞, we show that mod-minimizers introduced by Groot Koerkamp and Pibiri achieve optimal density matching our lower bound. Availability and implementation Minimizer implementations: github.com/RagnarGrootKoerkamp/minimizers ILP and analysis: github.com/treangenlab/sampling-scheme-analysis.
Schlagwörter
MeSH-Schlagwörter (MEDLINE)
Autor:innen und Institutionen
- Department of Computer Science, Rice University, Houston, TX 77005, United States.
- Department of Computer Science, ETH Zurich, Zurich 8092, Switzerland.
- Ken Kennedy Institute, Rice University, Houston, TX 77005, United States.
ORCID-Profile: Bryce Kille, Ragnar Groot Koerkamp
Förderung
- NIAID NIH HHS
- National Institute of Allergy and Infectious Diseases
- National Library of Medicine Training Program in Biomed-ical Informatics and Data Science
- National Science Foundation
- NLM NIH HHS
Zitieren
APA
Kille, B., Groot Koerkamp, R., McAdams, D., Liu, A., & Treangen, T. J. (2024). A near-tight lower bound on the density of forward sampling schemes. Bioinformatics, 41(1). https://doi.org/10.1093/bioinformatics/btae736
Vancouver
Kille B, Groot Koerkamp R, McAdams D, Liu A, Treangen TJ. A near-tight lower bound on the density of forward sampling schemes. Bioinformatics. 2024;41(1). doi:10.1093/bioinformatics/btae736
BibTeX
@article{Kille2024,
author = {Kille, Bryce and Groot Koerkamp, Ragnar and McAdams, Drake and Liu, Alan and Treangen, Todd J},
title = {A near-tight lower bound on the density of forward sampling schemes},
journal = {Bioinformatics},
year = {2024},
volume = {41},
number = {1},
doi = {10.1093/bioinformatics/btae736}
}
EUVIMED