title: The Amordad database engine for metagenomics.
abstract: BACKGROUND
  Several technical challenges in metagenomic data analysis, including assembling metagenomic sequence data or identifying operational taxonomic units, are both significant and well known. These forms of analysis are increasingly cited as conceptually flawed, given the extreme variation within traditionally defined species and rampant horizontal gene transfer. Furthermore, computational requirements of such analysis have hindered content-based organization of metagenomic data at large scale.
  
  
  RESULTS
  In this article, we introduce the Amordad database engine for alignment-free, content-based indexing of metagenomic datasets. Amordad places the metagenome comparison problem in a geometric context, and uses an indexing strategy that combines random hashing with a regular nearest neighbor graph. This framework allows refinement of the database over time by continual application of random hash functions, with the effect of each hash function encoded in the nearest neighbor graph. This eliminates the need to explicitly maintain the hash functions in order for query efficiency to benefit from the accumulated randomness. Results on real and simulated data show that Amordad can support logarithmic query time for identifying similar metagenomes even as the database size reaches into the millions.
  
  
  METHODS
  Source code, licensed under the GNU general public license (version 3) is freely available for download from http://smithlabresearch.org/amordad
  
  
  BACKGROUND
  andrewds@usc.edu
  
  
  BACKGROUND
  Supplementary data are available at Bioinformatics online.
authors: Molecular and Computational Biology, Department of Biological Sciences, University of Southern California, Los Angeles, CA, USA.
authors: Ehsan
authors: E
authors: Behnam
authors: Molecular and Computational Biology, Department of Biological Sciences, University of Southern California, Los Angeles, CA, USA.
authors: Andrew D
authors: AD
authors: Smith
mesh_terms: D030541:Databases, Genetic; D016247:Information Storage and Retrieval / Q000379:methods*; D056186:Metagenomics / Q000379:methods*; D012984:Software