Similarity-preserving Metrics for Amino-acid Sequences

irements. A simple and computationally very effective "distance" measure for sequences is the feature distance [1]. A feature is a short substring, usually referred to as N-gram, N being its length. The feature distance is then computed as the number of features the two strings differ in. It must be noted that this measure is not a distance, for two different strings can have zero distance. For example, strings, AABA and ABAA contain the same bigrams, so with N =2the "distance" between them is zero. Another very common distance measure for strings is the Levenshtein distance [2]. It measures the minimum effort needed to transform one string into another, using basic edit operations: replacement, insertion and deletion of a symbol. Generally, each of these operations has a cost assigned to it, in which case the distance function is usually referred to as weighted Levenshtein distance. This includes very common cases, where replacements of different symbols appear with different probab