Fundamentals of Bioinformatics - Ogurtsov, A.N. 2013

Methods of Bioinformatic Analysis
Substitution Matrices
Sequence Similarity Measure

To quantitatively measure the similarity and dissimilarity of sequences, METABOLISM/2.html">THE CONCEPT OF distance between two sequence strings is introduced.

A distance measure is a function that, much like a similarity measure, assigns a numerical value to a pair of sequences, but based on a different principle: the greater the distance, the lower the similarity (and vice versa). Distance measures typically satisfy the mathematical axioms of a metric.

In most cases, distance and similarity measures are interchangeable in the sense that a small distance implies high similarity, and vice versa.

There are two Methods for measuring the distance between two given sequence strings.

1. The Hamming distance is defined as the number of mismatched positions between two sequences of equal length.

For example, the Hamming distance is 2 for the following sequences

Class="center">

2. The Levenshtein distance, or "edit distance", is the minimum number of editing operations (deletion, insertion, or substitution) required to transform one string into another. (Any sequence of editing operations yields a unique alignment, but not vice versa.)

For example, the Levenshtein distance is 3 for the following sequences