GSearch: Ultra-Fast and Scalable Microbial Genome Search by combining Kmer Hashing with Hierarchical Navigable Small World Graphs

Abstract

Genome search and/or classification is a key step in microbiome studies and has recently become more challenging due to the increasing number of available (reference) genomes and the fact that traditional methods do not scale well with large databases. By combining k-mer hashing-based probabilistic data structures (e.g., (Prob/Super/Densified)-MinHash or SetSketch) to estimate genomic distance, with a graph-based nearest neighbor search algorithm (called Hierarchical Navigable Small World Graphs, or HNSW), we created a new data structure and developed an associated computer program, GSearch, that is orders of magnitude faster than alternative tools while maintaining high accuracy and low memory usage. For example, GSearch can identify/classify 8,000 query genomes against all available microbial or viral genomes (n=[~]318,000 or [~]3,000,000) within a few minutes on a personal laptop, using only [~]6GB of memory or less (e.g., 2.5G via SetSketch). Notably, GSearch will be even faster compared to other tools with even larger database size due to O(log(N)) time complexity and will scale well with billions of database genomes based on a database splitting strategy. Further, GSearch implements a three-step classification pipeline that accounts for the degree of novelty of query genomes relative to the database genome to maximize specificity and sensitivity. Therefore, GSearch solves a major bottleneck of microbiome studies that require genome search and/or classification of microbial or viral genomes. GSearch is available at: https://github.com/jean-pierreBoth/gsearch