Distanța Hamming este o măsură (mai exact o metrică) a diferențelor în obiecte de aceeași dimensiune.
Inițial metric formulată Richard Hamming în timpul funcționării sale, în laboratoarele Bell pentru determinarea măsurilor de diferențe între codewords (vectori binari) într-o secvență de cod spațiu vectorial, în care caz distanța Hamming dintre două secvențe binare (vectori) și lungimea este numărul de poziții în care acestea sunt diferite - în această formulare, distanța Hamming a intrat în dicționarul de algoritmi și structuri ale Institutului National de Standarde din SUA de date (eng NIST Dicționar de algoritmi si structuri de date.).
Astfel, distanța Hamming între vectorii 0 01 1 1 și 1 01 0 1 este 2 (marcajul roșu reprezintă biții diferiți). În cele ce urmează, metrica a fost generalizată în secvențe q: pentru o pereche de rânduri "select" și "a-b a", distanța Hamming este de trei.
În general, distanța Hamming pentru obiecte și dimensiuni este dată de funcția:
Distanța Hamming are proprietăți metrice, care îndeplinesc următoarele condiții:
Distanța Hamming în bioinformatică și genomică Edit href = Edit
Pentru acizii nucleici (ADN și ARN) hibridarea posibilitatea de două lanțuri de polinucleotide pentru a forma o structură secundară - un dublu helix - depinde de gradul de complementaritate a secvențelor de nucleotide ale ambelor lanțuri. Odată cu creșterea distanței Hamming, numărul legăturilor de hidrogen. formate de perechi complementare de bază scade și, în consecință, stabilitatea lanțului dublu scade. Începând cu o anumită distanță de la Hamming, hibridizarea devine imposibilă.
Dacă divergența evolutiv al secvențelor de ADN omoloage este o măsură a distanței Hamming, prin care este posibil să se judece timpul scurs din diferențele de timp omologi, de exemplu, durata intervalului de evoluție care separă genele și omologie genei precursoare.
Metode similare Edit
Editarea literaturii
- Richard W. Hamming. Coduri de detectare a erorilor și de corectare a erorilor, Bell System Technical Journal 29 (2): 147-160, 1950.
- Richard Bleyhut. Teoria și practica codurilor care controlează erorile. M. Mir, 1986