Source-linked AI summary
dna2vec: Consistent vector representations of variable-length k-mers
Patrick Ng
TL;DR
One-hot representations of k-mers suffer exponential dimensionality and equidistant pairwise encoding, limiting their suitability for biological-sequence machine learning. The paper proposes dna2vec, a word2vec-based shallow two-layer model for variable-length k-mers. Experiments provide evidence for nucleotide-concatenation-like vector arithmetic and a relationship between Needleman-Wunsch similarity and cosine similarity.
Problem
One-hot k-mer encodings have exponentially increasing dimensionality and equidistant pairwise distances, while biological-sequence machine learning often uses lower-dimensional continuous inputs.
Method
dna2vec trains distributed representations of variable-length k-mers with a word2vec-based shallow two-layer neural network.
Results
The experiments provide evidence that summing dna2vec vectors is akin to nucleotide concatenation and that Needleman-Wunsch similarity correlates with cosine similarity.
Takeaways & Limitations
dna2vec places variable-length k-mers in a consistent embedding space and supports nucleotide-concatenation analogies through vector arithmetic.
Abstract
from arXiv · showhide
One of the ubiquitous representation of long DNA sequence is dividing it into shorter k-mer components. Unfortunately, the straightforward vector encoding of k-mer as a one-hot vector is vulnerable to the curse of dimensionality. Worse yet, the distance between any pair of one-hot vectors is equidistant. This is particularly problematic when applying the latest machine learning algorithms to solve problems in biological sequence analysis. In this paper, we propose a novel method to train distributed representations of variable-length k-mers. Our method is based on the popular word embedding model word2vec, which is trained on a shallow two-layer neural network. Our experiments provide evidence that the summing of dna2vec vectors is akin to nucleotides concatenation. We also demonstrate that there is correlation between Needleman-Wunsch similarity score and cosine similarity of dna2vec vectors.
1 Introduction
The paper introduces dna2vec as a distributed representation for variable-length k-mers, motivated by the dimensionality and distance limitations of one-hot encodings. It connects dna2vec vector arithmetic and cosine similarity with nucleotide concatenation and Needleman-Wunsch alignment similarity.
- Motivation: One-hot k-mer vectors scale exponentially with k, making 8-mers require 48 = 65536 dimensions.This high dimensionality is problematic because many machine-learning tools prefer lower-dimensional continuous inputs.
- Background: Word embeddings provide distributed real-valued representations and have become common inputs to machine-learning algorithms.word2vec learns embeddings with a shallow two-layer neural network from words and their surrounding context.
- dna2vec: dna2vec embeds variable-length k-mers of lengths 3 ≤ k ≤ 8 in a shared continuous vector space.The representation uses 100-dimensional vectors across different k-mer lengths.
- dna2vec: The method generalizes word2vec-style two-layer neural-network embeddings to variable-length k-mers.This distinguishes dna2vec from prior biological-sequence applications that use two-layer embeddings without this variable-length generalization.
- Contributions: The paper provides evidence that dna2vec vector arithmetic is akin to nucleotide concatenation and that its cosine distance relates to Needleman-Wunsch distance.Needleman-Wunsch computes global-alignment similarity with dynamic programming and quadratic time complexity in sequence length.
2 Training dna2vec model
dna2vec training converts genome fragments into overlapping variable-length k-mers, trains an aggregate embedding with a shallow neural network, and decomposes it by k-mer length. The procedure uses word2vec-style context prediction and supports nearest-neighbor search across the resulting models.
- Training pipeline: dna2vec training has four stages: fragment genomes, create overlapping variable-length k-mers, train an aggregate model, and decompose it by k-mer length.The decomposition produces khigh − klow + 1 models for nearest-neighbor searching.
- Stage 1: Genome fragmentation: Genome sequences are split into long non-overlapping fragments, with reverse-complements randomly selected in the hg38 experiments.Fragments were typically a couple of thousand nucleotides and were identified using gap characters.
- Stage 2: Overlapping variable-length k-mers: A sliding window converts DNA sequences into overlapping k-mers, while variable-length extraction samples k uniformly between klow and khigh.For example, a sequence can produce overlapping fixed-length 5-mers or mixed-length k-mers sampled from {3, 4, 5}.
- Stage 3: Two-layer neural network: An aggregate DNA k-mer embedding is trained with a shallow two-layer neural network based on word2vec.The method supports CBOW and skip-gram formulations; the experiments use skip-gram.
- Stage 3: Two-layer neural network: The model predicts adjacent k-mers surrounding a targeted k-mer as its context.The experiments use a context size of 10 before and after the target, predicting 20 k-mers, with negative sampling for optimization.
3 Experiments
The experiments evaluate dna2vec similarity, nearest neighbors, vector addition, alignment similarity, and nucleotide-concatenation analogies. Results support relationships between dna2vec arithmetic, string concatenation, and Needleman-Wunsch similarity.
- 3.1 Similarity and nearest neighbors: Cosine similarity defines comparisons between dna2vec vectors, while nearest neighbors select k-mers maximizing similarity to a query vector.The nearest-neighbor procedure searches all k-mers of a specified length using the cosine-similarity measure.
- 3.2 dna2vec arithmetic and nucleotide concatenation: Summing dna2vec embeddings produced neighbors overlapping the string concatenation of the summed k-mers.The experiment used 1000 samples for each operand and evaluated overlap among n-nearest neighbors.
- 3.3 Relationship to global alignment similarity: Needleman-Wunsch similarity distributions of k-mers and their nearest dna2vec neighbors were compared with distributions for random k-mer pairs.The experiment sampled 1000 8-mers, identified each nearest neighbor, and computed alignment scores against a 1000-pair random null distribution.
- 3.4 Analogy of nucleotide concatenation: The experiments tested strong and weak nucleotide concatenation analogies by splicing snippets onto k-mers at either the 5’ or 3’ end.Strong concatenation restricts splicing to the same end, whereas weak concatenation relaxes that restriction.
- 3.4 Analogy of nucleotide concatenation: 88% accuracy was achieved for weak concatenation analogies of an 8-mer with a 4-nucleotide snippet using 10-NN.The experiments also compared correct matching snippets with scrambled random snippets and found a significant preference for the correct snippets.
4 Discussion
The discussion concludes that dna2vec provides consistent variable-length k-mer representations, with vector arithmetic and cosine similarity reflecting nucleotide concatenation and alignment similarity.
- dna2vec represents variable-length k-mers consistently through nucleotide concatenation experiments.
- Arithmetic on dna2vec vectors is akin to nucleotide concatenation.
- Needleman-Wunsch similarity between arbitrary k-mers correlates with cosine distance between their dna2vec vectors.
- Future work will apply dna2vec with machine learning techniques to biological sequence analysis.This direction reflects the need for fixed-length continuous vectors as machine-learning inputs.