Відстань Геммінга

Матеріал з Вікіпедії — вільної енциклопедії.
Перейти до: навігація, пошук

Відстань Геммінга — число позицій, у яких відповідні цифри двох двійкових слів однакової довжини різні [1]. У загальнішому випадку відстань Геммінга застосовується для рядків однакової довжини будь-яких q-кових алфавітів і служить метрикою відмінності (функцією, що визначає відстань в метричному просторі) об'єктів однакової розмірності.

Спочатку метрика була сформульована Річардом Геммінгом під час його роботи в Bell Labs для визначення міри відмінності між кодовими комбінаціями (двійковими векторами) у векторному просторі кодових послідовностей, в цьому випадку відстанню Геммінга d(x,y) між двома двійковими послідовностями (векторами) x і  y довжини  n називається число позицій, в яких вони різні — в такому формулюванні відстань Геммінга увійшло в словник алгоритмів і структур даних національного інституту стандартів і технологій США (англ. NIST Dictionary of Algorithms and Data Structures).

Приклади[ред.ред. код]

  • d(10{\color{Blue}1}1{\color{Blue}1}01, 10{\color{Red}0}1{\color{Red}0}01)=2
  • d(2{\color{Blue}17}3{\color{Blue}8}96, 2{\color{Red}23}3{\color{Red}7}96)=3
  • d({\color{Blue}t}o{\color{Blue}n}e{\color{Blue}d}, {\color{Red}r}o{\color{Red}s}e{\color{Red}s})=3

Властивості[ред.ред. код]

Відстань Геммінга має властивості метрики, задовольняючи таким умовам:

  • ~d(x,y) \ge 0
  • ~d(x,x)=0
  • ~d(x,y)=d(y,x)
  • ~d(x,z) \le d(x,y) + d(y,z)

Відстань Геммінга в біоінформатиці та геноміці[ред.ред. код]

Для нуклеїнових кислот (ДНК та РНК) можливість гібридизації двох полінуклеотидних ланцюгів з утворенням вторинної структури — подвійної спіралі — залежить від ступеня комплементарності нуклеотидних послідовностей обох ланцюгів. При збільшенні відстані Геммінга кількість водневих зв'язків, утворених комплементарними парами основ зменшується і, відповідно, зменшується стабільність подвійного ланцюга. Починаючи з деякої граничної відстані Геммінга гібридизація стає неможливою.

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

Див. також[ред.ред. код]

Примітки[ред.ред. код]

  1. 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 ).

Література[ред.ред. код]