title: A scalable assembly-free variable selection algorithm for biomarker discovery from metagenomes.
abstract: BACKGROUND
  Metagenomics holds great promises for deepening our knowledge of key bacterial driven processes, but metagenome assembly remains problematic, typically resulting in representation biases and discarding significant amounts of non-redundant sequence information. In order to alleviate constraints assembly can impose on downstream analyses, and/or to increase the fraction of raw reads assembled via targeted assemblies relying on pre-assembly binning steps, we developed a set of binning modules and evaluated their combination in a new "assembly-free" binning protocol.
  
  
  RESULTS
  We describe a scalable multi-tiered binning algorithm that combines frequency and compositional features to cluster unassembled reads, and demonstrate i) significant runtime performance gains of the developed modules against state of the art software, obtained through parallelization and the efficient use of large lock-free concurrent hash maps, ii) its relevance for clustering unassembled reads from high complexity (e.g., harboring 700 distinct genomes) samples, iii) its relevance to experimental setups involving multiple samples, through a use case consisting in the "de novo" identification of sequences from a target genome (e.g., a pathogenic strain) segregating at low levels in a cohort of 50 complex microbiomes (harboring 100 distinct genomes each), in the background of closely related strains and the absence of reference genomes, iv) its ability to correctly identify clusters of sequences from the E. coli O104:H4 genome as the most strongly correlated to the infection status in 53 microbiomes sampled from the 2011 STEC outbreak in Germany, and to accurately cluster contigs of this pathogenic strain from a cross-assembly of these 53 microbiomes.
  
  
  CONCLUSIONS
  We present a set of sequence clustering ("binning") modules and their application to biomarker (e.g., genomes of pathogenic organisms) discovery from large synthetic and real metagenomics datasets. Initially designed for the "assembly-free" analysis of individual metagenomic samples, we demonstrate their extension to setups involving multiple samples via the usage of the "alignment-free" d2S statistic to relate clusters across samples, and illustrate how the clustering modules can otherwise be leveraged for de novo "pre-assembly" tasks by segregating sequences into biologically meaningful partitions.
authors.affiliation: Commissariat à l'Energie Atomique et aux Energies Alternatives, Direction de la Recherche Fondamentale, Institut de Génomique, Genoscope, Evry, Essonne, 91057, France.|UMR 8030 - Génomique Métabolique, Centre National de la Recherche Scientifique, Evry, Essonne, 91057, France.|Université d'Evry-Val-d'Essonne & Université Paris-Saclay, Evry, Essonne, 91000, France.
authors.forename: Anestis
authors.initials: A
authors.lastname: Gkanogiannis
authors.affiliation: Commissariat à l'Energie Atomique et aux Energies Alternatives, Direction de la Recherche Technologique, CEA-Tech, LIST, Laboratoire d'Analyse de Données et Intelligence des Systèmes, 91191, Gif-sur-Yvette, France.
authors.forename: Stéphane
authors.initials: S
authors.lastname: Gazut
authors.affiliation: Commissariat à l'Energie Atomique et aux Energies Alternatives, Direction de la Recherche Fondamentale, Institut de Génomique, Genoscope, Evry, Essonne, 91057, France.|UMR 8030 - Génomique Métabolique, Centre National de la Recherche Scientifique, Evry, Essonne, 91057, France.|Université d'Evry-Val-d'Essonne & Université Paris-Saclay, Evry, Essonne, 91000, France.
authors.forename: Marcel
authors.initials: M
authors.lastname: Salanoubat
authors.affiliation: Commissariat à l'Energie Atomique et aux Energies Alternatives, Direction de la Recherche Technologique, CEA-Tech, LIST, Laboratoire d'Analyse de Données et Intelligence des Systèmes, 91191, Gif-sur-Yvette, France.
authors.forename: Sawsan
authors.initials: S
authors.lastname: Kanj
authors.affiliation: Commissariat à l'Energie Atomique et aux Energies Alternatives, Direction de la Recherche Fondamentale, Institut de Génomique, Genoscope, Evry, Essonne, 91057, France. bruls@genoscope.cns.fr.|UMR 8030 - Génomique Métabolique, Centre National de la Recherche Scientifique, Evry, Essonne, 91057, France. bruls@genoscope.cns.fr.|Université d'Evry-Val-d'Essonne & Université Paris-Saclay, Evry, Essonne, 91000, France. bruls@genoscope.cns.fr.
authors.forename: Thomas
authors.initials: T
authors.lastname: Brüls
mesh_terms: D000465:Algorithms; D015415:Biomarkers / Q000737:chemistry*; D066264:Datasets as Topic; D006801:Humans; D054892:Metagenome; D056186:Metagenomics; D064307:Microbiota / Q000235:genetics*
chemical_list: D015415:Biomarkers
keywords: Binning; Environmental genomics; Metagenomics; Microbiome; Sequence clustering; Unsupervised learning