Distance Types

Here you will find complete descriptions of all the alignment-free distance measures implemented with KAST along with references.

Euclid (AKA Euler or Euclidean Distance)

To select Euclid as a distance measurement within KAST, use the -t euclid flag.

$Eu(\mathbf{f}_{X},\mathbf{f}_{Y})=\left ( \sum_{i=1}^{4^{k}}\left | f_{X,i}-f_{Y,i} \right |^2 \right ) ^{1/2}$

Manhattan

To select Manhattan as a distance measurement within KAST, use the -t manhattan flag.

$Ma(\mathbf{f}_{X},\mathbf{f}_{Y})=\sum_{i=1}^{4^{k}}\left | f_{X},i-f_{Y,i} \right |$

d2

To select d2 [5] as a distance measurement within KAST, use the -t d2 flag.

$D_{2}(C_{X},C_{Y})=\sum_{i=1}^{4^{k}}C_{X},i C_{Y},i$

Chebyshev

To select Chebyshev as a distance measurement within KAST, use the -t chebyshev flag.

$Ch(\mathbf{f}_{X},\mathbf{f}_{Y})=\max_{1\leq i\leq 4^k}\left | f_{X,i}-f_{Y,i} \right |$

Normalised Google Distance

To select Normalised Google Distance [6] as a distance measurement within KAST, use the -t ngd flag.

$NGD_{xy}= \frac{C(xy)-min(C(x),C(y))}{max(C(x),C(y))}$

Bray-Curtis

To select Bray-Curtis [4] as a distance measurement within KAST, use the -t bc flag.

$BC_{ij}= \frac{\sum x_{i}-x_{j}}{\sum \left ( x_{i}+x_{j} \right )}$

Markov Based Measures

D2S

To select D2S [1] as a distance measurement within KAST, use the -t D2S flag.

$D_{2}^{S}(\widetilde{C}_{X},\widetilde{C}_{Y})=\sum_{i=1}^{4^{k}}\frac{\widetilde{C}_{X,i}\widetilde{C}_{Y,i}}{\sqrt{\widetilde{C}_{X,i}^{2}+\widetilde{C}_{Y,i}^{2}}}$

D2Star (AKA D2*)

To select D2Star [1] as a distance measurement within KAST, use the -t D2Star flag.

$D_{2}^{*}(\widetilde{C}_{X},\widetilde{C}_{Y})=\sum_{i=1}^{4^{k}}\frac{\widetilde{C}_{X,i} \widetilde{C}_{Y,i}}{\sqrt{\sqrt{n_{X}P_{X,i}}\sqrt{n_{Y}P_{Y,i}}}}$

S2 (AKA dAI)

To select S2 [3] as a distance measurement within KAST, use the -t dai flag.

$H_X=\sum_{i=1}^{4^k}\varphi_{X,i}\ln\frac{2_{\varphi_{X,i}}}{\varphi_{X,i}+\varphi_{Y,i}},H_Y=\sum_{i=1}^{4^k}\varphi_{Y,i}\ln\frac{2_{\varphi_{Y,i}}}{\varphi_{X,i}+\varphi_{Y,i}}$

$S2.k.r(\vartheta_X,\vartheta_Y)=\begin{cases} 0 & \text{ if } \vartheta_X = \vartheta_Y \\ \frac{1}{4^{k}} (H_X +H_Y)+2\ln 2 & \text{ else } \end{cases}$

d2s

To select d2s [2] as a distance measurement within KAST, use the -t d2s flag.

$d_2^S(\widetilde{C}_X,\widetilde{C}_Y)= \frac{1}{2} \left ( 1- \frac{D_2^S(\widetilde{C}_X,\widetilde{C}_Y))}{\left (\sqrt{\sum_{i=1}^{4^k}\frac{\widetilde{C}_{X,i}^{2}}{\widetilde{C}_{X,i}^{2}+\widetilde{C}_{Y,i}^{2}} } \sqrt{\sum_{i=1}^{4^k}}\frac{\widetilde{C}_{Y,i}^{2}}{\widetilde{C}_{X,i}^{2}+\widetilde{C}_{Y,i}^{2}} \right )} \right )$

d2star (AKA d2*)

To select d2star [2] as a distance measurement within KAST, use the -t d2star flag.

$d_2^*(\widetilde{C}_X,\widetilde{C}_Y)= \frac{1}{2} \left ( 1- \frac{D_2^*(\widetilde{C}_X,\widetilde{C}_Y))}{\left (\sqrt{\sum_{i=1}^{4^k}\frac{\widetilde{C}_{X,i}^{2}}{ n_Xp_{X,i} }} \sqrt{\sum_{i=1}^{4^k}\frac{\widetilde{C}_{Y,i}^{2}}{n_Yp_{Y,i}}} \right )} \right )$

References

[1]: Reinert G, Chew D, Sun F, Waterman MS. Alignment-Free Sequence Comparison (I): Statistics and Power. Journal of Computational Biology. 2009;16(12):1615-1634. doi:10.1089/cmb.2009.0198.

[2]: Wang Y, Liu L, Chen L, Chen T, Sun F. Comparison of Metatranscriptomic Samples Based on k-Tuple Frequencies. Parkinson J, ed. PLoS ONE. 2014;9(1):e84348. doi:10.1371/journal.pone.0084348.

[3]: Dai Q, Yang Y, Wang T (2008) Markov model plus k-word distributions: a synergy that produces novel statistical measures for sequence comparison. Bioinformatics 24: 2296–2302.

[4]: Bray, J. R. and Curtis, J. T. (1957), An Ordination of the Upland Forest Communities of Southern Wisconsin. Ecological Monographs, 27: 325-349. doi:10.2307/1942268

[5]: Blaisdell B (1986) A measure of the similarity of sets of sequences not requiring sequence alignment. Proc Natl Acad Sci USA 83: 5155–5159.

[6]: R. L. Cilibrasi and P. M. B. Vitanyi, "The Google Similarity Distance," in IEEE Transactions on Knowledge and Data Engineering, vol. 19, no. 3, pp. 370-383, March 2007. doi: 10.1109/TKDE.2007.48

Provide feedback

Saved searches

Use saved searches to filter your results more quickly

Distance Types

Euclid (AKA Euler or Euclidean Distance)

Manhattan

d2

Chebyshev

Normalised Google Distance

Bray-Curtis

Markov Based Measures

D2S

D2Star (AKA D2*)

S2 (AKA dAI)

d2s

d2star (AKA d2*)

References

Uh oh!

Uh oh!

Uh oh!

Uh oh!

Uh oh!

Clone this wiki locally