title: A framework for space-efficient read clustering in metagenomic samples.
abstract: 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.
authors.affiliation: Department of Computer Science, University of Helsinki, Gustaf Hällströmin katu 2b, Helsinki, 00560, Finland. jarno.alanko@cs.helsinki.fi.
authors.forename: Jarno
authors.initials: J
authors.lastname: Alanko
authors.affiliation: Max Planck Institute for Molecular Cell Biology and Genetics, Pfotenhauerstr. 108, Dresden, 01307, Germany.
authors.forename: Fabio
authors.initials: F
authors.lastname: Cunial
authors.affiliation: DTISI, CERIST (Research Centre for Scientific and Technical Information), Rue des 3 Fréres Aissou, Algiers, 16306, Algeria.
authors.forename: Djamal
authors.initials: D
authors.lastname: Belazzougui
authors.affiliation: Department of Computer Science, University of Helsinki, Gustaf Hällströmin katu 2b, Helsinki, 00560, Finland.
authors.forename: Veli
authors.initials: V
authors.lastname: Mäkinen
mesh_terms: D000465:Algorithms; D016000:Cluster Analysis; D019295:Computational Biology / Q000379:methods*; D053938:DNA Fragmentation; D056186:Metagenomics; D008962:Models, Theoretical; D017422:Sequence Analysis, DNA
keywords: Burrows-Wheeler transform; Metagenomics; Read clustering; Right-maximal k-mer; Submaximal repeat; Suffix-link tree; Text indexing