Generador de gráficos de fórmulas químicas

Un generador de gráficos químicos es un paquete de software para generar representaciones informáticas de estructuras químicas que se adhieren a ciertas condiciones de contorno. El desarrollo de dichos paquetes de software es un tema de investigación de la quimioinformática. Los generadores de gráficos químicos se utilizan en áreas como la generación de bibliotecas virtuales en el diseño de fármacos, en el diseño molecular con propiedades específicas, llamado QSAR/QSPR inverso, así como en el diseño de síntesis orgánica, retrosíntesis o en sistemas para la elucidación de estructuras asistida por computadora (CASE).. Los sistemas CASE nuevamente han recuperado el interés por la elucidación de estructuras desconocidas en la metabolómica computacional, un área actual de la biología computacional.

Historia

La generación de estructuras moleculares es una rama de los problemas de generación de grafos. Las estructuras moleculares son gráficos con restricciones químicas como valencias, multiplicidad de enlaces y fragmentos. Estos generadores son el núcleo de los sistemas CASE. En un generador, la fórmula molecular es la entrada básica. Si se obtienen fragmentos de los datos experimentales, también se pueden utilizar como entradas para acelerar la generación de estructuras. Los primeros generadores de estructuras fueron versiones de generadores de gráficos modificados con fines químicos. Uno de los primeros generadores de estructuras fue CONGEN, desarrollado originalmente para el proyecto DENDRAL, el primer proyecto de inteligencia artificial en química orgánica. DENDRAL fue desarrollado como parte del programa Mariner lanzado por la NASA para buscar vida en Marte.CONGEN se ocupó bien de las superposiciones en las subestructuras. Las superposiciones entre las subestructuras en lugar de los átomos se utilizaron como bloques de construcción. Para el caso de los estereoisómeros, se realizaron cálculos de grupos de simetría para la detección de duplicados.

Después de DENDRAL, se informó de otro método matemático, MASS, una herramienta para la síntesis matemática y el análisis de estructuras moleculares. Al igual que con CONGEN, el algoritmo MASS funcionó como un generador de matriz de adyacencia. Muchos generadores matemáticos son descendientes de métodos eficientes de ramificación y acotación del método de generación ordenada de Igor Faradjev y Ronald C. Read. Aunque sus informes son de la década de 1970, estos estudios siguen siendo las referencias fundamentales para los generadores de estructuras. En el método de generación ordenada, se realizan funciones específicas de verificación de orden en representantes de gráficos, como vectores. Por ejemplo, MOLGENrealiza una verificación de orden descendente mientras llena filas de matrices de adyacencia. Esta verificación de orden descendente se basa en una distribución de valencia de entrada. La literatura clasifica los generadores en dos tipos principales: montaje de estructura y reducción de estructura. La complejidad algorítmica y el tiempo de ejecución son los criterios utilizados para la comparación.

Montaje de estructura

El proceso de generación comienza con un conjunto de átomos de la fórmula molecular. En el ensamblaje de estructuras, los átomos se conectan combinatoriamente para considerar todas las extensiones posibles. Si se obtienen subestructuras a partir de datos experimentales, la generación comienza con estas subestructuras. Estas subestructuras proporcionan enlaces conocidos en la molécula. Hidetsugu Abe realizó uno de los primeros intentos en 1975 utilizando un generador de estructuras basado en el reconocimiento de patrones. El algoritmo constaba de dos pasos: primero, la predicción de la subestructura a partir de datos espectrales de baja resolución; en segundo lugar, el montaje de estas subestructuras en base a un conjunto de reglas de construcción. Hidetsugu Abe y los demás colaboradores publicaron el primer artículo sobre QUÍMICOS,que es una herramienta CASE que comprende varios métodos de generación de estructuras. El programa se basa en una biblioteca de fragmentos predefinidos que no se superponen. CHEMICS genera diferentes tipos de conjuntos de componentes clasificados de primario a terciario en función de la complejidad de los componentes. El conjunto primario contiene átomos, es decir, C, N, O y S, con su hibridación. Los conjuntos de componentes secundarios y terciarios se construyen capa por capa a partir de estos componentes primarios. Estos conjuntos de componentes se representan como vectores y se utilizan como bloques de construcción en el proceso.

