03.com.ua- свободная медицинская энциклопедия. Каждый зарегистрированый участник может редактировать статьи
Расстояние Хэмминга
Расстояние Хэмминга — мера (точнее, метрика) различия объектов одинаковой размерности.
Первоначально метрика была сформулирована Ричардом Хэммингом во время его работы в Bell Labs для определения меры различия между кодовыми комбинациями (двоичными векторами) в векторном пространстве кодовых последовательностей, в этом случае расстоянием Хэмминга <math>\mathbf{d (x, y)}</math> между двумя двоичными последовательностями (векторами) <math>\mathbf{X}</math> и <math>\mathbf{Y}</math> длины <math>\mathbf{n}</math> называется число позиций, в которых они различны — в такой формулировке расстояние Хэмминга вошло в Словарь алгоритмов и структур данных Национального Института Стандартов США (Шаблон:Lang-en).
Так, расстояние Хэмминга между векторами 00111 и 10101 равно 2 (красным отмечены различающиеся биты). В дальнейшем метрика была обобщена на q-ичные последовательности: для пары строк «выборы» и «забора» расстояние Хэмминга равно трём.
В общем виде расстояние Хэмминга <math>\mathbf{d_H}</math> для объектов <math>\mathbf{X_i}</math> и <math>\mathbf{X_j}</math> размерности <math>\mathbf{p}</math> задаётся функцией:
- <math>d_H (X_i ,X_j ) = \sum\limits_{s = 1}^p {\left| {x_i^{(s)} - x_j^{(s)} } \right|}</math>
Расстояние Хэмминга обладает свойствами метрики, удовлетворяя следующим условиям:
- <math>\mathbf{d_H (X_i ,X_j ) \ge 0}</math>
- <math>\mathbf{d_H (X_i ,X_i ) = 0}</math>
- <math>\mathbf{d_H (X_i ,X_j ) = d_H (X_j ,X_i )}</math>
- <math>\mathbf{d_H (X_i ,X_k ) \le d_H (X_i ,X_j ) + d_H (X_j ,X_k )}</math>
Содержание
Расстояние Хэмминга в биоинформатике и геномике
Для нуклеиновых кислот (ДНК и РНК) возможность гибридизации двух полинуклеотидных цепей с образованием вторичной структуры - двойной спирали - зависит от степени комплементарности нуклеотидных последовательностей обеих цепей. При увеличении расстояния Хэмминга количество водородных связей, образованных комплементарными парами оснований уменьшается и, соответственно, уменьшается стабильность двойной цепи. Начиная с некоторого граничного расстояния Хэмминга гибридизация становится невозможной.
При эволюционном расхождении гомологичных ДНК-последовательностей расстояние Хэмминга является мерой, по которой можно судить о времени, прошедшем с момента расхождения гомологов, например, о длительности эволюционного отрезка, разделяющего гены-гомологи и ген-предшественник.
Родственные методы
Литература
- Richard W. Hamming. Error-detecting and error-correcting codes, Bell System Technical Journal 29(2):147-160, 1950.
- Ричард Блейхут. Теория и практика кодов, контролирующих ошибки. М., «Мир», 1986
Ссылки
af:Hammingafstand ca:Distància de Hamming cs:Hammingova vzdálenost de:Hamming-Abstand en:Hamming distance es:Distancia de Hamming fi:Hammingin etäisyys fr:Distance de Hamming he:מרחק המינג hr:Hammingova udaljenost hu:Hamming-távolság it:Distanza di Hamming ja:ハミング距離 ko:해밍 거리 nl:Hammingafstand pl:Odległość Hamminga vi:Khoảng cách Hamming zh:汉明距离