Embedding the de Bruijn graph, and applications to metagenomics

Romain Menegaux, Jean‐Philippe VertbioRxiv 2020 · DOI

TL;DR

This paper introduces Brume, a novel method for metagenomic read classification that leverages de Bruijn graphs to efficiently embed longer k-mers (up to k=31). By grouping k-mers that co-occur in training data into "contigs" and learning embeddings for these contigs, Brume significantly reduces memory footprint, enabling higher accuracy than previous methods and even competing with traditional alignment-based approaches.

What Problem Does This Paper Address?

Metagenomics, the study of genetic material from environmental samples, relies heavily on accurately assigning short DNA sequencing reads to their source organisms (taxonomic binning). Traditional alignment-based methods are accurate but computationally expensive. Compositional methods, which analyze the frequency of short DNA subsequences (k-mers), offer a faster alternative. However, a key observation is that using longer k-mers generally improves accuracy. The challenge is that the memory required to store models based on all possible k-mers grows exponentially with k, limiting previous machine learning approaches to k-mers of length 12 or 13. This paper tackles the problem of enabling the use of much longer k-mers in machine learning-based compositional methods to boost accuracy without prohibitive memory costs.

Methods

The core innovation is Brume's approach to reducing the memory footprint of k-mer embeddings. Instead of learning an independent vector representation for every possible k-mer, Brume first constructs a compacted de Bruijn graph (cdBG) from the training sequences. In this graph, nodes represent "contigs" (non-branching paths), which are essentially groups of k-mers that tend to appear together in the same reads. Brume then learns a single vector embedding for each contig. When classifying a new read, its constituent k-mers are mapped to their respective contigs, and the read's embedding is computed as the average of its contig embeddings. This significantly reduces the number of embeddings that need to be stored, from the total number of possible k-mers ($4^k$) to the number of contigs ($N_c$), which is much smaller for larger $k$. The paper also mentions an initial step of exploiting DNA symmetry by using canonical k-mers (where a k-mer and its reverse complement share the same representation), which roughly halves the embedding space.

Datasets

The study uses two datasets, referred to as "small" and "large," previously introduced in related work (Vervier et al., 2016; Menegaux and Vert, 2019).

  • Small dataset: Composed of 356 bacterial genomes (training) and 52 validation genomes, from 51 species.
  • Large dataset: Composed of 2961 bacterial genomes (training) and 193 validation genomes, from 774 species.

Reads of length L=200 are extracted from these genomes. For validation, multiple sets of reads are created, including a "no-noise" set and three sets with simulated sequencing errors (Balzer, mutation-2, mutation-5) using the grinder software.

Key Insights and Ideas

  • The power of co-occurrence: The fundamental idea is that k-mers appearing together in reads carry similar information. Grouping them into contigs allows the model to learn a more robust and compressed representation.
  • De Bruijn graphs as a compression tool: The de Bruijn graph naturally captures the relationships between k-mers, and its compacted form provides a principled way to define these "bins" or contigs.
  • Longer k-mers are better, but memory is the bottleneck: The paper strongly reinforces the finding that increasing k generally improves classification performance, but Brume's contig-based embedding is the key to overcoming the memory limitations that previously prevented exploration of large k.
  • Trade-off between recall and precision: As k increases, models become more precise but may fail to classify "hard" reads (those with no matching k-mers in the training set), leading to decreased recall. This is observed as an increase in precision and a decrease in recall for larger k.

Key Results

  • Brume successfully trains models with k-mers up to k=31, significantly exceeding the k=12/13 limit of previous methods.
  • On the small dataset, Brume achieves optimal F1-score at k=23, demonstrating improved performance with larger k.
  • On the large dataset, Brume consistently outperforms previous state-of-the-art methods (fastDNA with k=13) and even the alignment-based BWA-MEM for k-mer lengths between 23 and 31, achieving better F1 scores.
  • Models with larger k are observed to be more robust to sequencing errors, with performance decreasing more slowly than for smaller k models.
  • The proportion of unclassified reads increases with k and noise, contributing to higher precision but lower recall.

Limitations and Future Work

  • Unclassified reads: A significant limitation of using very large k-mers is the increased proportion of reads that cannot be classified because their k-mers are not found in the training set's de Bruijn graph. This leads to a trade-off where recall decreases as precision increases.
  • Hybrid models: The authors explore combining embeddings from short and long k-mers (e.g., k=13 and k=31) to potentially improve both precision and recall. While this boosted recall, it came at a high cost to precision, suggesting that simply averaging embeddings isn't sufficient.
  • Speed impact: The k-mer lookup in the de Bruijn graph introduces a significant overhead for classification speed. While the paper mentions using libraries like kallisto and bifrost for de Bruijn graph construction, reimplementing kallisto's heuristics for faster lookups is suggested as future work.
  • Future directions: The authors believe their contig-based embedding approach can be extended to more sophisticated models (e.g., deep learning) and applied to other fields beyond metagenomics, such as RNA-seq. They also suggest further exploration of hybrid models that might better balance precision and recall.

Summary updated

Abstract

Abstract Fast mapping of sequencing reads to taxonomic clades is a crucial step in metagenomics, which however raises computational challenges as the numbers of reads and of taxonomic clades increases. Besides alignment-based methods, which are accurate but computational costly, faster compositional approaches have recently been proposed to predict the taxonomic clade of a read based on the set of k -mers it contains. Machine learning-based compositional approaches, in particular, have recently reached accuracies similar to alignment-based models, while being considerably faster. It has been observed that the accuracy of these models increases with the length k of the k -mers they use, however existing methods are limited to handle k -mers of lengths up to k = 12 or 13 because of their large memory footprint needed to store the model coefficients for each possible k -mer. In order to explore the performance of machine learning-based compositional approaches for longer k -mers than currently possible, we propose to reduce the memory footprint of these methods by binning together k -mers that appear together in the sequencing reads used to train the models. We achieve this binning by learning a vector embedding for the vertices of a compacted de Bruijn graph, allowing us to embed any DNA sequence in a low-dimensional vector space where a machine learning system can be trained. The resulting method, which we call Brume , allows us to train compositional machine learning-based models with k -mers of length up to k = 31. We show on two metagenomics benchmark that Brume reaches better performance than previously achieved, thanks to the use of longer k -mers.
BibTeX
@misc{menegaux2020embedding,
  author = {Romain Menegaux and Jean‐Philippe Vert},
  title = {{Embedding the de Bruijn graph, and applications to metagenomics}},
  year = {2020},
  doi = {10.1101/2020.03.06.980979},
  howpublished = {bioRxiv},
}
Figure