Distance Types

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

d2

To select d2 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$

Normalised Google Distance

To select Normalised Google Distance 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 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 )}$

S2 (AKA dAI)

To select S2 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}$

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 |$

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 |$

Markov Based Measures

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})=\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 [2] 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}}}}$

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)= \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 [1] 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]: 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.

[2]: 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.

Provide feedback

Saved searches

Use saved searches to filter your results more quickly

Distance Types

d2

Normalised Google Distance

Bray-Curtis

S2 (AKA dAI)

Euclid (AKA Euler or Euclidean Distance)

Manhattan

Chebyshev

Markov Based Measures

D2S

D2Star (AKA D2*)

d2s

d2star (AKA d2*)

References

Uh oh!

Uh oh!

Uh oh!

Uh oh!

Uh oh!

Uh oh!

Clone this wiki locally