Відстань Хеммінга - це
Відстань Хеммінга - міра (точніше, метрика) відмінності об'єктів однакової розмірності.
Спочатку метрика була сформульована Річардом Хеммінга під час його роботи в 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
Дивитися що таке "Відстань Хеммінга" в інших словниках:
відстань Хеммінга - хеммінговское відстань Відстань d (u, v) між двома кодовими последовательноаямі u і v однакової довжини, яка дорівнює кількості символів, в яких вони відрізняються. Блоковий код з мінімальним хеммінговскім відстанню d дозволяє виявити (d 1) і ... ... Довідник технічного перекладача
Лінійний код - В області математики і теорії інформації лінійний код це важливий тип блокового коду, що використовується в схемах визначення і корекції помилок. Лінійні коди, в порівнянні з іншими кодами, дозволяють реалізовувати більш ефективні алгоритми ... ... Вікіпедія
Породжує матриця - У галузі математики та теорії інформації лінійний код це важливий тип блокового коду, що використовується в схемах визначення і корекції помилок. Лінійні коди, в порівнянні з іншими кодами, дозволяють реалізовувати більш ефективні алгоритми ... ... Вікіпедія
Перевірочна матриця - У галузі математики та теорії інформації лінійний код це важливий тип блокового коду, що використовується в схемах визначення і корекції помилок. Лінійні коди, в порівнянні з іншими кодами, дозволяють реалізовувати більш ефективні алгоритми ... ... Вікіпедія
Виявлення і виправлення помилок - Виявлення помилок в техніці зв'язку дія, спрямована на контроль цілісності даних при записі / відтворенні інформації або при її передачі по лініях зв'язку. Виправлення помилок (корекція помилок) процедура відновлення ... ... Вікіпедія
Надмірне кодування - Виявлення помилок в техніці зв'язку дія, спрямована на контроль цілісності даних при записі / відтворенні інформації або при її передачі по лініях зв'язку. Виправлення помилок (корекція помилок) процедура відновлення інформації після ... ... Вікіпедія
Надмірність даних - Виявлення помилок в техніці зв'язку дія, спрямована на контроль цілісності даних при записі / відтворенні інформації або при її передачі по лініях зв'язку. Виправлення помилок (корекція помилок) процедура відновлення інформації після ... ... Вікіпедія
Виправляють помилки Коди - Виявлення помилок в техніці зв'язку дія, спрямована на контроль цілісності даних при записі / відтворенні інформації або при її передачі по лініях зв'язку. Виправлення помилок (корекція помилок) процедура відновлення інформації після ... ... Вікіпедія
Коди, що виправляють помилки - Виявлення помилок в техніці зв'язку дія, спрямована на контроль цілісності даних при записі / відтворенні інформації або при її передачі по лініях зв'язку. Виправлення помилок (корекція помилок) процедура відновлення інформації після ... ... Вікіпедія