Bacterial genome databases collectively approach ten million assembled genomes, yet redundancy and limited scalability of existing tools create bottlenecks for comprehensive, tree-of-life-scale genomic analyses. One widely used approach involves dereplication to remove redundancy, but methods struggle beyond a few thousand genomes, making global organisation of public genomes computationally infeasible.
Here we present gemsparcl, a tool that clusters bacterial genomes into genomically coherent units (GCUs), orders of magnitude faster than existing methods. Central to gemsparcl is sketchlib.rust, a highly efficient one-permutation MinHash implementation with an auxiliary inverted index that substantially accelerates all-versus-all genome comparisons. gemsparcl further applies statistical correction for incomplete metagenome-assembled genomes (MAGs) and uses network-based quality filtering to remove edges weakly connecting distinct GCUs.
We clustered 5.6 million high-quality bacterial genomes (2.88 million isolates and 2.77 million MAGs) into 92,954 GCUs in approximately 14 hours using 48 cores and less than 16.5 GB of memory, achieving 99.94% cluster purity. Delving into these results revealed 2,582 GCUs, each comprising more than 50 genomes, with clusters formed exclusively by MAGs, highlighting priorities for future isolation efforts. More detailed analysis of the GCU networks provides insights into genomic diversity, with work ongoing to routinely extract this information from the clusters.
The scalability of gemsparcl transforms what was previously intractable: routine and up-to-date organisation of all public bacterial genomes and large-scale biodiversity assessment.

Co-authors: John A. Lees, Robert D. Finn