Immunity-Based Computational Models - Immunological Computation: Theory and Applications - page 52

5. Rogers and Tanimoto

ad
ad

f

2( bc )

6. Yule

ad bc

f

ad bc

3.3.3 Edit Distance

h e edit distance between two strings s 1 and s 2 is defi ned as the minimum num-
ber of string transformations required to change s 1 into s 2 where the possible
string transformations are (i) changing a character, (ii) inserting a character, and
(iii) deleting a character. h e edit distance is also called “Levenshtein” distance, and
it is a generalization of the Hamming distance.

3.3.4 Value Difference Metric

Value diff erence metric (VDM) distance is defi ned as (Hamaker and Boggess,
2004)

N

∑

⋅

VDM( xy , ) vdm( x y , ) weight( x )

i i i

i 1

where

( )

2

∑

vdm( xy , ) Pcx ( ) Pcy ( )

i i i i

cC

and

∑

weight( x ) P c x ( )

2

i i

cC

P ( c | x i ) denotes the probability that x i be equal to the character c in the alphabet C .