Основы биоинформатики - Огурцов А.Н. 2013

Методы биоинформационного анализа
Матрицы замен
Мера сходства последовательностей

Для количественного измерения сходства и различия последовательностей вводят понятие расстояния (distance) между двумя строками последовательностей.

Мерой расстояния является функция, которая так же, как и мера подобия, присваивает численное значение паре последовательностей, но только на основании иного принципа: чем больше расстояние, тем меньше подобие (и наоборот). Меры расстояния обычно удовлетворяют математическим аксиомам метрики.

В большинстве случаев меры расстояния и подобия взаимозаменимы - в том смысле, что маленькое расстояние означает высокое подобие, и наоборот.

Существует два метода измерения расстояния между двумя данными строками последовательностей.

1. Расстояние Хэмминга (the Hamming distance) определяется количеством несовпадающих позиций между двумя последовательностями одинаковой длины.

Например, расстояние по Хэммингу равно 2 для данных последовательностей

2. Расстояние Левенштайна (the Levenshtein distance) или "редакционное расстояние" - это минимальное число операций редактирования (удаление, вставка или замена), необходимых, чтобы превратить одну строку в другую. (Любая последовательность редактирующих операций порождает уникальное выравнивание, но не наоборот.)

Например, расстояние по Левенштайну равно 3 для данных последовательностей