EUVIMEDEUVIMED entdecken
Open Access · CC BY 4.0

GreedyMini: generating low-density DNA minimizers

Shay Golan iD, Ido Tziony iD, Matan Kraus iD, Yaron Orenstein iD, Arseny Shur

Bioinformatics · 01.07.2025 · 41 (Supplement_1) · i275-i284

DOI: 10.1093/bioinformatics/btaf251 ↗

Kurz gefasst

Fachartikel in der Zeitschrift Bioinformatics, online erschienen am 15.07.2025. Verfasst von Shay Golan und 4 weiteren Autor:innen. Beteiligte Einrichtung: Department of Computer Science, University of Haifa, Haifa 3498838, Israel. Hauptthemen laut MEDLINE: Algorithms, High-Throughput Nucleotide Sequencing, Sequence Analysis, DNA, DNA. Die Arbeit wurde bisher 11-mal zitiert (Crossref) und nennt 32 Literaturangaben. Der Volltext ist frei zugänglich (Open Access, CC BY 4.0). Gefördert von: Israel Science Foundation, Israel Data Science and AI Initiative, ERC.

AbstractSchlagwörterBibliografische AngabenZitierenVerwandte Studien

Abstract (Originalsprache)

Motivation Minimizers are the most popular k-mer selection scheme in algorithms and data structures analyzing high-throughput sequencing (HTS) data. In a minimizer scheme, the smallest k-mer by some predefined order is selected as the representative of a sequence window containing w consecutive k-mers, which results in overlapping windows often selecting the same k-mer. Minimizers that achieve the lowest frequency of selected k-mers over a random DNA sequence, termed the expected density, are desired for improved performance of HTS analyses. Yet, no method to date exists to generate minimizers that achieve minimum expected density. Moreover, for k and w values used by common HTS algorithms and data structures, there is a gap between densities achieved by existing selection schemes and the theoretical lower bound. Results We developed GreedyMini, a toolkit of methods to generate minimizers with low expected or particular density, to improve minimizers, to extend minimizers to larger alphabets, k, and w, and to measure the expected density of a given minimizer efficiently. We demonstrate over various combinations of k and w values, including those of popular HTS methods, that GreedyMini can generate DNA minimizers that achieve expected densities very close to the lower bound, and both expected and particular densities much lower compared to existing selection schemes. Moreover, we show that GreedyMini’s k-mer rank-retrieval time is comparable to common k-mer hash functions. We expect GreedyMini to improve the performance of many HTS algorithms and data structures and advance the research of k-mer selection schemes. Availability and implementation The toolkit, its source code, and precomputed minimizers for a variety of (k,w) pairs are available via https://github.com/OrensteinLab/GreedyMini.

Schlagwörter

MeSH-Schlagwörter (MEDLINE)

AlgorithmsHigh-Throughput Nucleotide SequencingSequence Analysis, DNADNASoftware

Substanzen

DNA

Autor:innen und Institutionen

  • Department of Computer Science, University of Haifa, Haifa 3498838, Israel.
  • Efi Arazi School of Computer Science, Reichman University, Herzliya 4610101, Israel.
  • Department of Computer Science, Bar-Ilan University, Ramat Gan 5290002, Israel.
  • The Mina and Everard Goodman Faculty of Life Sciences, Bar-Ilan University, Ramat Gan 5290002, Israel.

ORCID-Profile: Shay Golan, Ido Tziony, Matan Kraus, Yaron Orenstein

Förderung

  • Israel Science Foundation
  • Israel Data Science and AI Initiative
  • ERC
  • EU's Horizon 2020 Research and Innovation Programme
  • Center for Absorption in Science of the Ministry of Aliyah and Immigration
  • United States-Israel Binational Science Foundation
  • EU’s Horizon 2020 Research and Innovation Programme
  • United States–Israel Binational Science Foundation

Zitieren

APA

Golan, S., Tziony, I., Kraus, M., Orenstein, Y., & Shur, A. (2025). GreedyMini: generating low-density DNA minimizers. Bioinformatics, 41(Supplement_1), i275-i284. https://doi.org/10.1093/bioinformatics/btaf251

Vancouver

Golan S, Tziony I, Kraus M, Orenstein Y, Shur A. GreedyMini: generating low-density DNA minimizers. Bioinformatics. 2025;41(Supplement_1):i275-i284. doi:10.1093/bioinformatics/btaf251

BibTeX
@article{Golan2025,
  author = {Golan, Shay and Tziony, Ido and Kraus, Matan and Orenstein, Yaron and Shur, Arseny},
  title = {GreedyMini: generating low-density DNA minimizers},
  journal = {Bioinformatics},
  year = {2025},
  volume = {41},
  number = {Supplement_1},
  pages = {i275--i284},
  doi = {10.1093/bioinformatics/btaf251}
}
Kostenlos starten →