Phylo-HS: A phylogenetic hierarchical softmax for taxonomic classification

Romain MenegauxbioRxiv 2025 · DOI

TL;DR

This paper introduces Phylo-HS, a novel hierarchical softmax method for taxonomic classification of DNA sequencing reads. By leveraging the natural phylogenetic tree structure of microbial life, Phylo-HS significantly speeds up classification and improves accuracy compared to existing methods, making large-scale metagenomic analysis more efficient and reliable.

What Problem Does This Paper Address?

Metagenomics, the study of genetic material from environmental samples, relies heavily on taxonomic binning to identify the organisms present. This involves assigning short DNA sequences (reads) to their corresponding taxonomic labels (e.g., species, genus). As the number of known genomes and species explodes, traditional machine learning models, particularly those using a standard softmax layer for classification, struggle with scalability. The softmax layer's computational cost grows linearly with the number of possible taxonomic labels, becoming a significant bottleneck during both training and inference. Existing hierarchical softmax methods offer speedups but often sacrifice accuracy. This paper aims to bridge this gap by developing a hierarchical softmax that effectively utilizes the inherent taxonomic hierarchy to achieve both speed and accuracy.

Methods

The core innovation is Phylo-HS, a hierarchical softmax (HSM) approach that integrates the phylogenetic tree into the classification process.

  • Hierarchical Softmax (HSM): Instead of a single, flat classification layer, HSM breaks down the classification problem into a series of smaller, hierarchical decisions. For a given input (a DNA read's representation), the model first predicts a broader taxonomic group (a cluster), and then within that cluster, it predicts the specific taxon. This is achieved by learning classifiers for each internal node of a tree.
  • Phylogenetic Tree Integration: Unlike traditional HSMs that might group taxa based on frequency or arbitrary similarity, Phylo-HS explicitly uses the taxonomic tree (derived from the reference tree of life) to define the hierarchy. This means that closely related species are naturally grouped together in the hierarchy.
  • Tree Construction: The classification tree for Phylo-HS is built by extracting the full lineage of all training taxa and their ancestors from a reference tree of life. This tree is then binarized to maximize computational efficiency. For nodes with multiple children, the children are split into two groups based on their frequencies (proportional to genome sizes) to ensure a balanced tree structure, aiming to keep more frequent taxa higher up for faster access. This creates a hybrid tree that combines aspects of the taxonomic tree and Huffman coding trees.
  • Input Representation: DNA reads are transformed into a fixed-dimensional vector representation using fastDNA, which averages the embeddings of k-mers within the read. This representation is jointly trained with the classification layer.

Datasets

The authors evaluated Phylo-HS on several datasets of increasing complexity:

  • Small, Medium, and Large datasets: These are derived from [Vervier et al., 2016] and contain 51, 193, and 771 species, respectively, with corresponding numbers of genomes.
  • Large validation set: Composed of 193 genomes not present in the training set of the "large" dataset, used to evaluate generalization.
  • DeepMicrobes dataset: A more realistic dataset with 10,857 genomes from 3,640 species, obtained from the DeepMicrobes preprint [Liang et al., 2019].
  • RefSeq dataset: The largest dataset used, containing complete microbial genomes from RefSeq as of 2018, with 23,000 genomes and 13,000 taxa. For practical reasons, viruses were grouped into a single taxonomic ID, resulting in 5,500 taxa.

The reference taxonomic tree used was downloaded from the NCBI taxonomy on 30/09/2020.

Key Insights and Ideas

  • Phylogenetic structure is informative for classification: By leveraging the natural relationships between taxa, Phylo-HS can group similar organisms together, leading to more accurate predictions and efficient computation. This is a more principled approach than arbitrary frequency-based grouping.
  • Hierarchical softmax can overcome scalability bottlenecks: The paper demonstrates that HSMs, particularly when well-designed, can significantly reduce the computational burden of classifying against a vast number of classes, a critical issue in modern metagenomics.
  • Balancing speed and accuracy: Phylo-HS achieves an order of magnitude speedup while simultaneously improving classification accuracy over frequency-based HSMs, suggesting that the phylogenetic structure is not only computationally beneficial but also taxonomically meaningful.

Key Results

  • Speed Improvement: Phylo-HS achieves an order of magnitude speed improvement on a dataset with 5,000 classes compared to standard softmax. Both training and testing speeds are significantly enhanced, especially on larger datasets.
  • Accuracy Improvement: Phylo-HS outperforms frequency-based hierarchical softmax methods in classification accuracy. On the "large" dataset, Phylo-HS shows better species-level precision and recall compared to Huffman tree-based HSMs.
  • Scalability: The paper highlights that standard softmax becomes prohibitively slow for large label sets, whereas hierarchical softmax models (including Phylo-HS) are much less affected.

Limitations and Future Work

  • Nomenclature-agnostic vs. Taxonomy-dependent: The authors acknowledge that frequency-based trees (like Huffman coding) are nomenclature-agnostic, meaning they don't rely on official taxonomic IDs. This could be an advantage for characterizing genomes of unknown species.
  • Future Work: The paper suggests that Phylo-HS could be applied to cases where taxonomic IDs are not readily available by clustering genomes based on similarity measures (e.g., Average Nucleotide Identity). They also propose using tools that infer phylogenetic trees from raw genomes to build the taxonomic classification tree for training.

Summary updated

Abstract

Abstract Taxonomic binning –assigning taxonomic labels to DNA sequencing reads – is a core component of metagenomics data analysis. While machine learning approaches offer competitive speed and accuracy, their scalability is hindered by the growing number of referenced genomes and species. A major bottleneck lies in the final softmax layer of neural network models, which computes probabilities and gradients for all outcome classes. To address this, we propose Phylo-HS , a hierarchical softmax method that leverages the taxonomic tree to group classes into meaningful clusters. Phylo-HS achieves an order of magnitude speed improvement on a dataset with 5,000 classes and improves classification accuracy compared to frequency-based hierarchical softmax methods. By integrating phylogenetic structure into the model, Phylo-HS effectively balances scalability and accuracy for large-scale metagenomic analysis.
BibTeX
@misc{menegaux2025phylo,
  author = {Romain Menegaux},
  title = {{Phylo-HS: A phylogenetic hierarchical softmax for taxonomic classification}},
  year = {2025},
  doi = {10.1101/2025.01.27.634943},
  howpublished = {bioRxiv},
}

Loading related content...

Figure