Craig Shelley y Morton Munk hicieron contribuciones sustanciales, quienes publicaron una gran cantidad de artículos CASE en este campo. El primero de estos artículos informó sobre un generador de estructuras, ASSEMBLE.El algoritmo se considera uno de los primeros métodos de ensamblaje en el campo. Como su nombre lo indica, el algoritmo ensambla subestructuras con superposiciones para construir estructuras. ASSEMBLE supera la superposición al incluir una "etiqueta de átomo vecino". El generador es puramente matemático y no implica la interpretación de ningún dato espectral. Los datos espectrales se utilizan para la puntuación de la estructura y la información de la subestructura. Según la fórmula molecular, el generador forma enlaces entre pares de átomos y todas las extensiones se verifican con las restricciones dadas. Si el proceso se considera como un árbol, el primer nodo del árbol es un conjunto de átomos con subestructuras, si las proporcionan los datos espectrales. Al extender la molécula con un enlace, se construye una estructura intermedia. Cada estructura intermedia puede ser representada por un nodo en el árbol de generación. ASSEMBLE fue desarrollado con una interfaz fácil de usar para facilitar su uso. La segunda versión de ASSEMBLE se lanzó en 2000.Otro método de montaje es GÉNOVA. En comparación con ASSEMBLE y muchos otros generadores, GÉNOVA es un algoritmo basado en la búsqueda de subestructuras constructivas y ensambla diferentes subestructuras considerando también las superposiciones.

La eficiencia y exhaustividad de los generadores también están relacionadas con las estructuras de datos. A diferencia de los métodos anteriores, AEGIS era un generador de procesamiento de listas. En comparación con las matrices de adyacencia, los datos de lista requieren menos memoria. Como no se interpretaron datos espectrales en este sistema, el usuario necesitaba proporcionar subestructuras como entradas. Los generadores de estructuras también pueden variar según el tipo de datos utilizados, como HMBC, HSQC y otros datos de RMN. LUCY es un método de elucidación de estructuras de código abierto basado en los datos de HMBC de moléculas desconocidas,e implica un proceso exhaustivo de generación de estructura de 2 pasos donde primero se implementan todas las combinaciones de interpretaciones de señales HMBC en una matriz de conectividad, que luego se completa con un generador determinista que completa la información de enlace faltante. Esta plataforma podría generar estructuras con cualquier tamaño arbitrario de moléculas; sin embargo, las fórmulas moleculares con más de 30 átomos pesados ​​consumen demasiado tiempo para aplicaciones prácticas. Esta limitación destacó la necesidad de un nuevo sistema CASE. SENECA fue desarrollado para eliminar las deficiencias de LUCY.Para superar las limitaciones del enfoque exhaustivo, SENECA se desarrolló como un método estocástico para encontrar soluciones óptimas. Los sistemas comprenden dos métodos estocásticos: recocido simulado y algoritmos genéticos. Primero, se genera una estructura aleatoria; luego, se calcula su energía para evaluar la estructura y sus propiedades espectrales. Al transformar esta estructura en otra estructura, el proceso continúa hasta alcanzar la energía óptima. En la generación, esta transformación se basa en ecuaciones basadas en las reglas de Jean-Loup Faulon. LSD (Lógica para la Determinación de la Estructura)es una importante contribución de los científicos franceses. La herramienta utiliza información de datos espectrales como datos HMBC y COSY para generar todas las estructuras posibles. LSD es un generador de estructura de código abierto lanzado bajo la Licencia Pública General (GPL). Un conocido sistema CASE comercial, StrucEluc, también cuenta con un generador basado en RMN. Esta herramienta es de ACD Labs y, en particular, de uno de los desarrolladores de MASS, Mikhail Elyashberg. COCON es otro generador de estructuras basado en RMN, que se basa en conjuntos de datos teóricos para la generación de estructuras. Excepto J-HMBC y J-COSY, todos los tipos de RMN se pueden utilizar como entradas.

En 1994, Hu y Xu informaron sobre un generador de estructura basado en partición de enteros. La descomposición de la fórmula molecular en fragmentos, componentes y segmentos se realizó como una aplicación de partición de enteros. Estos fragmentos luego se usaron como bloques de construcción en el generador de estructuras. Este generador de estructuras era parte de un sistema CASE, ESESOC.

