Расстояние Хэмминга
Материал из Википедии — свободной энциклопедии
Расстояние Хэмминга — число позиций, в которых соответствующие символы двух слов одинаковой длины различны[1]. В более общем случае расстояние Хэмминга применяется для строк одинаковой длины любых q-ичных алфавитов и служит метрикой различия (функцией, определяющей расстояние в метрическом пространстве) объектов одинаковой размерности.
Первоначально
метрика была сформулирована Ричардом
Хэммингом во время его работы
в Bell
Labs для определения меры различия
между кодовыми комбинациями (двоичными
векторами)
в векторном пространстве кодовых
последовательностей, в этом случае
расстоянием Хэмминга
между
двумя двоичными последовательностями
(векторами)
и
длины
называется
число позиций, в которых они различны —
в такой формулировке расстояние Хэмминга
вошло в словарь
алгоритмов и структур данных
национального
института стандартов и технологий США
(англ. NIST
Dictionary of
Algorithms and
Data Structures).
Расстояние Хэмминга является частным
случаем метрики
Минковского (при соответствующем
определении вычитания):
.
Примеры
Свойства
Расстояние Хэмминга обладает свойствами метрики, удовлетворяя следующим условиям:
Расстояние Хэмминга в биоинформатике и геномике
Для нуклеиновых кислот (ДНК и РНК) возможность гибридизации двух полинуклеотидных цепей с образованием вторичной структуры — двойной спирали — зависит от степени комплементарности нуклеотидных последовательностей обеих цепей. При увеличении расстояния Хэмминга количество водородных связей, образованных комплементарными парами оснований уменьшается и, соответственно, уменьшается стабильность двойной цепи. Начиная с некоторого граничного расстояния Хэмминга гибридизация становится невозможной.
При эволюционном расхождении гомологичных ДНК-последовательностей расстояние Хэмминга является мерой, по которой можно судить о времени, прошедшем с момента расхождения гомологов, например, о длительности эволюционного отрезка, разделяющего гены-гомологи и ген-предшественник.
Сходство или
различие между объектами классификации
устанавливается в зависимости от
выбранного метрического расстояния
между ними. Если каждый объект описывается
свойствами
(признаками), то он может быть представлен
как точка в
-мерном
пространстве, и сходство с другими
объектами будет определяться как
соответствующее расстояние. При
классификации используются различные
меры расстояния между объектами.
1. Евклидово расстояние
Это, пожалуй, наиболее часто используемая мера расстояния. Она является геометрическим расстоянием в многомерном пространстве и вычисляется следующим образом:
где:
–
расстояние между
объектами
и
;
–
значение
-свойства
объекта
;
–
значение
-свойства
объекта
.
Естественное, с геометрической точки зрения, евклидова мера расстояния может оказаться бессмысленной, если признаки измерены в разных единицах. Чтобы исправить положение, прибегают к нормированию каждого признака. Применение евклидова расстояния оправдано в следующих случаях:
свойства (признаки) объекта однородны по физическому смыслу и одинаково важны для классификации;
признаковое пространство совпадает с геометрическим пространством.