Accès ouvert · CC BY

A framework for space-efficient read clustering in metagenomic samples

Article scientifique 2017 Sciences mathématiques et statistiques Anglais

Résumé

BACKGROUND: A metagenomic sample is a set of DNA fragments, randomly extracted from multiple cells in an environment, belonging to distinct, often unknown species. Unsupervised metagenomic clustering aims at partitioning a metagenomic sample into sets that approximate taxonomic units, without using reference genomes. Since samples are large and steadily growing, space-efficient clustering algorithms are strongly needed. RESULTS: We design and implement a space-efficient algorithmic framework that solves a number of core primitives in unsupervised metagenomic clustering using just the bidirectional Burrows-Wheeler index and a union-find data structure on the set of reads. When run on a sample of total length n, with m reads of maximum length ℓ each, on an alphabet of total size σ, our algorithms take O(n(t+logσ)) time and just 2n+o(n)+O(max{ℓ σlogn,K logm}) bits of space in addition to the index and to the union-find data structure, where K is a measure of the redundancy of the sample and t is the query time of the union-find data structure. CONCLUSIONS: Our experimental results show that our algorithms are practical, they can exploit multiple cores by a parallel traversal of the suffix-link tree, and they are competitive both in space and in time with the state of the art.

Citer ce document

Alanko, J., Cunial, F., Belazzougui, D., & Mäkinen, V. (2017). A framework for space-efficient read clustering in metagenomic samples. BMC Bioinformatics. https://doi.org/10.1186/s12859-017-1466-6

Exporter : BibTeX · RIS (Zotero, Mendeley, EndNote)

Accès au document

Texte intégral archivé sur SPHAERO, en accès ouvert : lisible gratuitement en ligne après connexion. Le document reste aussi disponible à sa source. Se connecter

Voir l'article sur le site de la revue

Licence et provenance

Licence : CC BY

Notice moissonnée depuis OpenAlex le 27/08/2026. Le document reste hébergé par sa source.
Voir le document à la source →

Statistiques

Consultations (hors robots) : 11

Téléchargements (hors robots) : 0

Méthode de comptage