Comparación de Gráficos (Lista de Adjecencia/Matriz)

La teoría de grafos no es mi área más fuerte en matemáticas y deseo implementarla, por lo que cuanto más simple sea la descripción, mejor. Gracias por cualquier respuesta de antemano.

El problema: deseo comparar moléculas químicas o grupos específicamente reactivos en una molécula química. Estas moléculas se almacenan como listas de adyacencia de nodos y bordes, sin embargo, el orden de los nodos es arbitrario, es decir, debo usar la información de conectividad real en sí. Obviamente, los nodos también contienen un tipo de átomo, por ejemplo, hidrógeno, carbono, etc., y los bordes pueden ser enlaces simples, enlaces dobles, etc., por lo que efectivamente también hay "información de tipo". (Escribir una matriz de adyacencia no funciona ya que los nodos se pueden numerar de manera diferente en los dos grupos).

Entonces, ¿cómo puedo comparar dos grupos/gráficos que están definidos solo por su lista de adyacencia?

Intenté buscar algoritmos, pero las preguntas típicas son "¿cuál es la ruta más corta de A a B?" o "cómo visitar todos los nodos", o tal vez estaba usando los términos de búsqueda incorrectos... Puedo (con un montón de intrincados código) hacer una comparación de fuerza bruta en un átomo, pero ¿cómo continuaría? Obviamente, usar la fuerza bruta es muy costoso... (aunque potencialmente manejable en mi caso...)

Editar: siguiendo los comentarios y buscando un poco, creo que esto sería identificar un subgráfico inducido por borde y vértice (nodo). - Es decir, cuál es el algoritmo asociado o un puntero en la literatura específica. (Cuanto más simple, mejor)

Tal vez no lo entiendo bien, pero me parece que necesita probar estas moléculas en busca de isomorfismo. ¿Esta pregunta es de naturaleza teórica o necesita hacer esto en la práctica?
@Jernej Eso es todo, y desafortunadamente es algo que quiero implementar. (Aunque la optimización no es tan importante para mí, hacer que funcione es lo primero).
El software de isomorfismo ya está disponible en forma de bibliotecas (nauty, bliss) y, si no le importa la interfaz, le recomiendo que use Sage. Implementar un buen comprobador de isomorfismos desde cero puede ser una exageración
Sage no es una opción, ya que no necesito un paquete binario, pero las bibliotecas pueden ser una opción. Tendré que leerlas y verificarlas. Gracias.
@DetlevCM: le sugiero encarecidamente que use una biblioteca química existente para hacer isomorfismo de moléculas. InChI, SMILES canónicos, etc. Dependiendo de su idioma, pueden ser Java (CDK o SMSD), C (OpenBABEL), python (Cinfony), por ejemplo. Si realmente desea implementar uno usted mismo, ¿podría ser mejor como una pregunta de algoritmo sobre el desbordamiento de pila?
@gilleain Es más fácil decirlo que hacerlo: el objetivo específico es escribir "entradas de biblioteca" para un software llamado RMG ( github.com/ReactionMechanismGenerator ), utilizando la entrada definida por el usuario. Todo lo que leo e imprimo es una matriz de adyacencia, por lo que no hay "química explícita" en lo que hago. Supongo que uno puede traducir; por otra parte, tengo la costumbre de escribir cosas desde cero siempre que sea posible. Podría ser una pregunta de StackOverflow, pero hasta ahora ni siquiera puedo entender la lógica de un algoritmo (aunque yo no sabía qué buscar antes...) - y esa es una pregunta de matemáticas.
@gilleain Por otra parte, tal vez el truco sea pasar de una matriz de adyacencia a algo como SMILES, hacer la comparación y luego volver a convertir...
Entendido. Bueno, si realmente quieres hacer bricolaje, entonces el algoritmo más fácil de implementar es probablemente VF2. Lo primero que puedo encontrar es esto ( jcheminf.com/content/4/1/13 ) pero hay muchas otras cosas por ahí.
La lógica de los algoritmos de isomorfismo es, en principio, tan simple como la coincidencia de cadenas: siga intentando hacer coincidir la siguiente parte hasta que se le acabe. Por supuesto, para los gráficos, tiene que hacer algo más que la coincidencia de izquierda a derecha, por lo que debe probar todos los puntos de inicio. En última instancia, está generando un mapeo átomo-átomo, y si existe, los fragmentos son isomorfos.
@gilleain Llegué a hacer coincidir átomos y enlaces: el problema que me desconcierta es el tema de la ramificación y cómo proceder después de hacer coincidir un átomo inicial (la ramificación es "muy química"). Revisaré el artículo, gracias . Editar: hmm, la página 2 se ve EXACTAMENTE como lo que necesito, parece un muy buen artículo. -> Debe leer :)
@gilleain ¿Hay alguna posibilidad de que pueda combinar sus comentarios en una respuesta? - Creo que efectivamente has dado en el clavo. El documento que sugirió es exactamente lo que necesito, y sería un buen recurso para cualquier otra persona que busque "matemáticas para química" en el futuro. (Me daría una respuesta que podría aceptar y ser útil para otros). Comprender e implementar es otro problema, pero eso es algo que yo debo resolver.

