Abstract Motivation Comparing large number of genomes in term of their genomic distance is becoming more and more challenging because there is an increasing number of microbial genomes deposited in public databases. Nowadays, we may need to estimate pairwise distances between millions or even billions of genomes. Few softwares can perform such comparisons efficiently. Results Here we update the multi-threaded software BinDash by implementing several new MinHash algorithms and computational optimization (e.g. Simple Instruction Multiple Data, SIMD) for ultra-fast and accurate genome search and comparisons at trillion scale. That is, we implemented b-bit one-permutation rolling MinHash with optimal/faster densification with SIMD. Now with BinDash 2, we can perform 0.1 trillion (or ∼10^11) pairs of genome comparisons in about 1.8 hours on a descent computer cluster or several hours on personal laptops, a ∼50% or more improvement over original version. The ANI (average nucleotide identity) estimated by BinDash is well correlated with other accurate but much slower ANI estimators such as FastANI or alignment-based ANI. In line with the findings from comparing 90K genomes (∼10^9 comparisons) via FastANI, the 85% ∼ 95% ANI gap is consistent in our study of ∼10^11 prokaryotic genome comparisons via BinDash2, which indicates fundamental ecological and evolutionary forces keeping species-like unit (e.g., > 95% ANI) together. Availability and implementation BinDash is released under the Apache 2.0 license at: https://github.com/zhaoxiaofei/bindash Contact kostas.konstantinidis@gatech.edu Supplementary information Supplementary data are available at Bioinformatics online.

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

Abstract Dimension reduction (or embedding), as a popular way to visualize data, has been a fundamental technique in many applications. Non-linear dimension reduction such as t-SNE and UMAP has been widely used in visualizing single cell RNA sequencing data and metagenomic binning and thus receive many attentions in bioinformatics and computational biology. Here in this paper, we further improve UMAP-like non-linear dimension reduction algorithms by updating the graph- based nearest neighbor search algorithm (e.g. we use Hierarchical Navigable Small World Graph, or HNSW instead of K-graph) and combine several aspects of t-SNE and UMAP to create a new non-linear dimension reduction algorithm. We also provide several additional features including computation of LID (Local Intrinsic Dimension) and hubness, which can reflect structures and properties of the underlying data that strongly affect nearest neighbor search algorithm in traditional UMAP-like algorithms and thus the quality of embeddings. We also combined the improved non-linear dimension reduction algorithm with probabilistic data structures such as MinHash-likes ones (e.g., ProbMinHash et.al.) for large-scale biological sequence data visualization. Our library is called annembed and it was implemented and fully parallelized in Rust. We benchmark it against popular tools mentioned above using standard testing datasets and it showed competitive accuracy. Additionally, we apply our library in three real-world problems: visualizing large-scale microbial genomic database, visualizing single cell RNA sequencing data and metagenomic binning, to showcase the performance, scalability and efficiency of the library when distance computation is expensive or when the number of data points is large (e.g. millions or billions). Annembed can be found here: https://github.com/jean-pierreBoth/annembed

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 against all available microbial or viral genomes for their best matches (n = ∼318 000 or ∼3 000 000, respectively) within a few minutes on a personal laptop, using ∼6 GB of memory (2.5 GB via SetSketch). Notably, GSearch has an O(log(N)) time complexity and will scale well with billions of genomes based on a database splitting strategy. Further, GSearch implements a three-step search strategy depending on the degree of novelty of the query genomes to maximize specificity and sensitivity. Therefore, GSearch solves a major bottleneck of microbiome studies that require genome search and/or classification.