Расстояние Хэмминга

Расстояние Хэмминга — мера (точнее, метрика) различия объектов одинаковой размерности.

Первоначально метрика была сформулирована Ричардом Хэммингом во время его работы в Bell Labs для определения меры различия между кодовыми комбинациями (двоичными векторами) в векторном пространстве кодовых последовательностей, в этом случае расстоянием Хэмминга \mathbf{d (x, y)} между двумя двоичными последовательностями (векторами) \mathbf{X} и \mathbf{Y} длины \mathbf{n} называется число позиций, в которых они различны — в такой формулировке расстояние Хэмминга вошло в Словарь алгоритмов и структур данных Национального Институра Стандартов США (англ. NIST Dictionary of Algorithms and Data Structures).

Так, расстояние Хэмминга между векторами 00111 и 10101 равно 2 (красным отмечены различающиеся биты). В дальнейшем метрика была обобщена на q-ичные последовательности: для пары строк «выборы» и «забора» расстояние Хэмминга равно трём.

В общем виде расстояние Хэмминга \mathbf{d_H} для объектов \mathbf{X_i} и \mathbf{X_j} размерности \mathbf{p} задаётся функцией:

d_H (X_i ,X_j ) = \sum\limits_{s = 1}^p {\left| {x_i^{(s)} - x_j^{(s)} } \right|}

Расстояние Хэмминга обладает свойствами метрики, удовлетворяя следующим условиям:

  1. \mathbf{d_H (X_i ,X_j ) \ge 0}
  2. \mathbf{d_H (X_i ,X_i ) = 0}
  3. \mathbf{d_H (X_i ,X_j ) = d_H (X_j ,X_i )}
  4. \mathbf{d_H (X_i ,X_k ) \le d_H (X_i ,X_j ) + d_H (X_j ,X_k )}

Расстояние Хэмминга в биоинформатике и геномике

Для нуклеиновых кислот (ДНК и РНК) возможность гибридизации двух полинуклеотидных цепей с образованием вторичной структуры - двойной спирали - зависит от степени комплементарности нуклеотидных последовательностей обеих цепей. При увеличении расстояния Хэмминга количество водородных связей, образованных комплементарными парами оснований уменьшается и, соответственно, уменьшается стабильность ввойной цепи. Начиная с некоторого граничного расстояния Хэмминга гибридизация становится невозможной.

При эволюционном расхождении гомологичных ДНК-последовательностей расстояние Хэмминга является мерой, по которой можно судить о времени, прошедшем с момента расхождения гомологов, например, о длительности эволюционного отрезка, разделяющего гены-гомологи и ген-предшественник.


Литература

  • Richard W. Hamming. Error-detecting and error-correcting codes, Bell System Technical Journal 29(2):147-160, 1950.
  • Ричард Блейхут. Теория и практика кодов, контролирующих ошибки. М., «Мир», 1986

Ссылки

 
Начальная страница  » 
А Б В Г Д Е Ж З И Й К Л М Н О П Р С Т У Ф Х Ц Ч Ш Щ Ы Э Ю Я
A B C D E F G H I J K L M N O P Q R S T U V W X Y Z
0 1 2 3 4 5 6 7 8 9 Home