ФЭНДОМ


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

Первоначально метрика была сформулирована Ричардом Хэммингом во время его работы в 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 {\rm sign}{\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

Ссылки Править


Обнаружено использование расширения AdBlock.


Викия — это свободный ресурс, который существует и развивается за счёт рекламы. Для блокирующих рекламу пользователей мы предоставляем модифицированную версию сайта.

Викия не будет доступна для последующих модификаций. Если вы желаете продолжать работать со страницей, то, пожалуйста, отключите расширение для блокировки рекламы.