Jean-Loup Faulon informó sobre una serie de generadores estocásticos. El software, MOLSIG, se integró en este generador estocástico para etiquetado canónico y verificación de duplicados. Como para muchos otros generadores, el enfoque de árbol es el esqueleto de los generadores de estructura de Jean-Loup Faulon. Sin embargo, considerar todas las extensiones posibles conduce a una explosión combinatoria. La generación ordenada se realiza para hacer frente a esta exhaustividad. Muchos algoritmos de ensamblaje, como OMG, MOLGEN y el generador de estructuras de Jean-Loup Faulon,son métodos de generación ordenada. El generador de estructuras de Jean-Loup Faulon se basa en clases de equivalencia sobre átomos. Los átomos con el mismo tipo de interacción y elemento se agrupan en la misma clase de equivalencia. En lugar de extender todos los átomos de una molécula, un átomo de cada clase se conecta con otros átomos. Similar al generador anterior, el generador de estructuras de Julio Peironcely, OMG, toma átomos y subestructuras como entradas y extiende las estructuras usando un método de búsqueda primero en amplitud. Esta extensión del árbol termina cuando todas las ramas alcanzan estructuras saturadas.

OMG genera estructuras basadas en el método de aumento canónico del paquete NAUTY de Brendan McKay. El algoritmo calcula el etiquetado canónico y luego extiende las estructuras agregando un enlace. Para mantener la extensión canónica, se agregan enlaces canónicos. Aunque NAUTY es una herramienta eficiente para el etiquetado canónico de gráficos, OMG es aproximadamente 2000 veces más lento que MOLGEN. El problema es el almacenamiento de todas las estructuras intermedias. Desde entonces, OMG se ha paralelizado y los desarrolladores lanzaron PMG (generador de moléculas paralelas). MOLGEN supera a PMG usando solo 1 núcleo; sin embargo, PMG supera a MOLGEN al aumentar la cantidad de núcleos a 10.

Un algoritmo de búsqueda constructiva es un método de ramificación y acotación, como el algoritmo de Igor Faradjev, y una solución adicional a los problemas de memoria. Los métodos de ramificación y acotación son algoritmos de generación de matrices. A diferencia de los métodos anteriores, estos métodos construyen todas las matrices de conectividad sin construir estructuras intermedias. En estos algoritmos, los criterios de canonicidad y las comprobaciones de isomorfismos se basan en grupos de automorfismos de la teoría matemática de grupos. MASS, SMOG y el algoritmo de Ivan Bangovson buenos ejemplos en la literatura. MASS es un método de síntesis matemática. Primero, construye todas las matrices de incidencia para una fórmula molecular dada. Las valencias de los átomos se utilizan luego como entrada para la generación de la matriz. Las matrices se generan considerando todas las posibles interacciones entre átomos con respecto a las restricciones y valencias. El beneficio de los algoritmos de búsqueda constructivos es su bajo uso de memoria. SMOG es un sucesor de MASS.

A diferencia de los métodos anteriores, MOLGEN es el único generador de estructura genérica eficiente mantenido, desarrollado como una plataforma de código cerrado por un grupo de matemáticos como una aplicación de la teoría de grupos computacional. MOLGEN es un método de generación ordenada. Se han desarrollado muchas versiones diferentes de MOLGEN y proporcionan varias funciones. Según las necesidades de los usuarios, se pueden utilizar diferentes tipos de insumos. Por ejemplo, MOLGEN-MS permite a los usuarios ingresar datos de espectrometría de masas de una molécula desconocida. En comparación con muchos otros generadores, MOLGEN aborda el problema desde diferentes ángulos. La característica clave de MOLGEN es generar estructuras sin construir todas las estructuras intermedias y sin generar duplicados.

