0 Fork 0

Table of Contents

Whole k-mer set distances

Presence/absence-based distances
Abundance-based distances
Bibliography

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). 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

p_i^A=\frac{c_i^A}{\sum_j c_j^A}, \qquad p_i^B=\frac{c_i^B}{\sum_j c_j^B}

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):

D = 1 - \frac{\lvert A \cap B \rvert}{\lvert A \cup B \rvert}.

Jaccard distance is a metric and therefore satisfies the triangle inequality (Kosub 2019).

The Hamming distance is the L^1 distance between the corresponding binary incidence vectors:

D = \sum_i \mathbb{1}[a_i \ne b_i],

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.

Mash is not an independent set dissimilarity but a nonlinear transformation of the Jaccard similarity (Ondov et al. 2016). If

J = 1-D_{\mathrm{Jaccard}},

the Mash distance is defined as

D = -\frac{1}{k}\ln\left(\frac{2J}{1+J}\right) = -\frac{1}{k}\ln\left(\frac{2(1-J_{\mathrm{Jaccard}})} {2-J_{\mathrm{Jaccard}}}\right),

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

D = \sqrt{\sum_i (c_i^A-c_i^B)^2},

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):

D = \frac{1}{\sqrt{2}}\sqrt{\sum_i\left(\sqrt{p_i^A}-\sqrt{p_i^B}\right)^2}.

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,

\begin{aligned} D &=\sqrt{\sum_i\left(\sqrt{p_i^A}-\sqrt{p_i^B}\right)^2} \\ &=\sqrt{2}\,D_{\mathrm{Hellinger}}, \end{aligned}

is likewise a metric, since multiplication by a positive constant preserves the triangle inequality.

The Bray–Curtis dissimilarity (Bray & Curtis 1957) is defined from the amount of abundance shared between two vectors:

D = 1-\frac{2\sum_i\min(c_i^A,c_i^B)}{\sum_i c_i^A+\sum_i c_i^B}.

Using

a+b-2\min(a,b)=|a-b|,

this can equivalently be written as

D = \frac{\sum_i|c_i^A-c_i^B|} {\sum_i c_i^A+\sum_i c_i^B}.

For arbitrary count vectors, Bray–Curtis is not a metric (Gower & Legendre 1986): 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,

\sum_i c_i^A=\sum_i c_i^B=S

for every pair, and Bray–Curtis reduces to

D = \frac{1}{2S} \sum_i|c_i^A-c_i^B|.

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

\sum_i p_i^A=\sum_i p_i^B=1.

Consequently, relfreq-bray-curtis reduces to

D = \frac12\sum_i|p_i^A-p_i^B|,

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.

Bibliography

Anderson, M.J., Crist, T.O., Chase, J.M., Vellend, M., Inouye, B.D., Freestone, A.L., et al. (2011). Navigating the multiple meanings of β diversity: a roadmap for the practicing ecologist. Ecology Letters, 14, 19–28.

Bray, J.R. & Curtis, J.T. (1957). An ordination of the upland forest communities of southern Wisconsin. Ecological Monographs, 27, 325–349.

Gower, J.C. & Legendre, P. (1986). Metric and Euclidean properties of dissimilarity coefficients. Journal of Classification, 3, 5–48.

Jaccard, P. (1901). Étude comparative de la distribution florale dans une portion des Alpes et du Jura. 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. Pattern Recognition Letters, 120, 36–38.

Legendre, P. & Gallagher, E.D. (2001). Ecologically meaningful transformations for ordination of species data. Oecologia, 129, 271–280.

Ondov, B.D., Treangen, T.J., Melsted, P., Mallonee, A.B., Bergman, N.H., Koren, S., et al. (2016). Mash: fast genome and metagenome distance estimation using MinHash. Genome biology, 17, 132.

Whole k-mer set distances

Presence/absence-based distances

Abundance-based distances

Bibliography

Wiki sidebar

Theory

Kmer indexing

Phylogeny

Kmer-based

SNP-based

Usage

Formats