Continuous embeddings of DNA sequencing reads, and application to metagenomics

Romain Menegaux, Jean‐Philippe VertbioRxiv 2018 · DOI

TL;DR

This paper introduces fastDNA, a novel method that represents DNA sequencing reads as continuous low-dimensional vectors by learning embeddings for k-mers. This approach significantly outperforms existing methods in metagenomic classification accuracy and scalability, offering a faster and more memory-efficient alternative to traditional alignment-based techniques.

What Problem Does This Paper Address?

The explosion of DNA sequencing data has created a bottleneck in its analysis. Traditional methods for tasks like metagenomic classification (identifying species present in a sample) rely on computationally intensive alignment algorithms (e.g., BLAST, BWA). While compositional approaches, which analyze the frequency of short DNA subsequences (k-mers), offer a faster alternative, they often require very high-dimensional representations (millions of dimensions for k=12) and large memory footprints. This paper tackles the challenge of developing a compositional method that is both accurate and scalable, addressing the need for efficient analysis of massive genomic datasets.

Methods

The core innovation of fastDNA lies in learning continuous, low-dimensional embeddings for k-mers. Instead of using a sparse, high-dimensional representation where each k-mer is a distinct dimension, fastDNA maps each k-mer to a dense vector in a much smaller dimensional space (e.g., 100 dimensions). This embedding is learned end-to-end as part of a multiclass classification task, optimizing a cross-entropy loss using stochastic gradient descent. This approach is inspired by recent advances in natural language processing, such as fastText and word2vec, but adapted for DNA sequences. The authors also explore regularization techniques, including adding random mutations to training data, which surprisingly improves robustness and performance.

Datasets

The authors evaluate fastDNA on two benchmarks previously used in related work:

  • Small dataset: Contains 356 complete bacterial genomes from 51 species, with a validation set of 52 genomes.
  • Large dataset: Features 2,961 genomes from 774 species, with a validation set of 193 genomes.

Reads of length 200 bp are sampled from these genomes. The paper also introduces noisy validation sets by simulating sequencing errors (substitutions, insertions, deletions) at rates of 2% and 5% using the grinder software, and a homopolymeric error model.

Key Insights and Ideas

  • Low-dimensional embeddings are sufficient: The paper demonstrates that learning low-dimensional representations of k-mers is highly effective for metagenomic classification, achieving competitive or superior accuracy compared to high-dimensional methods.
  • End-to-end learning is powerful: Optimizing the k-mer embeddings directly for the classification task, rather than using pre-defined embeddings, leads to better performance.
  • Noise as regularization: Introducing random mutations to training data acts as a powerful regularization technique, improving robustness to sequencing errors and intra-species heterogeneity. This is a counter-intuitive but highly effective finding.
  • Scalability benefits: The low-dimensional nature of the embeddings significantly reduces memory footprint and speeds up classification, making it practical for large-scale metagenomic analysis.

Key Results

  • Accuracy: fastDNA outperforms state-of-the-art compositional methods (like VW) in terms of average species-level recall and precision, especially on noisy datasets. For instance, on the large dataset with mutation-5 noise, fastDNA maintains higher accuracy than VW.
  • Speed: fastDNA is significantly faster than alignment-based methods like BWA-MEM, achieving classification speeds of up to 7.5 x 10^3 reads per second (compared to BWA's 1.2-2.2 x 10^3 reads per second on noisy data).
  • Memory: The use of low-dimensional embeddings and Product Quantization (PQ) for compression drastically reduces the model's memory footprint, making it feasible to train and deploy on standard hardware. For example, PQ can reduce model size by an order of magnitude.
  • K-mer size vs. dimension: The paper shows that longer k-mers can be used effectively with smaller embedding dimensions, offering a trade-off between k-mer size and embedding dimension to achieve similar performance. For example, k=14, d=10 performs similarly to k=12, d=50.

Limitations and Future Work

  • Error model realism: The authors suggest using a more realistic error model for training than simple uniform substitutions to better mimic real-world sequencing noise.
  • Beyond contiguous k-mers: Future work could explore extending the notion of "word" to include gap-seeded k-mers or Bloom filters to capture longer-range dependencies in DNA sequences.
  • Other applications: The authors propose that fastDNA could be adapted for other tasks, such as classifying RNA-seq reads for gene expression quantification, which involves a much larger number of classes.
  • Non-convexity: The learning problem is non-convex when the embedding dimension d is smaller than the number of classes T, meaning SGD might converge to a local optimum.

Summary updated

Abstract

Abstract We propose a new model for fast classification of DNA sequences output by next generation sequencing machines. The model, which we call fastDNA , embeds DNA sequences in a vector space by learning continuous low-dimensional representations of the k -mers it contains. We show on metagenomics benchmarks that it outperforms state-of-the-art methods in terms of accuracy and scalability.
BibTeX
@misc{menegaux2018continuous,
  author = {Romain Menegaux and Jean‐Philippe Vert},
  title = {{Continuous embeddings of DNA sequencing reads, and application to metagenomics}},
  year = {2018},
  doi = {10.1101/335943},
  howpublished = {bioRxiv},
}
Figure