EUVIMEDEUVIMED entdecken
Open Access

Memory-bound k -mer selection for large and evolutionarily diverse reference libraries

Ali Osman Berk Şapcı iD, Siavash Mirarab iD

Genome Research · 2024

DOI: 10.1101/gr.279339.124 ↗

Kurz gefasst

Fachartikel in der Zeitschrift Genome Research, 2024. Verfasst von Ali Osman Berk Şapcı und 1 weiteren Autor:innen. Beteiligte Einrichtung: Bioinformatics and Systems Biology Graduate Program, University of California, San Diego, California 92093, USA. Hauptthemen laut MEDLINE: Algorithms. Die Arbeit wurde bisher 4-mal zitiert (Crossref) und nennt 25 Literaturangaben. Der Volltext ist frei in PubMed Central verfügbar. Gefördert von: NIGMS NIH HHS, National Institute of Health, Minderoo Foundation.

AbstractSchlagwörterBibliografische AngabenZitierenVerwandte Studien

Abstract (Originalsprache)

Using k -mers to find sequence matches is increasingly used in many bioinformatic applications, including metagenomic sequence classification. The accuracy of these downstream applications relies on the density of the reference databases, which are rapidly growing. Although the increased density provides hope for improvements in accuracy, scalability is a concern. Reference k -mers are kept in the memory during the query time, and saving all k -mers of these ever-expanding databases is fast becoming impractical. Several strategies for subsampling have been proposed, including minimizers and finding taxon-specific k -mers. However, we contend that these strategies are inadequate, especially when reference sets are taxonomically imbalanced, as are most microbial libraries. In this paper, we explore approaches for selecting a fixed-size subset of k -mers present in an ultra-large data set to include in a library such that the classification of reads suffers the least. Our experiments demonstrate the limitations of existing approaches, especially for novel and poorly sampled groups. We propose a library construction algorithm called k -mer RANKer (KRANK) that combines several components, including a hierarchical selection strategy with adaptive size restrictions and an equitable coverage strategy. We implement KRANK in highly optimized code and combine it with the locality-sensitive hashing classifier CONSULT-II to build a taxonomic classification and profiling method. On several benchmarks, KRANK k -mer selection significantly reduces memory consumption with minimal loss in classification accuracy. We show in extensive analyses based on CAMI benchmarks that KRANK outperforms k -mer-based alternatives in terms of taxonomic profiling and comes close to the best marker-based methods in terms of accuracy.

Schlagwörter

MeSH-Schlagwörter (MEDLINE)

AlgorithmsMetagenomicsHumansGene LibrarySoftwareComputational BiologySequence Analysis, DNADatabases, GeneticMetagenome

Autor:innen und Institutionen

  • Bioinformatics and Systems Biology Graduate Program, University of California, San Diego, California 92093, USA.
  • Bioinformatics and Systems Biology Graduate Program, University of California, San Diego, California 92093, USA; smirarab@ucsd.edu.
  • Department of Electrical and Computer Engineering, University of California, San Diego, California 92093, USA.

ORCID-Profile: Ali Osman Berk Şapcı, Siavash Mirarab

Förderung

  • NIGMS NIH HHS
  • National Institute of Health
  • Minderoo Foundation

Zitieren

APA

Şapcı, A. O. B., & Mirarab, S. (2024). Memory-bound k -mer selection for large and evolutionarily diverse reference libraries. Genome Research. https://doi.org/10.1101/gr.279339.124

Vancouver

Şapcı AOB, Mirarab S. Memory-bound k -mer selection for large and evolutionarily diverse reference libraries. Genome Research. 2024. doi:10.1101/gr.279339.124

BibTeX
@article{apc2024,
  author = {Şapcı, Ali Osman Berk and Mirarab, Siavash},
  title = {Memory-bound k -mer selection for large and evolutionarily diverse reference libraries},
  journal = {Genome Research},
  year = {2024},
  doi = {10.1101/gr.279339.124}
}
Kostenlos starten →