A Computational Study of Algebraic Chemistry

Abstract

La Química Algebraica es un modelo abstracto para la bioquímica. Una Química Algebraica se compone de una red de reacciones moleculares, prescindiendo de una dinámica que permita estudiar su evolución, pues el modelo se enfoca en como las moléculas pueden ser producidas o consumidas por las reacciones. Se ha probado que en una Química Algebraica, un tipo especial de subredes llamadas organizaciones, son las únicas subredes que pueden tener estabilidad dinámica. Este hecho permite simplificar la comprensión de la dinámica de los sistemas bioquímicos, dado que permite explicar la evolución del sistema como movimientos entre organizaciones en el espacio de fase. De aquí que el cómputo del conjunto de organizaciones de una Química Algebraica es una tarea central en la teoría. Al momento no han hay suficientemente buenos algoritmos para computar organizaciones, ni hay una comprensión de la estructura que subyace en la definición de organización (tal vez es esto es la razón de lo anterior). Esta tesis es un intento por formalizar el trabajo algorítmico en Químicas Algebraicas. Dicha formalización busca una fertilización cruzada entre modelos de Ciencias de la computación y Químicas Algebraicas. Es posible enmarcar las Químicas Algebraicas en algunos conocidos formalismos de la Ciencia de la computación como Sistemas de Adición de Vectores y Redes de Petri. Se investiga la equivalencia entre los formalismos mencionados y las Químicas Algebraicas. Luego algunos conocidos problemas de los Sistemas de Adición de Vectores y Redes de Petri tales como alcance (reachability), vida (liveness), etc., son estudiados desde la perspectiva de las Químicas Algebraicas, enfocando el análisis a la relación de dichos problemas con el problema de computar organizaciones. De las ideas que surgen del anterior análisis, se hace posible el desarrollo de varios resultados sobre el cómputo de organizaciones, así como sobre la estructura del conjunto total de organizaciones de una Química Algebraica. Un teorema para descomponer una organización, en subsistemas más simples, y sus implicaciones son derivados como los resultados más importantes de esta tesis. Los resultados de este trabajo hacen posible además el desarrollo de nuevos y más eficientes algoritmos para el cómputo de organizaciones y permite separar diferentes clases de Químicas Algebraicas en términos de la dificultad de computar su conjunto de organizaciones.