generador de gráficos químicos

El proceso de generación comienza con un conjunto de átomos de la fórmula molecular . En el ensamblaje de la estructura, 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. Uno de los primeros intentos fue realizado por Hidetsugu Abe en 1975 utilizando un generador de estructuras basado en reconocimiento de patrones . ^{[ 10 ]} El algoritmo tenía dos pasos: primero, la predicción de la subestructura a partir de datos espectrales de baja resolución ; segundo, el ensamblaje de estas subestructuras basado en un conjunto de reglas de construcción. Hidetsugu Abe y otros colaboradores publicaron el primer artículo sobre CHEMICS, ^{[ 11 ]} que es una herramienta CASE que comprende varios métodos de generación de estructuras. El programa se basa en una biblioteca de fragmentos no superpuestos predefinida. CHEMICS genera diferentes tipos de conjuntos de componentes clasificados de primario a terciario según la complejidad del componente. 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 realizaron importantes contribuciones, publicando numerosos artículos CASE en este campo. El primero de estos artículos describió un generador de estructuras, ASSEMBLE. ^{[ 12 ]} El algoritmo se considera uno de los primeros métodos de ensamblaje en este campo. Como su nombre indica, el algoritmo ensambla subestructuras con solapamientos para construir estructuras. ASSEMBLE supera el solapamiento mediante la inclusión de una "etiqueta de átomo vecino". El generador es puramente matemático y no requiere la interpretación de datos espectrales. Los datos espectrales se utilizan para la puntuación de la estructura y la información de la subestructura. Basándose en la fórmula molecular, el generador forma enlaces entre pares de átomos, y todas las extensiones se verifican con respecto a 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 hay, proporcionadas por los datos espectrales. Al extender la molécula con un enlace, se construye una estructura intermedia. Cada estructura intermedia puede representarse mediante un nodo en el árbol de generación. ASSEMBLE se desarrolló con una interfaz fácil de usar para facilitar su utilización. La segunda versión de ASSEMBLE se lanzó en 2000. ^{[ 13 ]} Otro método de ensamblaje es GENOA. ^{[ 14 ]} En comparación con ASSEMBLE y muchos otros generadores, GENOA es un algoritmo constructivo basado en la búsqueda de subestructuras, 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 ^{[ 15 ]} era un generador de procesamiento de listas. En comparación con las matrices de adyacencia, los datos de lista requieren menos memoria . Como en este sistema no se interpretaban datos espectrales, el usuario debía 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 HMBC de moléculas desconocidas ^{[ 16 ]} , e implica un exhaustivo proceso de generación de estructuras en dos pasos donde primero todas las combinaciones de interpretaciones de señales HMBC se implementan en una matriz de conectividad, que luego se completa mediante un generador determinista que rellena la información de enlaces faltante. Esta plataforma podía generar estructuras con moléculas de cualquier tamaño arbitrario; sin embargo, las fórmulas moleculares con más de 30 átomos pesados ​​son demasiado lentas para aplicaciones prácticas. Esta limitación puso de manifiesto la necesidad de un nuevo sistema CASE. SENECA se desarrolló para eliminar las deficiencias de LUCY. ^{[ 17 ]} 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, el proceso continúa hasta que se alcanza la energía óptima . En la generación, esta transformación se basa en ecuaciones basadas en las reglas de Jean-Loup Faulon. ^{[ 18 ]} LSD (Logic for Structure Determination) ^{[ 19 ]} es una contribución importante de 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 estructuras de código abierto publicado bajo la Licencia Pública General (GPL) . Un conocido sistema CASE comercial, StrucEluc, ^{[ 20 ]} 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 ^{[ 21 ]}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, se pueden usar todos los tipos de RMN como entrada.

En 1994, Hu y Xu informaron sobre un generador de estructuras basado en particiones enteras . ^{[ 22 ]} La descomposición de la fórmula molecular en fragmentos, componentes y segmentos se realizó como una aplicación de la partición entera. Estos fragmentos se utilizaron posteriormente como bloques de construcción en el generador de estructuras. Este generador de estructuras formaba parte de un sistema CASE, ESESOC. ^{[ 23 ]}

