En Matemáticas, Ciencias de la computación y teoría de grafos, una matriz de distancias es una Matriz cuadrada cuyos elementos representan las Distancias entre los puntos, tomados por pares, de un conjunto. Dependiendo de su aplicación, la distancia usada para definir esta matriz puede o no ser una métrica. Se trata, por lo tanto, de una matriz simétrica de tamaño (dado un conjunto de puntos en el Espacio euclídeo) conteniendo números reales no negativos como elementos. El número N de pares de puntos, (N-1)/2, es el número de elementos independientes en la matriz de distancias.
Las matrices de distancias están relacionadas con las matrices de adyacencia, diferenciándose en que las últimas sólo informan sobre qué vértices están conectados, pero no especifican costes o distancias entre los vértices; además, cada elemento de una matriz de distancias es más pequeño cuanto más cercanos se encuentren los puntos, mientras que vértices cercanos (conectados) producen elementos mayores en una matriz de adyacencia.
Matriz de distancias no métricas En general, una matriz de distancias es una matriz de adyacencia ponderada de alguna gráfica. En una red, una gráfica dirigida con pesos asignados en sus aristas, la distancia entre dos nodos de la red se puede definir como el mínimo de las sumas de los pesos en los caminos más cortos que unen los dos nodos. Esta función de distancia, aunque bien definida, no es una métrica. No es necesario que haya restricciones en los pesos, aparte de la necesidad de poder combinarlos y compararlos, por lo que los pesos negativos se utilizan en algunas aplicaciones. Dado que los caminos están dirigidos, la simetría no se puede garantizar, y si los ciclos existen, la matriz de distancia puede no ser hueca.
Una formulación algebraica de lo anterior se puede obtener mediante el álgebra min-plus. La multiplicación de la matriz en este sistema se define de la siguiente manera: Dadas dos matrices de tamaño , y , su producto de distancia se define como una matriz de tamaño tal que
Tenga en cuenta que los elementos fuera de la diagonal que no están conectados directamente tendrán que ajustarse al infinito o un valor grande adecuado para que las operaciones min-plus funcionen correctamente. Un cero en estas ubicaciones será interpretado incorrectamente como una arista sin distancia, costo, etc.
Si es una matriz de tamaño que contiene los pesos de las aristas de una gráfica, entonces (usando este producto de distancia) da las distancias entre vértices usando caminos de longitud ce a lo más aristas, y es la matriz de distancias de la gráfica.
Una gráfica arbitraria sobre vértices puede ser modelada como una gráfica completa ponderada sobre vértices, asignando un peso de uno a cada arista de la gráfica completa que corresponde a una arista de y cero a todos las aristas restantes. Para esta gráfica completa, es la matriz de adyacencia de . La matriz de distancias de se puede calcular a partir de como se indica anteriormente, sin embargo, calculada por la multiplicación matricial habitual solo codifica el número de caminos entre dos vértices de longitud exactamente .
Matriz de distancias métricas En muchas aplicaciones, el valor de una matriz de distancias está en como puede codificar los axiomas métricos y en como se presta al uso de técnicas de álgebra lineal. Es decir, si con es una matriz de distancias con una distancia métrica, entonces
Las entradas en la diagonal son todas cero, i.e. para todo . Todas las entradas fuera de la diagonal son positivas ( si ), es decir, es una matriz no-negativa. La matriz es una matriz simétrica () y Para cualquier y , para todo (desigualdad del triángulo).
Una matriz de distancias métricas que puede ser encajada en espacio Euclidiano se llama una matriz de distancias Euclidiana.
Otro ejemplo común de una matriz de distancias métricas surge en la teoría de códigos cuando en un bloque de códigos los elementos son cadenas de longitud fija sobre un alfabeto y la distancia entre ellos está dada por la distancia Hamming. La entrada más pequeña distinta de cero, mide la capacidad de corrección y detección de errores del código.
Matriz de distancia aditiva Una matriz de distancia aditiva es un tipo especial de matriz utilizada en bioinformática para construir un árbol filogenético. Si es el ancestro común más antiguo entre dos especies y , esperamos que . Aquí es de donde viene la métrica aditiva. Una matriz de distancia para un conjunto de especies se dice que es aditiva si y sólo si existe una filogenia para tal que:
Cada arista en se asocia con un peso positivo , Para todo , es igual a la suma de los pesos a lo largo del camino de a en .
En este caso, se denomina una matriz aditiva y se denomina un árbol aditivo. A continuación podemos ver un ejemplo de una matriz de distancia aditiva y su árbol correspondiente: centro|miniaturadeimagen|512x512px|Matriz de distancia aditiva (izquierda) y su árbol filogenético (derecha).
Matriz de distancias ultramétricas La matriz de distancia ultramétrica se define como una matriz aditiva que modela el reloj molecular constante. Es usada para construir un árbol filogenético. Una matriz se dice que es ultramétrica si existe un árbol tal que:
es igual a la suma de los pesos de las aristas de una trayectoria en de a . Una raíz del árbol se puede identificar con la misma distancia a todas las hojas.
El siguiente es un ejemplo de una matriz de distancia ultramétrica con su correspondiente árbol. centro|miniaturadeimagen|463x463px|Ejemplo de un árbol ultramétrico de filogenética
Bioinformática La matriz de distancia es ampliamente utilizada en el campo de la bioinformática, y está presente en varios métodos, algoritmos y programas. Las matrices de distancia se utilizan para representar estructuras de proteínas de manera independiente de las coordenadas, así como las distancias de emparejamiento entre dos secuencias en el espacio de secuencia. Se utilizan en la alineación estructural y secuencial, y para la determinación de estructuras de proteínas a partir de la cristalografía de rayos X o resonancia magnética nuclear.
A veces es más conveniente expresar los datos como una matriz de similitud.
También se utiliza para definir la correlación de la distancia.
Alineación de Secuencias Una alineación de dos secuencias se forma mediante la inserción de espacios en ubicaciones arbitrarias a lo largo de las secuencias de modo que terminan con la misma longitud y no hay dos espacios en la misma posición de las dos secuencias aumentadas. Uno de los principales métodos para la alineación de secuencias es la programación dinámica. El método se utiliza para llenar la matriz de distancia y luego obtener la alineación. En el uso típico, para la alineación de secuencias se utiliza una matriz para asignar puntuaciones a las coincidencias de aminoácidos o desajustes, y una penalización por hueco por emparejar un aminoácido en una secuencia con un hueco en la otra.
Alineamiento Global El algoritmo de Needleman-Wunsch utilizado para calcular la alineación global utiliza programación dinámica para obtener la matriz de distancia.
Alineamiento Local El algoritmo de Smith-Waterman también está basado en programación dinámica que consiste también en obtener la matriz de distancias y luego obtener la alineación local.
Alineación de Secuencias Múltiples La alineación múltiple de secuencias es una extensión de la alineación por pares para alinear varias secuencias a la vez. Los diferentes métodos de ASM se basan en la misma idea de la matriz de distancia que las alineaciones globales y locales.
Método de Estrella Central. Este método define una secuencia central que minimiza la distancia entre la secuencia y cualquier otra secuencia . Luego genera una alineación múltiple para el conjunto de secuencias de modo que para cada la distancia de alineación es la alineación de emparejamiento óptima. Este método tiene la característica de que la alineación calculada para , cuya distancia de suma de pares es como máximo el doble de la alineación múltiple óptima. Método de alineación progresiva. Es un método heurístico para crear ASM, donde primero alinea las dos secuencias más relacionadas, y progresivamente alinea las siguientes dos secuencias más relacionadas hasta que todas las secuencias se alinean.
Hay otros métodos que tienen su propio programa debido a su popularidad:
Clustal MUSCLE MAFFT MANGO
MAFFT La Alineación Múltiple usando la Transformada Rápida de Fourier (MAFFT) es un programa con un algoritmo basado en la alineación progresiva, y ofrece varias estrategias de alineación múltiple. Primero, MAFFT construye una matriz de distancia basada en el número de 6 tuplas compartidas. Segundo, construye el árbol de guía basado en la matriz anterior. En tercer lugar, agrupa las secuencias con la ayuda de la transformada rápida de Fourier y comienza la alineación. Basado en la nueva alineación, reconstruye el árbol de guía y se alinea de nuevo.
Análisis Filogenético Para realizar el análisis filogenético, el primer paso es reconstruir el árbol filogenético: dada una colección de especies, el problema es reconstruir o inferir las relaciones ancestrales entre las especies, es decir, el árbol filogenético entre las especies. Los métodos de matriz de distancia realizan esta actividad.
Métodos de matriz de distancia Los métodos de matrices de distancia del análisis filogenético se basan explícitamente en una medida de "distancia genética" entre las secuencias que se clasifican, y por lo tanto requieren múltiples secuencias como entrada. Los métodos de distancia intentan construir una matriz todo-a-todo a partir del conjunto de consultas de secuencia que describe la distancia entre cada par de secuencias. A partir de esto se construye un árbol filogenético que coloca secuencias estrechamente relacionadas bajo el mismo nodo interior y cuyas longitudes de rama reproducen estrechamente las distancias observadas entre secuencias. Los métodos de matrices de distancia pueden producir árboles enraizados o no enraizados, dependiendo del algoritmo utilizado para calcularlos. Dada la especie , la entrada es una matriz de distancia de tamaño donde es la distancia de mutación entre las especies y . El objetivo es producir un árbol de grado 3 que sea consistente con la matriz de distancia.
Se utilizan con frecuencia como base para tipos progresivos e iterativos de alineamiento múltiple de secuencias. La principal desventaja de los métodos de matrices de distancia es su incapacidad para usar eficientemente la información sobre regiones locales de alta variación que aparecen a través de múltiples subárboles. A pesar de los problemas potenciales, los métodos de distancia son extremadamente rápidos, y a menudo producen una estimación razonable de la filogenia. También tienen ciertos beneficios sobre los métodos que usan caracteres directamente. Cabe destacar que los métodos de distancia permiten el uso de datos que no pueden convertirse fácilmente en datos de caracteres, como los ensayos de hibridación de ADN-ADN.
Los siguientes son métodos basados en la distancia para la reconstrucción filogenética:
Reconstrucción de árboles aditivos MGPMA Unión de vecinos Fitch-Margoliash
Reconstrucción de Árboles Aditivos La reconstrucción del árbol aditivo se basa en matrices de distancia aditivas y ultramétricas. Estas matrices tienen una característica especial:
Considere una matriz aditiva . Para cualquier tres especies ,,, el árbol correspondiente es único. Cada matriz de distancia ultramétrica es una matriz aditiva. Podemos observar esta propiedad para el árbol de abajo, que consiste en la especie ,,. centro