En campo, los estudios recientes a 2021 son del grupo de investigación de Kimito Funatsu. Como un tipo de método de ensamblaje, los bloques de construcción, como los sistemas de anillos y los fragmentos de átomos, se utilizan en la generación de estructuras. Cada estructura intermedia se amplía agregando bloques de construcción en todas las formas posibles. Para reducir el número de duplicados, se utiliza el método de aumento de ruta canónica de Brendan McKay. Para superar la explosión combinatoria en la generación, el dominio de aplicabilidad y los sistemas de anillo se detectan en función del análisis QSPR/QSAR inverso. El dominio de aplicabilidad, o área objetivo, se describe en función de la información de actividad biológica y farmacéutica proporcionada por QSPR/QSAR.En ese estudio, se utilizan descriptores cambiados monótonamente (MCD) para describir los dominios de aplicabilidad. Para cada extensión en estructuras intermedias, se actualizan los MCD. El uso de MCD reduce el espacio de búsqueda en el proceso de generación. En la generación de estructuras basada en QSPR/QSAR, existe la falta de capacidad de síntesis de las estructuras generadas. El uso de rutas de retrosíntesis en la generación hace que el proceso de generación sea más eficiente. Por ejemplo, se utiliza una herramienta muy conocida llamada RetroPath para la enumeración de estructuras moleculares y la detección virtual basada en las reglas de reacción dadas.Su algoritmo central es un método primero en amplitud, que genera estructuras aplicando reglas de reacción a cada compuesto fuente. La generación y enumeración de estructuras se realizan en base al método de aumento canónico de Brendan McKay. RetroPath 2.0 proporciona una variedad de flujos de trabajo, como transformación de isómeros, enumeración, QSAR y metabolómica.

Además de estos métodos de generación de estructuras matemáticas, las implementaciones de redes neuronales, como los modelos generativos de autocodificador, son las direcciones novedosas del campo.

Reducción de estructura

A diferencia de estos métodos de ensamblaje, los métodos de reducción hacen que todos los enlaces entre pares de átomos generen una hipergrafía. Entonces, el tamaño del gráfico se reduce con respecto a las restricciones. En primer lugar, se comprueba la existencia de subestructuras en la hipergrafía. A diferencia de los métodos de ensamblaje, el árbol de generación comienza con la hipergrafía y las estructuras disminuyen de tamaño en cada paso. Los enlaces se eliminan en función de las subestructuras. Si una subestructura ya no está en la hipergrafía, la subestructura se elimina de las restricciones. También se consideraron superposiciones en las subestructuras debido a las hipergrafías. El primer generador de estructuras basado en la reducción es COCOA, un método de eliminación de enlaces exhaustivo y recursivo. Los fragmentos generados se describen como fragmentos centrados en átomos para optimizar el almacenamiento, comparables a las huellas dactilares circulares.y firmas atómicas. En lugar de almacenar estructuras, solo se almacena la lista de los primeros vecinos de cada átomo. La principal desventaja de los métodos de reducción es el tamaño masivo de las hipergrafías. De hecho, para moléculas con estructuras desconocidas, el tamaño de la hiperestructura se vuelve extremadamente grande, lo que resulta en un aumento proporcional del tiempo de ejecución.

El generador de estructuras GENde Simona Bohanec combina dos tareas: montaje de estructura y reducción de estructura. Al igual que COCOA, el estado inicial del problema es una hiperestructura. Tanto el método de ensamblaje como el de reducción tienen ventajas y desventajas, y la herramienta GEN evita estas desventajas en el paso de generación. En otras palabras, la reducción de la estructura es eficiente cuando se proporcionan restricciones estructurales y el ensamblaje de la estructura es más rápido sin restricciones. Primero se eliminan las conexiones inútiles y luego se ensamblan las subestructuras para construir estructuras. Por lo tanto, GEN hace frente a las limitaciones de una manera más eficiente mediante la combinación de estos métodos. GEN elimina las conexiones que crean las estructuras prohibidas, y luego las matrices de conexión se llenan en función de la información de la subestructura. El método no acepta superposiciones entre subestructuras. Una vez que se construye la estructura en la representación matricial, la molécula saturada se almacena en la lista de salida. Se mejoró aún más el método COCOA y se construyó un nuevo generador, HOUDINI.Se basa en dos estructuras de datos: se construye una matriz cuadrada de compuestos que representan todos los enlaces en una hiperestructura y, en segundo lugar, se usa la representación de la subestructura para enumerar fragmentos centrados en átomos. En la generación de estructuras, HOUDINI mapea todos los fragmentos centrados en átomos en la hiperestructura.

