math - filogenia - matriz de distancias euclidianas

Encontrar las coordenadas de los puntos de la matriz de distancia

Question

Tengo un conjunto de puntos (con coordenadas desconocidas) y la matriz de distancia. Necesito encontrar las coordenadas de estos puntos para trazarlos y mostrar la solución de mi algoritmo.

Puedo establecer uno de estos puntos en la coordenada (0,0) para simplificar y encontrar los otros. ¿Alguien puede decirme si es posible encontrar las coordenadas de los otros puntos, y si es así, cómo?

¡Gracias por adelantado!

EDITAR Olvidé decir que necesito las coordenadas solo en xy

Answer 1

Este es un problema de matemáticas. Para derivar la matriz de coordenadas X solo dada por su matriz de distancia.

Sin embargo, hay una solución eficiente para esto: escalamiento multidimensional, que hace un poco de álgebra lineal. En pocas palabras, requiere una matriz de distancia Euclidiana por pares D, y la salida es la coordenada Y estimada (tal vez rotada), que es una aproximación a X. Por razones de programación, simplemente use SciKit.manifold.MDS en Python.

Answer 2

Las respuestas basadas en ángulos son difíciles de implementar y no se pueden generalizar fácilmente a datos en dimensiones superiores. Un mejor enfoque es el mencionado en las respuestas de mi y WimC aquí : dada la matriz de distancia D(i, j) , defina

M(i, j) = 0.5*(D(1, j)^2 + D(i, 1)^2 - D(i, j)^2)

que debería ser una matriz positiva semidefinida con un rango igual a la dimensión euclidiana mínima k en la cual los puntos pueden ser incrustados. Las coordenadas de los puntos se pueden obtener a partir de los k vectores propios v(i) de M correspondientes a valores propios distintos de cero q(i) : coloque los vectores sqrt(q(i))*v(i) como columnas en un nxk matriz X ; entonces cada fila de X es un punto. En otras palabras, sqrt(q(i))*v(i) proporciona el componente i ésimo de todos los puntos.

Los valores propios y vectores propios de una matriz se pueden obtener fácilmente en la mayoría de los lenguajes de programación (por ejemplo, usando GSL en C / C ++, usando la función incorporada eig en Matlab, usando Numpy en Python, etc.)

Tenga en cuenta que este método particular siempre coloca el primer punto en el origen, pero cualquier rotación, reflexión o traducción de los puntos también satisfará la matriz de distancia original.

Answer 3

Paso 1, asigna arbitrariamente un punto P1 como (0,0).

Paso 2, asigna arbitrariamente un punto P2 a lo largo del eje x positivo. (0, Dp1p2)

Paso 3, encuentra un punto P3 tal que

Dp1p2 ~= Dp1p3+Dp2p3
Dp1p3 ~= Dp1p2+Dp2p3
Dp2p3 ~= Dp1p3+Dp1p2

y establecer ese punto en el dominio y "positivo" (si cumple con alguno de estos criterios, el punto debe colocarse en el eje P1P2).
Usa la ley del coseno para determinar la distancia:

cos (A) = (Dp1p2^2 + Dp1p3^2 - Dp2p3^2)/(2*Dp1p2* Dp1p3)
P3 = (Dp1p3 * cos (A), Dp1p3 * sin(A))

Ahora ha construido con éxito un espacio ortonormal y ha colocado tres puntos en ese espacio.

Paso 4: Para determinar todos los otros puntos, repita el paso 3, para darle una coordenada y tentativa. (Xn, Yn).
Compara la distancia {(Xn, Yn), (X3, Y3)} a Dp3pn en tu matriz. Si es idéntico, ha identificado con éxito la coordenada para el punto n. De lo contrario, el punto n está en (Xn, -Yn).

Tenga en cuenta que hay una alternativa al paso 4, pero es demasiada matemática para un sábado por la tarde

Answer 4

Si para los puntos p, qy r tienes pq, qr y rp en tu matriz, tienes un triángulo.

Donde sea que tengas un triángulo en tu matriz, puedes calcular una de las dos soluciones para ese triángulo (independientemente de una transformación euclidiana del triángulo en el plano). Es decir, para cada triángulo que calcula, su imagen especular también es un triángulo que satisface las restricciones de distancia en p, qy r. El hecho de que haya dos soluciones, incluso para un triángulo, conduce al problema de quiralidad: debe elegir la quiralidad (orientación) de cada triángulo, y no todas las opciones pueden conducir a una solución factible al problema.

Sin embargo, tengo algunas sugerencias. Si las entradas de números son pequeñas, considere usar el recocido simulado . Podría incorporar la quiralidad en el paso de recocido. Esto será lento para sistemas grandes, y puede no converger a una solución perfecta, pero para algunos problemas es lo mejor que puedes hacer.

La segunda sugerencia no le dará una solución perfecta, pero distribuirá el error: el método de mínimos cuadrados . En su caso, la función objetivo será el error entre las distancias en su matriz y las distancias reales entre sus puntos.