EUVIMEDEUVIMED entdecken
Open Access · CC BY 4.0

A near-tight lower bound on the density of forward sampling schemes

Bryce Kille iD, Ragnar Groot Koerkamp iD, Drake McAdams, Alan Liu, Todd J Treangen

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.

AbstractSchlagwörterBibliografische AngabenZitierenVerwandte Studien

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)

AlgorithmsComputational Biology

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}
}
Kostenlos starten →