Base matemática

Gráficos químicos

En un gráfico que representa una estructura química, los vértices y los bordes representan átomos y enlaces, respectivamente. El orden de enlace corresponde a la multiplicidad de aristas y, como resultado, los gráficos químicos son gráficos de vértices y de aristas. Un gráfico con vértices y aristas se describe como un gráfico químico donde es el conjunto de vértices, es decir, átomos, y es el conjunto de aristas, que representa los enlaces.

En teoría de grafos, el grado de un vértice es su número de conexiones. En un gráfico químico, el grado máximo de un átomo es su valencia y el número máximo de enlaces que puede hacer un elemento químico. Por ejemplo, la valencia del carbono es 4. En un gráfico químico, un átomo está saturado si alcanza su valencia. Un grafo es conexo si hay al menos un camino entre cada par de vértices. Aunque las mezclas químicas son uno de los principales intereses de muchos químicos, debido a la explosión computacional, muchos generadores de estructuras generan solo gráficos químicos conectados. Por lo tanto, la verificación de conectividad es uno de los pasos intermedios obligatorios en la generación de estructuras porque el objetivo es generar moléculas completamente saturadas. Una molécula está saturada si todos sus átomos están saturados.

Grupos de simetría para gráficos moleculares

Para un conjunto de elementos, una permutación es un reordenamiento de estos elementos. A continuación se muestra un ejemplo:

	1	2	3	4	5	6	7	8	9	10	11
	4	2	11	6	1	5	8	9	7	10	3

La segunda línea de esta tabla muestra una permutación de la primera línea. La multiplicación de permutaciones, y , se define como una composición de función, como se muestra a continuación.

La combinación de dos permutaciones también es una permutación. Un grupo, , es un conjunto de elementos junto con una operación binaria asociativa definida en tal que se cumple lo siguiente:

• Hay un elemento en satisfacer , para todos los elementos de .
• Para cada elemento de G, existe un elemento tal que es igual al elemento identidad.

El orden de un grupo es el número de elementos en el grupo. Supongamos que es un conjunto de números enteros. Bajo la operación de composición de funciones, es un grupo de simetría, el conjunto de todas las permutaciones sobre X. Si el tamaño de es , entonces el orden de es . Los sistemas de conjuntos consisten en un conjunto finito y sus subconjuntos, llamados bloques del conjunto. El conjunto de permutaciones que conserva el sistema de conjuntos se utiliza para construir los automorfismos del gráfico. Un automorfismo permuta los vértices de un gráfico; en otras palabras, mapea un gráfico sobre sí mismo. Esta acción preserva el borde y el vértice. Si es una arista de la gráfica, y es una permutación de , entonces

Una permutación de es un automorfismo del gráfico sies un elemento de , si es un elemento de .

El grupo de automorfismos de un gráfico , denotado , es el conjunto de todos los automorfismos en . En gráficos moleculares, el etiquetado canónico y la detección de simetría molecular son implementaciones de grupos de automorfismos. Aunque existen métodos de etiquetado canónico bien conocidos en el campo, como InChI y ALATIS, NAUTY es un paquete de software comúnmente utilizado para cálculos de grupos de automorfismos y etiquetado canónico.

Lista de generadores de estructuras disponibles

Los paquetes de software disponibles y sus enlaces se enumeran a continuación.

Nombre	Enlace
ARMAR	www.upstream.ch /main.html
COCON	cocon.nmr.de
CONGÉN DENDRAL+GÉNOVA	www.softwarepreservation.org /projects /AI /DENDRAL /DENDRAL-CONGEN _GENOA.zip /view
LSD	eos.univ-reims.fr /LSD /index _ESP.html
MOLGEN	www.molgen.de _ _
MOLSIG	molsig.sourceforge.net
DIOS MÍO	sourceforge.net /p /openmg
PMG	sourceforge.net /proyectos /pmgcoordination
SÉNECA	github.com/steinbeck/seneca _ _ _
NIEBLA TÓXICA	ccl.net /cca /software /MS-DOS /SMOG