GSearch: ultra-fast and scalable genome search by combining K-mer hashing with hierarchical navigable small world graphs.

ABSTRACT: Genome search and/or classification typically involves finding the best-match database (reference) genomes and has become increasingly challenging due to the growing number of available database genomes and the fact that traditional methods do not scale well with large databases. By combining k-mer hashing-based probabilistic data structures (i.e. ProbMinHash, SuperMinHash, Densified MinHash and SetSketch) to estimate genomic distance, with a graph based nearest neighbor search algorithm (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 search 8000 query genomes aga

SUBMITTER: Zhao J 

PROVIDER: S-EPMC11381346 | biostudies-literature | 2024 Sep

REPOSITORIES: biostudies-literature