title: GEMINI: a computationally-efficient search engine for large gene expression datasets.
abstract: BACKGROUND
  Low-cost DNA sequencing allows organizations to accumulate massive amounts of genomic data and use that data to answer a diverse range of research questions. Presently, users must search for relevant genomic data using a keyword, accession number of meta-data tag. However, in this search paradigm the form of the query - a text-based string - is mismatched with the form of the target - a genomic profile.
  
  
  RESULTS
  To improve access to massive genomic data resources, we have developed a fast search engine, GEMINI, that uses a genomic profile as a query to search for similar genomic profiles. GEMINI implements a nearest-neighbor search algorithm using a vantage-point tree to store a database of n profiles and in certain circumstances achieves an [Formula: see text] expected query time in the limit. We tested GEMINI on breast and ovarian cancer gene expression data from The Cancer Genome Atlas project and show that it achieves a query time that scales as the logarithm of the number of records in practice on genomic data. In a database with 10(5) samples, GEMINI identifies the nearest neighbor in 0.05 sec compared to a brute force search time of 0.6 sec.
  
  
  CONCLUSIONS
  GEMINI is a fast search engine that uses a query genomic profile to search for similar profiles in a very large genomic database. It enables users to identify similar profiles independent of sample label, data origin or other meta-data information.
authors.affiliation: Computer Science Department, Worcester Polytechnic Institute, 100 Institute Rd, Worcester, 01609, USA. tmdefreitas@wpi.edu.|Program in Bioinformatics and Computational Biology, 100 Institute Rd, Worcester, 01609, USA. tmdefreitas@wpi.edu.
authors.forename: Timothy
authors.initials: T
authors.lastname: DeFreitas
authors.affiliation: Department of Mathematics and Statistics, University of Massachusetts, Amherst, 710 N. Pleasant St, Amherst, 01003, USA. hsaddiki@umass.edu.
authors.forename: Hachem
authors.initials: H
authors.lastname: Saddiki
authors.affiliation: Program in Bioinformatics and Computational Biology, 100 Institute Rd, Worcester, 01609, USA. flaherty@math.umass.edu.|Biomedical Engineering Department, Worcester Polytechnic Institute, 100 Institute Rd, Worcester, 01609, USA. flaherty@math.umass.edu.|Department of Mathematics and Statistics, University of Massachusetts, Amherst, 710 N. Pleasant St, Amherst, 01003, USA. flaherty@math.umass.edu.
authors.forename: Patrick
authors.initials: P
authors.lastname: Flaherty
mesh_terms: D016000:Cluster Analysis; D016208:Databases, Factual; D015870:Gene Expression / Q000235:genetics*; D023281:Genomics; D006801:Humans; D057386:Search Engine / Q000706:statistics & numerical data*; D017422:Sequence Analysis, DNA / Q000379:methods*