Nature Biotechnology
(2026) Cite this article
Accurately characterizing metagenome-assembled genomes remains a substantial challenge due to the presence of sequencing errors, incomplete assembly and contamination. Here, we present MetaSBT, a tool for organizing, indexing and characterizing microbial reference genomes and metagenome-assembled genomes, demonstrated in this study using viruses. MetaSBT identifies clusters of genomes across all seven taxonomic levels using the Sequence Bloom Tree data structure, which relies on Bloom filters to index large amounts of genomes based on their k-mer composition. We built an initial set of databases composed of over 190,000 viral genomes from public sources, grouped into sequence-consistent clusters at different taxonomic levels. We defined over 40,000 candidate species, ~80% of which, to our knowledge, do not match viral species in reference databases to date. Furthermore, we showed that our databases are useful to existing quantitative metagenomic profilers to unlock the detection of unknown microbes and the estimation of their abundance in metagenomic samples. The open-source framework and databases are fully integrated into the Galaxy platform.
Microbial genomics and metagenomics1, the study of genetic material recovered directly from environmental samples, have revolutionized our understanding of microbial diversity and function, enabling us to identify and characterize microbial species and communities without the need for cultivation2, with profound implications for a wide variety of scientific fields, including medicine, agriculture, environmental science and biotechnology. However, harnessing the full potential of large metagenomic datasets presents major computational and analytical challenges. Accurately identifying and characterizing the myriad microbes within complex environmental samples requires robust bioinformatics tools capable of handling massive datasets, resolving complex relationships between species and accounting for the vast unknown diversity that still eludes our current understanding. Although gold-standard taxonomies exist for prokaryotes (for example, GTDB3 and MGnify4) and viruses (ICTV5, vConTACT2 (ref. 6) and VIRIDIC7), current computational methods struggle to scale these taxonomies to the magnitude of current metagenomic output. One of the main challenges here is the clustering of genomes into taxonomically consistent groups. In this context, we adopt the American Society for Microbiology’s definition of microbes to include all microscopic life forms and viruses. Consequently, in this study, we refer to the vast uncharacterized fraction of both prokaryotic and viral entities with the term microbial dark matter.
Traditionally, microbial genomes have been clustered using methods that consider their phylogeny, which infers the evolutionary relationships between organisms and defines huge phylogenetic trees8. These are built by aligning genomes of different organisms and identifying similarities among their genomic regions. However, phylogenetic methods are not well suited for clustering large datasets of genomes, mainly because requiring the alignment of all the genomes under study can be computationally prohibitive, especially for datasets containing hundreds of thousands, or even millions, of genomes.
In recent years, several methods have been developed for the clustering of microbial genomes based on the analysis of k-mers, that is, by comparing the set of k-mers present in each genome in the dataset2,9. Genomes that share a large number of k-mers are likely more closely related than genomes that share a small number of k-mers. However, existing k-mer-based methods, such as the widely used species-level genome bins approach based on the average-linkage hierarchical clustering of microbial genomes2, rely on fixed thresholds to delineate clusters at different taxonomic levels (5% of genetic distance to define species, 10% to define genera and 30% to define families). This approach can limit the ability to capture finer-grained taxonomic distinctions, especially for less well-characterized microbial lineages, where the boundaries between clusters of genomes may be less clear, or for higher taxonomic levels, where thresholds cannot be easily defined. Additionally, the thresholds on the genomes’ genetic distances have been designed to work with Bacteria and Archaea and cannot be directly applied to other microbial kingdoms.
Given these limitations, we built a framework to organize large amounts of microbial genomes. We leveraged Sequence Bloom Trees (SBTs)10, hierarchies of Bloom filters (BFs), probabilistic data structures that efficiently store k-mer presence information. Unlike traditional alignment, which scales quadratically, SBTs allow for rapid containment queries, enabling the interrogation of massive sequence collections with minimal memory footprint.
MetaSBT is a scalable k-mer-based framework specifically designed for the incremental clustering of massive amounts of microbial reference genomes and metagenome-assembled genomes (MAGs), with the final aim of uncovering groups of yet-to-be-named microbes at different taxonomic levels.
Here, we provide a detailed description of the MetaSBT framework, including its underlying methodology and data structures, with its software architecture illustrated in Fig. 1. We constructed and validated MetaSBT databases and applied the framework to a set of publicly available viral genomes for building a series of public MetaSBT databases. We exploited our databases to extend and improve the ability of quantitative taxonomic profilers to detect still-unknown viral species and integrate our framework and its databases into the Galaxy platform for broader accessibility.
Module 1: index. Reference genomes and taxonomic metadata retrieved from public repositories (for example, NCBI GenBank) undergo quality assessment and dereplication. Next, optimal k-mer length and BF size are estimated. The core index is then constructed bottom–up, from the species level up to the kingdom level, producing a hierarchy of SBTs, which serves as the foundational MetaSBT reference database. Module 2: profile. Uncharacterized input genomes (for example, MAGs) are queried against the index. The framework performs a top–down database traversal (kingdom to species), using bitwise distance estimation to find the closest cluster match. This module outputs a full taxonomic classification label for the input sequence based on containment proximity. Module 3: update. To expand the database without requiring a computationally expensive from-scratch reconstruction, collections of uncharacterized genomes trigger an internal call to the profile module. The framework evaluates a decision node: is the genome within a known cluster boundary? If yes, the genome is assigned to the existing taxonomy, and that specific subtree is updated. If no, MetaSBT isolates the unassigned genomes and calculates intracluster distances to delineate structurally robust novel clusters. These new taxonomic topologies are dynamically integrated into the tree, resulting in an expanded, updated database that iteratively maps unknown microbial sequence space. DB, database.
Although MetaSBT is a general-purpose framework applicable to all microbial domains, this study used the viral domain as the primary test environment to demonstrate the scalability and accuracy of the system under high-diversity conditions.
We built the first baseline of the database using all the viral reference genomes in NCBI GenBank11. The set of references comprised 26,285 genomes organized into 17 phyla, 38 classes, 63 orders, 161 families, 1,014 genera and 8,169 species. Genomes were automatically retrieved with the get_ncbi_genomes subroutine implemented in MetaSBT, which establishes whether a genome in NCBI GenBank is a reference genome or a MAG (or vMAG specifically, with ‘v’ standing for viral) according to a series of rules, as reported in Supplementary Tables 3 and 4.
We also retrieved a set of 1,111 vMAGs from NCBI GenBank, where genomes are classified as vMAGs according to the same set of rules. We used these genomes to produce a database by updating the initial database with reference genomes only. The update process resulted in the definition of 28 unknown orders, as far as we know, 79 families, 268 genera and 936 species.
To demonstrate the ability of MetaSBT to handle heterogeneous sources, we also considered the viral sequences distributed in the public Metagenomic Gut Virus (MGV) catalog12 over the MetaSBT database, with NCBI GenBank genomes and vMAGs as an incremental update. MGV contains a metagenomic compendium of roughly 190,000 DNA viruses from the human gut microbiome, which we treated as vMAGs for updating our database. It greatly expanded the set of unknown taxa to 2,976 additional classes, 6,460 orders, 8,622 families, 12,634 genera and 31,624 species. The MGV genomes were originally identified using a comprehensive viral detection pipeline developed by the MGV team, which integrates multiple features and classifiers to distinguish viral contigs from non-viral contigs in metagenomic assemblies. The pipeline combines gene prediction via Prodigal13, functional annotation through HMMER14 searches against both viral (Integrated Microbial Genomes/Virus Resource) and microbial (Pfam) marker gene databases15,16, k-mer-based viral sequence scoring using VirFinder17 and sequence-level characteristics such as strand switch rates. The final classification step is based on a rule-based system that integrates these features using logic that is adapted to different contig length ranges. This pipeline is well explained in the MGV publication12 and on GitHub at https://github.com/snayfach/MGV. We are currently planning to adopt the same procedure in future analyses of publicly available metagenomic samples. The viral genomes recovered from these samples will be periodically integrated into MetaSBT.
The MetaSBT database presented here was constructed using the whole set of k-mers in the involved genomes. As previously explained, we used KITSUNE, which reported nine as the best k-mer size for our set of genomes. This parameter was also used to establish a proper BF size, which is determined using ntCard, defined as the total number of distinct k-mers. As detailed in the previous section, we applied our 100% over provisioning factor to the estimated BF size to accommodate future updates and avoid early saturation, and we used a single hash function to maximize index construction and query speed.
Because the k-mer size is involved in every aspect of the MetaSBT framework, once established, it can only be changed at the price of rebuilding the whole database from scratch. This is why it is important to estimate a proper kingdom-specific k-mer size before building a database.
