Distancia de hamming

Distancia de Hamming (distancia de código) - el número de posiciones en las que los caracteres correspondientes de dos palabras de la misma longitud son diferentes [1] . De manera más general, la distancia de Hamming se aplica a cadenas de la misma longitud de cualquier alfabeto q - ario y sirve como una métrica de diferencia (una función que determina la distancia en un espacio métrico ) de objetos de la misma dimensión.

La métrica fue formulada originalmente por Richard Hamming durante su tiempo en Bell Labs para definir una medida de la diferencia entre palabras clave ( vectores binarios ) en un espacio vectorial de palabras clave: en este caso, la distancia de Hamming entre dos secuencias binarias (vectores) y la longitud es el número de posiciones en las que son diferentes. En esta formulación, la distancia de Hamming se incluyó en el Diccionario NIST de algoritmos y estructuras de datos . La distancia de Hamming es un caso especial de la métrica de Minkowski (con una definición apropiada de resta): $d(x,y)$ $X$ $y$ $norte$

d_{ij}=\sum _{k=1}^{p}\left|x_{ik}-x_{jk}\right|

Dos palabras con una distancia de Hamming de 1 se llaman vecinas.

En algunos sistemas numéricos, como el código Gray , los enteros codificados que difieren en 1 tienen una distancia de Hamming de 1. Se dice que estos números son "adyacentes".

La codificación de vecinos es importante en el diseño de dispositivos lógicos donde se deben evitar carreras lógicas .

Ejemplos

$d(10{\color {Azul cielo}1}1{\color {Azul cielo}1}01,10{\color {Rojo}0}1{\color {Rojo}0}01)=2$
$d(2{\color {Azul cielo}17}3{\color {Azul cielo}8}96,2{\color {Rojo}23}3{\color {Rojo}7}96)=3$
$d(\mathrm {{\color {SkyBlue}t}o{\color {SkyBlue}n}e{\color {SkyBlue}d}} ,\mathrm {{\color {Red}r}o{\ color {Rojo}s}e{\color {Rojo}s}} )=3$

Propiedades

Un conjunto de palabras de igual longitud forman un espacio métrico , donde para cada par de elementos espaciales se define un número - la distancia de Hamming que satisface los axiomas de la métrica: ${\ estilo de visualización d (x, y)}$

$d(x,\;y)=0\Flecha izquierda-derecha x=y$ ( axioma de identidad ).
$d(x,\;y)=d(y,\;x)$ ( axioma de simetría ).
$d(x,\;z)\leqslant d(x,\;y)+d(y,\;z)$ ( axioma del triángulo o desigualdad del triángulo ).

De los axiomas se sigue que la distancia no es negativa, ya que $0=d(x,x)\leqslant d(x,y)+d(y,x)=2\cdot d(x,y)$ .
Si representamos la desigualdad triangular como $d(x,y)\leqslant d(x,z)+d(y,z)$ para todos y $x, y$ $z$

entonces el axioma de simetría se sigue del axioma de identidad y de la desigualdad triangular.

La distancia de Hamming es siempre:

d(x,\;y)\leqslant n,

donde es la longitud de las palabras en caracteres.

norte

Distancia de Hamming en bioinformática y genómica

Para los ácidos nucleicos ( ADN y ARN ), la posibilidad de hibridación de dos cadenas de polinucleótidos con la formación de una estructura secundaria -una doble hélice- depende del grado de complementariedad de las secuencias de nucleótidos de ambas cadenas. A medida que aumenta la distancia de Hamming, disminuye el número de enlaces de hidrógeno formados por pares de bases complementarias y, en consecuencia, disminuye la estabilidad de la doble cadena. A partir de cierta distancia límite de Hamming, la hibridación se vuelve imposible.

En la divergencia evolutiva de secuencias homólogas de ADN, la distancia de Hamming es una medida por la cual se puede juzgar el tiempo transcurrido desde la divergencia de homólogos, por ejemplo, la longitud del segmento evolutivo que separa genes homólogos y un gen precursor.

Véase también

Notas

↑ Distancia de Hamming: el número de posiciones de dígitos en las que los dígitos correspondientes de dos palabras binarias de la misma longitud son diferentes ( Estándar federal 1037C Archivado el 2 de marzo de 2009 en Wayback Machine ).

Literatura

Blahut R. Teoría y práctica de los códigos de control de errores. — M .: Mir , 1986. — 576 p.

Instrumentos de cuerda
Medidas de similitud de cadenas	Distancia de Damerau a Loewenstein distancia Levenstein distancia de hamming Similitud de Jaro-Winkler
Búsqueda de subcadena	Algoritmo de Boyer-Moore Algoritmo de Boyer-Moore-Horspool Algoritmo de Knuth-Morris-Pratt Algoritmo de Rabin-Karp función de prefijo Función Z Algoritmo Aho - Korasik
palíndromos	árbol palíndromo Algoritmo del administrador
Alineación de secuencia	Algoritmo de Needleman-Wunsha Algoritmo de Smith-Waterman
Estructuras de sufijos	Matriz de sufijos sufijo autómata árbol de sufijos árbol de prefijos
Otro	analizando La coincidencia de patrones Mayor subsecuencia común Mayor subcadena común