Расстояние Хэмминга
Расстояние Хэмминга — число позиций, в которых соответствующие цифры двух двоичных слов одинаковой длины различны[1]. В более общем случае расстояние Хэмминга применяется для строк одинаковой длины любых q-ичных алфавитов и служит метрикой различия (функцией, определяющей расстояние в метрическом пространстве) объектов одинаковой размерности.
Первоначально метрика была сформулирована Ричардом Хэммингом во время его работы в Bell Labs для определения меры различия между кодовыми комбинациями (двоичными векторами) в векторном пространстве кодовых последовательностей, в этом случае расстоянием Хэмминга <math>d(x, y)</math> между двумя двоичными последовательностями (векторами) <math>x</math> и <math>y</math> длины <math>n</math> называется число позиций, в которых они различны — в такой формулировке расстояние Хэмминга вошло в словарь алгоритмов и структур данных национального института стандартов и технологий США (англ. NIST Dictionary of Algorithms and Data Structures).
Примеры
- <math>d(10{\color{Blue}1}1{\color{Blue}1}01, 10{\color{Red}0}1{\color{Red}0}01)=2</math>
- <math>d(2{\color{Blue}17}3{\color{Blue}8}96, 2{\color{Red}23}3{\color{Red}7}96)=3</math>
- <math>d({\color{Blue}t}o{\color{Blue}n}e{\color{Blue}d}, {\color{Red}r}o{\color{Red}s}e{\color{Red}s})=3</math>
Свойства
Расстояние Хэмминга обладает свойствами метрики, удовлетворяя следующим условиям:
- <math>~d(x,y) \ge 0</math>
- <math>~d(x,x)=0</math>
- <math>~d(x,y)=d(y,x)</math>
- <math>~d(x,z) \le d(x,y) + d(y,z)</math>
Расстояние Хэмминга в биоинформатике и геномике
Для нуклеиновых кислот (ДНК и РНК) возможность гибридизации двух полинуклеотидных цепей с образованием вторичной структуры - двойной спирали - зависит от степени комплементарности нуклеотидных последовательностей обеих цепей. При увеличении расстояния Хэмминга количество водородных связей, образованных комплементарными парами оснований уменьшается и, соответственно, уменьшается стабильность двойной цепи. Начиная с некоторого граничного расстояния Хэмминга гибридизация становится невозможной.
При эволюционном расхождении гомологичных ДНК-последовательностей расстояние Хэмминга является мерой, по которой можно судить о времени, прошедшем с момента расхождения гомологов, например, о длительности эволюционного отрезка, разделяющего гены-гомологи и ген-предшественник.
См. также
Примечания
- ↑ Hamming distance: The number of digit positions in which the corresponding digits of two binary words of the same length are different (Federal Standard 1037C).
Литература
- Блейхут Р. Теория и практика кодов, контролирующих ошибки = Theory and Practice of Error Control Codes. — М.: Мир, 1986. — 576 с.
| Информатика | Это незавершённая статья по информатике. Вы можете помочь проекту, исправив и дополнив её. |
af:Hammingafstand bg:Разстояние на Хеминг 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 no:Hamming-avstand pl:Odległość Hamminga pt:Distância de Hamming ro:Distanţă Hamming vi:Khoảng cách Hamming zh:汉明距离
Если вам нравится SbUP.com Сайт, вы можете поддержать его - BTC: bc1qppjcl3c2cyjazy6lepmrv3fh6ke9mxs7zpfky0 , TRC20 и ещё....