Jean-Loup Faulon informó sobre una serie de generadores estocásticos. El software MOLSIG ^{[ 24 ]} se integró en este generador estocástico para el etiquetado canónico y la verificación de duplicados ^{[ 25 ]} . Al igual que muchos otros generadores, el enfoque de árbol es el esqueleto de los generadores de estructuras de Jean-Loup Faulon. Sin embargo, considerar todas las extensiones posibles conduce a una explosión combinatoria . Se realiza una generación ordenada para abordar esta exhaustividad. Muchos algoritmos de ensamblaje, como OMG ^{[ 26 ]} , MOLGEN y el generador de estructuras de Jean-Loup Faulon ^{[ 27 ]} , 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 en una molécula, un átomo de cada clase se conecta con otros átomos. Al igual que el generador anterior, el generador de estructuras de Julio Peironcely, OMG, toma átomos y subestructuras como entrada y extiende las estructuras mediante un método de búsqueda en anchura . Esta extensión del árbol finaliza 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. ^{[ 28 ]} Aunque NAUTY es una herramienta eficiente para el etiquetado canónico de grafos, OMG es aproximadamente 2000 veces más lento que MOLGEN. ^{[ 29 ]} El problema es el almacenamiento de todas las estructuras intermedias. OMG se ha paralelizado desde entonces , y los desarrolladores lanzaron PMG (Parallel Molecule Generator). ^{[ 30 ]} MOLGEN supera a PMG usando solo 1 núcleo; sin embargo, PMG supera a MOLGEN al aumentar el número 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 isomorfismo se basan en grupos de automorfismos de la teoría matemática de grupos . MASS, SMOG ^{[ 31 ]} y el algoritmo de Ivan Bangov ^{[ 32 ]} son ​​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 matrices. Las matrices se generan considerando todas las interacciones posibles entre átomos con respecto a las restricciones y valencias. La ventaja de los algoritmos de búsqueda constructiva 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 estructuras genéricas eficiente y 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 ordenado. Se han desarrollado muchas versiones diferentes de MOLGEN, que ofrecen diversas funciones. Según las necesidades del usuario, se pueden utilizar diferentes tipos de entradas. Por ejemplo, MOLGEN-MS ^{[ 33 ]} permite a los usuarios introducir datos de espectrometría de masas de una molécula desconocida. En comparación con muchos otros generadores, MOLGEN aborda el problema desde diferentes perspectivas. La característica clave de MOLGEN es la generación de estructuras sin construir todas las estructuras intermedias y sin generar duplicados.

En el campo, los estudios recientes hasta 2021 son del grupo de investigación de Kimito Funatsu . Como un tipo de método de ensamblaje, se utilizan bloques de construcción, como sistemas de anillos y fragmentos de átomos, en la generación de la estructura. ^{[ 34 ]} Cada estructura intermedia se extiende agregando bloques de construcción de todas las maneras 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 anillos se detectan basándose en el análisis QSPR/QSAR inverso . ^{[ 35 ]} El dominio de aplicabilidad, o área objetivo, se describe basándose en la información de actividad biológica y farmacéutica dada de QSPR/QSAR. ^{[ 36 ]} En ese estudio, se utilizan descriptores cambiados monótonamente (MCD) para describir los dominios de aplicabilidad. Para cada extensión en las estructuras intermedias, los MCD se actualizan. 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 sintetizabilidad 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, una herramienta bien conocida llamada RetroPath ^{[ 37 ]} se utiliza para la enumeración de estructuras moleculares y el cribado virtual basado en reglas de reacción dadas. ^{[ 38 ]} Su algoritmo central es un método de búsqueda en amplitud, generando estructuras aplicando reglas de reacción a cada compuesto fuente. La generación y enumeración de estructuras se realizan basándose en el método de aumento canónico de Brendan McKay. RetroPath 2.0 proporciona una variedad de flujos de trabajo tales 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 autoencoder generativos , ^{[ 39 ] [ 40 ]} son ​​las direcciones novedosas del campo.

A diferencia de estos métodos de ensamblaje, los métodos de reducción crean todos los enlaces entre pares de átomos, generando un hipergrafo. Luego, el tamaño del grafo se reduce con respecto a las restricciones. Primero, se verifica la existencia de subestructuras en el hipergrafo. A diferencia de los métodos de ensamblaje, el árbol de generación comienza con el hipergrafo, 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 el hipergrafo, se elimina de las restricciones. También se consideraron las superposiciones en las subestructuras debido a los hipergrafos. El primer generador de estructuras basado en reducción es COCOA, ^{[ 41 ]} un método exhaustivo y recursivo de eliminación de enlaces. Los fragmentos generados se describen como fragmentos centrados en átomos para optimizar el almacenamiento, comparable a las huellas digitales circulares ^{[ 42 ]} y las firmas atómicas. ^{[ 43 ]} En lugar de almacenar estructuras, solo se almacena la lista de primeros vecinos de cada átomo. La principal desventaja de los métodos de reducción es el tamaño masivo de los hipergrafos. 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 GEN ^{[ 44 ]} de Simona Bohanec combina dos tareas: ensamblaje y reducción de estructuras. 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 la etapa de generación. En otras palabras, la reducción de estructuras es eficiente cuando se proporcionan restricciones estructurales, y el ensamblaje de estructuras es más rápido sin restricciones. Primero, se eliminan las conexiones innecesarias y luego se ensamblan las subestructuras para construir estructuras. Así, GEN maneja las restricciones de una manera más eficiente al combinar estos métodos. GEN elimina las conexiones que crean estructuras prohibidas y luego las matrices de conexión se completan en función de la información de la subestructura. El método no acepta solapamientos entre subestructuras. Una vez que la estructura se construye en la representación matricial, la molécula saturada se almacena en la lista de salida. El método COCOA se mejoró aún más y se construyó un nuevo generador, HOUDINI. ^{[ 45 ]} Se basa en dos estructuras de datos: primero, se construye una matriz cuadrada de compuestos que representa todos los enlaces en una hiperestructura, y segundo, se utiliza una representación de subestructura para listar los fragmentos centrados en átomos. En la generación de la estructura, HOUDINI mapea todos los fragmentos centrados en átomos sobre la hiperestructura.

