Towards Mass Spectrum Analysis with ASP

Resumen Técnico: Análisis de Espectros de Masas mediante Programación de Conjuntos de Respuesta (ASP)

1. Planteamiento del Problema

El objetivo principal de la investigación es determinar la estructura molecular de muestras químicas basándose en la información parcial proporcionada por la espectrometría de masas.

• El desafío: La espectrometría de masas revela la composición elemental (fórmula molecular) y la abundancia relativa de fragmentos, pero no la estructura exacta de los enlaces. Esto convierte la identificación de la molécula en un problema de búsqueda combinatoria.
• La limitación actual: Aunque la Programación de Conjuntos de Respuesta (ASP) es ideal para codificar conocimiento químico (valencias, tipos de enlaces), una codificación directa genera un número exponencial de conjuntos de respuesta (soluciones) debido a las simetrías del grafo (automorfismos). Por ejemplo, una molécula simple como $C_6H_{12}O$ tiene 211 estructuras distintas, pero una codificación ASP ingenua puede generar más de 111,000 soluciones redundantes.
• Necesidad: Se requiere un método para romper estas simetrías de manera eficiente durante la fase de "grounding" (instantiación) para enumerar únicamente estructuras moleculares únicas (no isomorfas).

2. Metodología

Los autores desarrollan Genmol, una herramienta prototipo que utiliza ASP para enumerar estructuras moleculares. La metodología se basa en tres pilares fundamentales:

A. Representación Canónica de Grafos Moleculares
Para eliminar soluciones redundantes, los autores definen una representación canónica única para cada grafo molecular, inspirada en el formato SMILES pero formalizada para ASP:

1. Árboles Moleculares Canónicos: Para grafos acíclicos, se define un orden total estricto ($\prec$) sobre los árboles moleculares. La representación canónica se selecciona como el árbol $\prec$-máximo entre todos los isomorfos.
   • Se utiliza una tupla de características $R(G, v)$ (profundidad, tamaño, número de hijos, elemento, etiqueta de entrada) para comparar nodos y subárboles lexicográficamente.
   • Se selecciona una raíz central (basada en los vértices centrales de los caminos más largos) para garantizar la unicidad.
2. Grafos con Ciclos: Para grafos cíclicos, se transforma el grafo en un árbol sustituyendo las aristas de los ciclos por nuevas aristas y nodos frescos. La representación canónica se define como la "refinación máxima centralizada" que resulta en el árbol $\prec$-máximo.
3. Restricciones Heurísticas: Dado que calcular la representación canónica exacta para grafos complejos es computacionalmente costoso en ASP, se implementan heurísticas para detectar y eliminar "ciclos acortantes" (estructuras que no maximizan la profundidad del árbol) y asegurar que los hijos de un nodo estén ordenados según la relación $\prec$.

B. Implementación en ASP (Genmol)
La implementación en clingo sigue un enfoque de "adivinar y verificar" optimizado:

• Fase de Adivinanza: Se adivinan las longitudes de la cadena principal, la distribución de elementos, enlaces múltiples y marcadores de ciclos.
• Fase de Construcción: Se construye el árbol de expansión (spanning tree) iterativamente, garantizando que la raíz sea central y que la profundidad de los subárboles sea no creciente de izquierda a derecha (cumpliendo el orden canónico).
• Filtrado: Se aplican restricciones para eliminar representaciones que no pueden ser canónicas (ej. raíces no centrales, ordenamiento incorrecto de hermanos).

C. Herramienta Genmol

• Desarrollada en Rust con una interfaz web progresiva (PWA).
• Utiliza ASP para el núcleo de búsqueda.
• Permite entrada de fórmulas sumarias, fragmentos detectados y restricciones de tipos de enlace.

3. Contribuciones Clave

1. Nueva Codificación ASP: Se presenta una codificación que integra la ruptura de simetrías directamente en la generación de soluciones, en lugar de filtrarlas después.
2. Definición Formal de Canonicidad: Se define rigurosamente una representación de árbol canónico para grafos moleculares que permite una comparación total y única.
3. Ruptura de Simetría Perfecta (Acíclicos): Para estructuras acíclicas (sin ciclos), el método logra una ruptura de simetría perfecta, eliminando el 100% de las soluciones redundantes.
4. Reducción Significativa (Cíclicos): Para estructuras cíclicas, se logra una reducción de hasta tres órdenes de magnitud en el número de conjuntos de respuesta en comparación con métodos ASP estándar.
5. Evaluación Comparativa: Se compara el enfoque contra:
   • Codificaciones ASP ingenuas.
   • Métodos de ruptura de simetría genéricos (sbass, BreakID).
   • Una herramienta comercial líder en química analítica (Molgen).

4. Resultados de la Evaluación

Los experimentos se realizaron en un servidor con 768 GB de RAM utilizando el solver clingo v5.7.1 sobre un conjunto de datos de 5,625 compuestos químicos reales.

• Correctitud: Genmol encontró la estructura molecular correcta para el 97.5% de los compuestos (5,338 de 5,473) dentro del tiempo límite. Los fallos se debieron principalmente a compuestos muy grandes o insaturados que excedían el tiempo de cómputo, o a errores en los datos de origen (Wikidata).
• Eficiencia en Ruptura de Simetría:
  • Genmol redujo drásticamente el número de modelos en comparación con la codificación "Naive". Para el caso $C_8H_2$, la reducción fue de un factor de 39 (vs. >20,000 en Naive).
  • El 99% de los compuestos generaron un número de modelos dentro de un factor de 10 del óptimo (Molgen), frente a un 48% para las herramientas genéricas (BreakID, sbass).
  • Los métodos genéricos (BreakID, sbass) apenas mejoraron sobre la codificación ingenua y, en algunos casos, aumentaron los tiempos de espera (timeouts).
• Rendimiento y Escalabilidad:
  • Genmol es la aproximación basada en ASP más escalable, acercándose al rendimiento de la herramienta comercial Molgen.
  • Los tiempos de ejecución crecen exponencialmente con el tamaño de la molécula, pero Genmol mantiene tiempos de cómputo manejables para moléculas de hasta 16-17 átomos.
• Aprendizaje de Restricciones: Se intentó aprender restricciones de ruptura de simetría automáticamente usando ilasp, pero el proceso falló por agotamiento de memoria, demostrando que en este dominio es más efectivo definir las restricciones manualmente basándose en la teoría de grafos.

5. Significado e Impacto

• Viabilidad de ASP en Química: El trabajo demuestra que ASP es una base prometedora para problemas de análisis de estructuras químicas, ofreciendo una flexibilidad superior a las herramientas comerciales (que son "cajas negras") con un rendimiento competitivo.
• Generalización: Las técnicas de representación canónica y ruptura de simetría desarrolladas no se limitan a la química; son aplicables a cualquier problema de búsqueda de grafos no dirigidos con restricciones de grado.
• Herramienta Práctica: Genmol proporciona una interfaz accesible para investigadores que necesitan explorar el espacio de estructuras moleculares posibles a partir de datos espectrométricos parciales, permitiendo la integración de conocimiento experto adicional (ej. presencia de grupos funcionales específicos) de forma sencilla.

En conclusión, el artículo establece un nuevo estándar para la enumeración de estructuras moleculares mediante lógica declarativa, resolviendo eficazmente el problema de la explosión combinatoria mediante una teoría de grafos canónicos integrada directamente en el solver.