Відстань Хеммінга - міра (точніше, метрика) відмінності об'єктів однакової розмірності.
Спочатку метрика була сформульована Річардом Хеммінга під час його роботи в Bell Labs для визначення міри відмінності між кодовими комбінаціями (двійковими векторами) у векторному просторі кодових послідовностей, в цьому випадку відстанню Хеммінга між двома двійковими послідовностями (векторами) і довжини називається число позицій, в яких вони різні - в такому формулюванні відстань Хеммінга увійшло в Словник алгоритмів і структур даних Національного Інституту Стандартів США (англ. NIST Dictionary of Algorithms and Data Structures).
Так, відстань Хеммінга між векторами 0 01 1 1 і 1 01 0 1 дорівнює 2 (червоним відзначені розрізняються біти). Надалі метрика була узагальнена на q-ічние послідовності: для пари рядків «ви бор и» та «за бор а» відстань Хеммінга дорівнює трьом.
У загальному вигляді відстань Хеммінга для об'єктів і розмірності задається функцією:
Відстань Хеммінга має властивості метрики, задовольняючи таким умовам:
Відстань Хеммінга в біоінформатики і геноміки Правити
Для нуклеїнових кислот (ДНК і РНК) можливість гібридизації двох полінуклеотидних ланцюгів з утворенням вторинної структури - подвійної спіралі - залежить від ступеня комплементарності нуклеотидних послідовностей обох ланцюгів. При збільшенні відстані Хеммінга кількість водневих зв'язків. утворених комплементарними парами основ зменшується і, відповідно, зменшується стабільність подвійного ланцюга. Починаючи з деякого граничного відстані Хеммінга гібридизація стає невозможной.дополнітельно сказано про це
При еволюційному розходженні гомологічних ДНК-послідовностей відстань Хеммінга є мірою, по якій можна судити про час, що пройшов з моменту розбіжності гомологів, наприклад, про тривалість еволюційного відрізка, що розділяє гени -гомологі і ген-попередник.
Споріднені методи Правити
література Правити
- Richard W. Hamming. Error-detecting and error-correcting codes, Bell System Technical Journal 29 (2): 147-160, 1950.
- Річард Блейхут. Теорія і практика кодів, контролюючих помилки. М. «Мир», 1986