GEMINI: a computationally-efficient search engine for large gene expression datasets. Issue 1 (December 2016)

• Record Type: Journal Article
• Authors: DeFreitas, Timothy; Saddiki, Hachem; Flaherty, Patrick
• Is Part Of: BMC bioinformatics. Volume 17:Issue 1(2016)
• Page Start: 1
• Page End: 7
• Publication Date: 2016-12
• Subjects: Genomic search -- Vantage-point tree -- Cancer Genome Atlas; Bioinformatics -- Periodicals; Computational biology -- Periodicals; 570.285
• DOI: 10.1186/s12859-016-0934-8
• Languages: English
• ISSNs: 1471-2105

Abstract

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 ofn profiles and in certain circumstances achieves an O ( log n ) $\mathcal {O}(\log n)$ 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 105 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.