Відстань Геммінга (англ. Hamming distance) — число позицій, у яких відповідні цифри двох двійкових слів однакової довжини різні. У загальнішому випадку відстань Геммінга застосовується для рядків однакової довжини будь-яких абеток, що складаються з q символів, і служить метрикою відмінності (функцією, що визначає відстань в метричному просторі) об'єктів однакової вимірності.
Іншими словами, відстань Геммінга вимірює мінімальну кількість замін, необхідних для зміни одного рядка в інший, або мінімальну кількість помилок, які могли перетворити одну стрічку в іншу. У більш загальному контексті відстань Хеммінга є однією з метрик рядків[en] для вимірювання відстані редагування[en] між двома послідовностями.
Спочатку метрика була сформульована Річардом Геммінгом під час його роботи в Bell Labs для визначення міри відмінності між кодовими комбінаціями (двійковими векторами) у векторному просторі кодових послідовностей, в цьому випадку відстанню Геммінга між двома двійковими послідовностями (векторами) і довжини називається кількість позицій, в яких вони різні — в такому формулюванні відстань Геммінга увійшла в словник алгоритмів і структур даних[en] національного інституту стандартів і технологій США.
Приклади Редагувати
Властивості Редагувати
Відстань Геммінга має властивості метрики, задовольняючи таким умовам:
Відстань Геммінга в біоінформатиці та геноміці Редагувати
Для нуклеїнових кислот (ДНК та РНК) можливість гібридизації двох полінуклеотидних ланцюгів з утворенням вторинної структури — подвійної спіралі — залежить від ступеня комплементарності нуклеотидних послідовностей обох ланцюгів. При збільшенні відстані Геммінга кількість водневих зв'язків, утворених комплементарними парами основ зменшується і, відповідно, зменшується стабільність подвійного ланцюга. Починаючи з деякої граничної відстані Геммінга гібридизація стає неможливою.
При еволюційному розходженні гомологічних ДНК-послідовностей відстань Геммінга є мірою, за якою можна судити про час, що пройшов з моменту розбіжності гомологів, наприклад, про тривалість еволюційного відрізку, що розділяє гени-гомолог і ген-попередник.
Див. також Редагувати
Примітки Редагувати
- 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 [ 2 березня 2009 у Wayback Machine.]).
Література Редагувати
- Блейхут Р. Теория и практика кодов, контролирующих ошибки = Theory and Practice of Error Control Codes. — М.: Мир, 1986. — 576 с.
- Hamming, Richard W. (1950). . Bell System Technical Journal 29 (2): 147–160. MR 0035935. Архів оригіналу за 25 травня 2006. Процитовано 25 листопада 2012..