Respuestas (1)

Representación

Desde la perspectiva de la teoría de grafos, las sustancias químicas pueden describirse de manera útil como gráficos simples con vértices y bordes coloreados. Los átomos generalmente se representan como vértices con el elemento como una etiqueta asociada. Los enlaces se pueden considerar como de múltiples aristas, pero los colores de las aristas son más habituales ya que hay un pequeño conjunto de órdenes de enlace (sencillo, doble, triple), aunque para completar podríamos incluir cuádruple y quíntuple, u otros tipos de enlace como hidrógeno, dativo , interacciones Cp-Metal, etc.

Problemas teóricos

La química y la teoría de grafos tienen una historia larga y fructífera, pero los problemas particulares sobre los que pregunta son el isomorfismo de grafos (GI) y/o el isomorfismo de subgrafos. Existe mucha información sobre GI como un problema, pero el enfoque para los informáticos y los matemáticos tiende a centrarse en la parte más difícil del problema. Por ejemplo, las noticias recientes sobre el resultado de László Babai sobre la complejidad de GI son fascinantes pero algo irrelevantes para la química.

Los productos químicos suelen ser gráficos bastante "simples", en algunos sentidos; a menudo tienen vértices de grado inferior a 5, ciertamente son escasos, la mayoría de ellos son planos o casi. Esto los hace bastante manejables para GI y algoritmos similares. Por otro lado, pueden ser bastante grandes: fullerenos, azúcares grandes, proteínas.

Algoritmos

Entonces, GI es más simple de describir que el problema del isomorfismo del subgrafo. Para comprobar que dos grafos son isomorfos, basta con generar una representación canónica de ambos grafos y compararlos. Por ejemplo InChI o canonical-SMILES, o signatures . Para obtener realmente el mapeo entre átomos, es necesario hacer algo como isomorfismo de subgrafo con todo el gráfico de consulta.

Entonces, una forma de obtener el mapeo entre un (sub) gráfico y otro gráfico es buscar repetidamente a través de ambos gráficos, construyendo el mapeo en el camino. Durante la búsqueda, se queda sin vértices en el gráfico de consulta (un isomorfismo) o llega a un estado en el que no se pueden realizar más asignaciones. En cuyo caso, el mapeo se reinicia en una 'raíz' diferente en la consulta, para tantos vértices en la consulta original.

Este proceso se describe en varios lugares, por ejemplo, este artículo compara dos algoritmos de búsqueda de subestructura. Por supuesto, existen algoritmos más sofisticados o especializados, pero VF2 es bastante bueno y bastante simple de implementar. Además, hay mucha literatura en el área de la "minería de grafos" que trata sobre el isomorfismo de subgrafos.

Comparación de Gráficos (Lista de Adjecencia/Matriz)
RespuestasAquíPolítica de privacidad1y, 0v