Whole k-mer set distances
The k-mer composition of a genome provides a representation of its sequence content that can be compared directly between genomes. The distances considered here quantify dissimilarity between genomes from their complete k-mer composition, independently of any particular representation, storage scheme, or indexing strategy.
Two complementary classes of comparison arise according to the information retained about k-mer occurrences (Anderson et al. 2011)1. Presence/absence-based distances consider only whether each distinct k-mer occurs in a genome, whereas abundance-based distances also incorporate its observed frequency. Abundance-based measures may be computed either from raw k-mer counts or from the corresponding relative frequencies.
Let \(A\) and \(B\) denote the k-mer sets of two genomes. For each distinct k-mer \(i\), let \(c_i^A\) and \(c_i^B\) denote its counts in the two genomes, and let
denote the corresponding relative frequencies.
The resulting measures can be classified along two independent dimensions: the information retained about k-mer occurrences (presence/absence versus abundance) and the metric properties of the resulting dissimilarity, in particular whether the triangle inequality is satisfied.
Presence/absence-based distances
When only occurrence is retained, each genome is represented by its incidence vector over the k-mer space. The comparison therefore depends exclusively on the presence or absence of each distinct k-mer and is insensitive to its multiplicity.
The Jaccard distance compares two k-mer sets from the cardinalities of their intersection and union (Jaccard 1901)2:
Jaccard distance is a metric and therefore satisfies the triangle inequality (Kosub 2019)3.
The Hamming distance is the \(L^1\) distance between the corresponding binary incidence vectors:
where \(a_i,b_i\in\{0,1\}\) indicate the presence of k-mer \(i\) in the two genomes. It counts the number of k-mers for which the two incidence vectors differ, without normalization by the size of the k-mer space. As an \(L^1\) distance, Hamming distance is a metric. Unlike abundance-based measures, it cannot be recovered from k-mer counts alone once the presence/absence representation has been discarded. On an index that stores counts, a k-mer is taken as present when its count reaches the presence threshold (--presence-threshold, 1 by default).
Mash is not an independent set dissimilarity but a nonlinear transformation of the Jaccard similarity (Ondov et al. 2016)4. If
the Mash distance is defined as
with the result clamped to \(1.0\) when the Jaccard similarity reaches zero. This transformation is monotone increasing with Jaccard distance and therefore preserves the ordering of pairwise dissimilarities. Monotonicity alone, however, does not guarantee preservation of the triangle inequality. Mash should consequently be regarded as an evolutionary distance estimator derived from k-mer similarity rather than assumed to be a metric.
Abundance-based distances
When k-mer abundances are retained, genomes are represented by non-negative vectors of k-mer counts or frequencies. Distances can then distinguish genomes that contain the same k-mers but differ in their relative abundances.
The Euclidean distance is the ordinary \(L^2\) distance between the corresponding vectors. On raw counts it is
and the same definition applied to relative frequencies gives relfreq-euclidean. In both cases, Euclidean distance is a metric.
The Hellinger distance applies the Euclidean distance to the square-root-transformed relative frequencies (Legendre & Gallagher 2001)5:
It is bounded between 0 and 1 and is a metric because it is a positive rescaling of the Euclidean distance between the transformed vectors \(\sqrt{p^A}\) and \(\sqrt{p^B}\). Its unnormalized form, hellinger-euclidean,
is likewise a metric, since multiplication by a positive constant preserves the triangle inequality.
The Bray–Curtis dissimilarity (Bray & Curtis 1957)6 is defined from the amount of abundance shared between two vectors:
Using
this can equivalently be written as
For arbitrary count vectors, Bray–Curtis is not a metric (Gower & Legendre 1986)7: the pair-dependent normalization by the combined abundance can lead to violations of the triangle inequality. This distinguishes it from the \(L^1\)-based distances above, whose normalization factor is fixed independently of the pair being compared.
The metric property is recovered when all vectors under comparison have the same total abundance \(S\). In that case,
for every pair, and Bray–Curtis reduces to
It is therefore a positive rescaling of the \(L^1\) distance and is a metric on this fixed-total space.
Relative frequencies satisfy this condition by construction, since
Consequently, relfreq-bray-curtis reduces to
which is the total variation distance between the two frequency distributions. It is therefore a metric.
Thus, bray-curtis and relfreq-bray-curtis have the same algebraic form but operate on different domains: the former compares count vectors whose total abundance may vary between genomes, whereas the latter compares normalized frequency vectors with a fixed total. This difference in normalization is sufficient to change the metric properties of the measure.
See phylo for how to select a distance and the resulting output formats.
-
Anderson MJ, Crist TO, Chase JM, Vellend M, Inouye BD, Freestone AL, Sanders NJ, Cornell HV, Comita LS, Davies KF, Harrison SP, Kraft NJB, Stegen JC, Swenson NG (2011) [Navigating the multiple meanings of β diversity: a roadmap for the practicing ecologist]{.nocase}. Ecology Letters, 14, 19--28. ↩
-
Jaccard P (1901) [Étude comparative de la distribution florale dans une portion des Alpes et du Jura]{.nocase}. Bulletin de La Société Vaudoise Des Sciences Naturelles, 37, 547--579. ↩
-
Kosub S (2019) [A note on the triangle inequality for the Jaccard distance]{.nocase}. Pattern Recognition Letters, 120, 36--38. ↩
-
Ondov BD, Treangen TJ, Melsted P, Mallonee AB, Bergman NH, Koren S, Phillippy AM (2016) [Mash: fast genome and metagenome distance estimation using MinHash]{.nocase}. Genome Biology, 17, 132. ↩
-
Legendre P, Gallagher ED (2001) [Ecologically meaningful transformations for ordination of species data]{.nocase}. Oecologia, 129, 271--280. ↩
-
Bray JR, Curtis JT (1957) [An ordination of the upland forest communities of southern Wisconsin]{.nocase}. Ecological Monographs, 27, 325--349. ↩
-
Gower JC, Legendre P (1986) [Metric and Euclidean properties of dissimilarity coefficients]{.nocase}. Journal of Classification, 3, 5--48. ↩