Cálculo de volúmenes de politopos en espacios de altas dimensiones

Abstract

En este trabajo se estudia la aplicabilidad de los métodos de Monte Carlo para el estudio de las redes metabólicas de microorganismos como la Escherichia coli. En particular, se busca estimar el volumen del espacio de soluciones determinado por las posibles configuraciones de las redes mencionadas. Este problema surge en la literatura del área, donde se utilizan modelos lineales a partir de la información genómica y de restricciones adicionales, cuyos espacios de soluciones son politopos expresados como la interseción de un conjunto finito de semiespacios cerrados (H−Politopos). En un trabajo de maestría previo realizado en Udelar se abordó este mismo problema, llegando a estimar volúmenes con una cantidad limitada de dimensiones. Por lo tanto, el desafío pendiente que se planteó para abordar en este trabajo fue el estudio de algoritmos que permitieran aproximar el volumen utilizando este tipo de representación para espacios con mayor dimensión que la que fue alcanzada en la tesis mencionada. En el presente trabajo se realizó un relevamiento de estado del arte. A partir de ese estudio, se seleccionaron e implementaron tres métodos basados en Monte Carlo, que fueron vistos en trabajos relacionados al estudio específico de redes metabólicas. Por otra parte, se estudiaron y utilizaron los algoritmos, también basados en Monte Carlo, implementados en la librería de código abierto VolEsti. A su vez se estudiaron herramientas de software que calculan el volumen exacto de politopos regulares, para poder verificar la precisión de los resultados obtenidos con los otros algoritmos. A partir del estudio de estas herramientas pudimos recopilar un conjunto de politopos básico, para el cual se conoce su volumen. Los algoritmos basados en Monte Carlo que estudiamos fueron aplicados a este conjunto básico de politopos, con el fin de evaluar su desempeño antes de pasar a la etapa de aplicación de los mismos en los modelos metabólicos. El politopo de mayor dimensión que utilizamos en estas pruebas fue el politopo de Birkhoff de dimensión 81. En esta etapa del trabajo, verificamos que los resultados se aproximaban al volumen exacto con un error relativo porcentual aceptable en la mayoría de los politopos (incluso en los de mayor dimensión), pero hubo un subconjunto para los cuales los resultados no fueron buenos. Luego de estudiar las características de este subconjunto, vimos que se trataba de politopos con una forma alargada, es decir que tiene subespacios que se encuentran mucho más acotados que otros en determinadas direcciones. Obtener dichos resultados nos permitió verificar empíricamente lo que encontramos que decía la literatura con respecto a que los métodos estudiados no funcionan bien con politopos de estas características. Finalmente, seleccionamos un subconjunto de los algoritmos estudiados para ser aplicados en dos modelos que representan la red metabólica del organismo unicelular Escherichia coli (modelo compacto E.coli y modelo núcleo E.coli). En este punto, cabe destacar que la forma característica de estos modelos es similar a la de los modelos básicos para los cuales no se obtuvieron buenos resultados en la etapa anterior. Esto se debe a que la manera de modelar condiciones ambientales o biológicas que representan características del comportamiento del metabolismo de los microorganismos es utilizar restricciones muy acotadas en relación a las demás. Al igual que en la etapa anterior del trabajo, en una primera instancia no obtuvimos buenos resultados, pero luego de realizar un ajuste al modelo, pudimos seleccionar los dos algoritmos que devolvieron mejores resultados. A partir de estos resultados aplicamos el método de Bland-Altman que es utilizado para determinar si 2 métodos diferentes que miden la misma propiedad concuerdan lo suficiente para que se pueda decir que son intercambiables. A los efectos de este trabajo considerando como indicadores el error relativo calculado a partir de los politopos para los cuales pudimos calcular el volumen exacto y el resultado del análisis mediante el método Bland-Altman concluimos que la aproximación del volumen que obtuvimos para el modelo compacto E.coli fue aceptable; mientras que para el caso del modelo núcleo E.Coli, de mayores dimensiones, no fue posible alcanzar una aproximación de buena calidad, mostrando que es necesario continuar el trabajo de desarrollo de nuevos métodos para atender casos similares.