En un grafo que representa una estructura química, los vértices y las aristas representan átomos y enlaces, respectivamente. El orden de los enlaces corresponde a la multiplicidad de las aristas y, como resultado, los grafos químicos son grafos con vértices y aristas etiquetados . Un grafo con vértices y aristas etiquetados${\displaystyle G=(V,E)}$se describe como un gráfico químico donde${\displaystyle V}$es el conjunto de vértices, es decir, átomos, y${\displaystyle E}$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 grafo químico, el grado máximo de un átomo es su valencia y el número máximo de enlaces que un elemento químico puede formar. Por ejemplo, la valencia del carbono es 4. En un grafo químico, un átomo está saturado si alcanza su valencia. Un grafo está conectado si hay al menos un camino entre cada par de vértices. Aunque las mezclas químicas ^{[ 46 ]} son ​​uno de los principales intereses de muchos químicos , debido a la explosión computacional, muchos generadores de estructuras solo producen grafos 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.

Para un conjunto de elementos, una permutación es una reorganización de estos elementos. ^{[ 47 ]} A continuación se muestra un ejemplo:

La segunda línea de esta tabla muestra una permutación de la primera línea. La multiplicación de permutaciones,${\displaystyle a}$y${\displaystyle b}$, se define como una composición de funciones , como se muestra a continuación.

${\displaystyle (a*b)(x)=a(b(x))}$

La combinación de dos permutaciones también es una permutación. Un grupo ,${\displaystyle G}$es un conjunto de elementos junto con una operación binaria asociativa${\displaystyle *}$definido en${\displaystyle G}$de tal manera que se cumplen las siguientes condiciones:

• Hay un elemento${\displaystyle I}$en${\displaystyle G}$satisfactorio${\displaystyle g*I=g}$, para todos los elementos${\displaystyle g}$de${\displaystyle G}$.

• Para cada elemento de G, hay un elemento${\displaystyle g^{-1}}$de tal manera que${\displaystyle g*g^{-1}}$es igual al elemento identidad .

El orden de un grupo es el número de elementos en el grupo. Supongamos que${\displaystyle X}$es un conjunto de números enteros. Bajo la operación de composición de funciones,${\displaystyle Sym(X)}$es un grupo de simetría , el conjunto de todas las permutaciones sobre X. Si el tamaño de${\displaystyle X}$es${\displaystyle n}$, entonces el orden de${\displaystyle Sym(X)}$es${\displaystyle n!}$Los sistemas de conjuntos constan de un conjunto finito${\displaystyle X}$y sus subconjuntos , llamados bloques del conjunto. El conjunto de permutaciones que preservan el sistema de conjuntos se utiliza para construir los automorfismos del grafo. Un automorfismo permuta los vértices de un grafo; en otras palabras, mapea un grafo sobre sí mismo. Esta acción preserva los vértices y las aristas. Si${\displaystyle (u,v)}$es una arista del grafo,${\displaystyle G=(V,E)}$, y${\displaystyle a}$es una permutación de${\displaystyle V}$, entonces

${\displaystyle a({u,v})=(a(u),a(v))}$

Una permutación${\displaystyle a}$de${\displaystyle V}$es un automorfismo del grafo${\displaystyle G=(E,V)}$si

${\displaystyle a(u,v)}$es un elemento de${\displaystyle E}$, si${\displaystyle {(u,v)}}$es un elemento de${\displaystyle E}$.

El grupo de automorfismos de un grafo${\displaystyle G}$, denotado${\displaystyle Aut(G)}$, es el conjunto de todos los automorfismos en${\displaystyle V}$En los grafos 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 ^{[ 48 ]} y ALATIS ^{[ 49 ]} , NAUTY es un paquete de software comúnmente utilizado para cálculos de grupos de automorfismos y etiquetado canónico.