Scoring Matrices That Induce Metrics on Sequences

摘要

Scoring matrices are widely used in sequence comparisons. A scoring matrix γ is indexed by symbols of an alphabet. The entry in γ in row a and column b measures the cost of the edit operation of replacing symbol a by symbol b. For a given scoring matrix and sequences s and t, we consider two kinds of induced scoring functions. The first function, known as weighted edit distance, is defined as the sura of costs of the edit operations required to transform s into t. The second, known as normalized edit distance, is defined as the minimum quotient between the sum of costs of edit operations to transform s into t and the number of the corresponding edit operations. In this work we characterize the class of scoring matrices for which the induced weighted edit distance is actually a metric. We do the same for the normalized edit distance.