Eliminación sin salida

Algoritmo para minimizar una función sobre un conjunto de variables independientes

El algoritmo de eliminación de callejones sin salida ( DEE ) es un método para minimizar una función sobre un conjunto discreto de variables independientes . La idea básica es identificar "callejones sin salida", es decir, combinaciones de variables que no son necesarias para definir un mínimo global porque siempre hay una forma de reemplazar dicha combinación por una mejor o equivalente. Entonces podemos abstenernos de buscar más dichas combinaciones. Por lo tanto, la eliminación de callejones sin salida es una imagen especular de la programación dinámica , en la que se identifican y exploran más a fondo las combinaciones "buenas".

Aunque el método en sí es general, se ha desarrollado y aplicado principalmente a los problemas de predicción y diseño de las estructuras de las proteínas (y de esta manera se citó en los antecedentes científicos del Premio Nobel de Química de 2024 ). ^[1] Está estrechamente relacionado con la noción de dominio en optimización, también conocida como sustituibilidad en un problema de satisfacción de restricciones . La descripción y prueba original del teorema de eliminación de callejón sin salida se puede encontrar en ^[1] .

Requisitos básicos

Una implementación eficaz del DEE requiere cuatro piezas de información:

1. Un conjunto finito bien definido de variables independientes discretas
2. Un valor numérico precalculado (considerado la "energía") asociado con cada elemento del conjunto de variables (y posiblemente con sus pares, triples, etc.)
3. Un criterio o criterios para determinar cuándo un elemento es un "callejón sin salida", es decir, cuando no puede ser miembro del conjunto de soluciones.
4. Una función objetivo (considerada la "función energética") a minimizar

Tenga en cuenta que los criterios también se pueden invertir fácilmente para identificar el máximo de una función dada.

Aplicaciones a la predicción de la estructura de proteínas

La eliminación de extremos muertos se ha utilizado de manera eficaz para predecir la estructura de las cadenas laterales en una estructura de cadena principal de proteína dada al minimizar una función de energía . El espacio de búsqueda de ángulos diedros de las cadenas laterales está restringido a un conjunto discreto de rotámeros para cada posición de aminoácido en la proteína (que, obviamente, tiene una longitud fija). La descripción original de DEE incluía criterios para la eliminación de rotámeros individuales y de pares de rotámeros, aunque esto se puede ampliar. ${\displaystyle E}$

En la siguiente discusión, sea la longitud de la proteína y sea el rotámero de la cadena lateral. Dado que se supone que los átomos en las proteínas interactúan solo mediante potenciales de dos cuerpos , la energía puede escribirse ${\displaystyle N}$ ${\displaystyle r_{k}}$ ${\displaystyle \mathrm {k^{th}} }$

${\displaystyle E_{TOT}=\sum _{k}E_{k}(r_{k})+\sum _{k\neq l}E_{kl}(r_{k},r_{l})\,}$

Donde representa la "autoenergía" de un rotámero particular , y representa la "energía de par" de los rotámeros . ${\displaystyle E_{k}(r_{k})}$ ${\displaystyle r_{k}}$ ${\displaystyle E_{kl}(r_{k},r_{l})}$ ${\displaystyle r_{k},r_{j}}$

También tenga en cuenta que (es decir, la energía de par entre un rotámero y él mismo) se considera igual a cero y, por lo tanto, no afecta las sumas. Esta notación simplifica la descripción del criterio de pares que se muestra a continuación. ${\displaystyle E_{kk}(r_{k}^{A},r_{k}^{A})}$

Criterio de eliminación de individuales

Si un rotámero particular de cadena lateral no puede dar una mejor energía que otro rotámero de la misma cadena lateral, entonces el rotámero A puede eliminarse de la consideración posterior, lo que reduce el espacio de búsqueda. Matemáticamente, esta condición se expresa mediante la desigualdad ${\displaystyle r_{k}^{A}}$ ${\displaystyle k}$ ${\displaystyle r_{k}^{B}}$

${\displaystyle E_{k}(r_{k}^{A})+\sum _{l=1}^{N}\min _{X}E_{kl}(r_{k}^{A},r_{l}^{X})>E_{k}(r_{k}^{B})+\sum _{l=1}^{N}\max _{X}E_{kl}(r_{k}^{B},r_{l}^{X})}$

donde es la energía mínima (mejor) posible entre el rotámero de la cadena lateral y cualquier rotámero X de la cadena lateral . De manera similar, es la energía máxima (peor) posible entre el rotámero de la cadena lateral y cualquier rotámero X de la cadena lateral . ${\displaystyle \min _{X}E_{kl}(r_{k}^{A},r_{l}^{X})}$ ${\displaystyle r_{k}^{A}}$ ${\displaystyle k}$ ${\displaystyle l}$ ${\displaystyle \max _{X}E_{kl}(r_{k}^{B},r_{l}^{X})}$ ${\displaystyle r_{k}^{B}}$ ${\displaystyle k}$ ${\displaystyle l}$

Criterio de eliminación de parejas

El criterio de pares es más difícil de describir e implementar, pero agrega un poder de eliminación significativo. Para abreviar, definimos la variable abreviada que es la energía intrínseca de un par de rotámeros y en las posiciones y , respectivamente. ${\displaystyle U_{kl}^{AB}}$ ${\displaystyle A}$ ${\displaystyle B}$ ${\displaystyle k}$ ${\displaystyle l}$

${\displaystyle U_{kl}^{AB}\ {\stackrel {\mathrm {def} }{=}}\ E_{k}(r_{k}^{A})+E_{l}(r_{l}^{B})+E_{kl}(r_{k}^{A},r_{l}^{B})}$

Un par dado de rotámeros y en las posiciones y , respectivamente, no pueden estar ambos en la solución final (aunque uno u otro sí lo estén) si existe otro par y este siempre da una mejor energía. Expresado matemáticamente, ${\displaystyle A}$ ${\displaystyle B}$ ${\displaystyle k}$ ${\displaystyle l}$ ${\displaystyle C}$ ${\displaystyle D}$

${\displaystyle U_{kl}^{AB}+\sum _{i=1}^{N}\min _{X}\left(E_{ki}(r_{k}^{A},r_{i}^{X})+E_{lj}(r_{l}^{B},r_{j}^{X})\right)>U_{kl}^{CD}+\sum _{i=1}^{N}\max _{X}\left(E_{ki}(r_{k}^{C},r_{i}^{X})+E_{lj}(r_{l}^{D},r_{j}^{X})\right)}$

donde , y . ${\displaystyle A\neq C}$ ${\displaystyle B\neq D}$ ${\displaystyle k\neq l}$

Matrices energéticas

Para valores grandes , las matrices de energías precalculadas pueden resultar costosas de almacenar. Sea el número de posiciones de aminoácidos, como se indicó anteriormente, y sea el número de rotámeros en cada posición (esto suele ser constante en todas las posiciones, aunque no necesariamente). Cada matriz de autoenergía para una posición dada requiere entradas, por lo que el número total de autoenergías a almacenar es . Cada matriz de energía de pares entre dos posiciones y , para rotámeros discretos en cada posición, requiere una matriz. Esto hace que el número total de entradas en una matriz de pares no reducida sea . Esto se puede recortar un poco, a costa de una complejidad adicional en la implementación, porque las energías de pares son simétricas y la energía de pares entre un rotámero y él mismo es cero. ${\displaystyle N}$ ${\displaystyle N}$ ${\displaystyle p}$ ${\displaystyle p}$ ${\displaystyle Np}$ ${\displaystyle r_{k}}$ ${\displaystyle r_{l}}$ ${\displaystyle p}$ ${\displaystyle p\times p}$ ${\displaystyle N^{2}p^{2}}$

Implementación y eficiencia

Los dos criterios anteriores se aplican normalmente de forma iterativa hasta la convergencia, definida como el punto en el que ya no se pueden eliminar más rotámeros ni pares. Dado que normalmente se trata de una reducción del espacio muestral de muchos órdenes de magnitud, bastará una enumeración simple para determinar el mínimo dentro de este conjunto reducido.

Dado este modelo, resulta claro que el algoritmo DEE garantiza encontrar la solución óptima; es decir, es un proceso de optimización global . La búsqueda de un solo rotámero escala cuadráticamente en el tiempo con el número total de rotámeros. La búsqueda de pares escala cúbicamente y es la parte más lenta del algoritmo (aparte de los cálculos de energía). Esta es una mejora espectacular con respecto a la enumeración de fuerza bruta, que escala como . ${\displaystyle O(p^{N})}$

Un estudio comparativo a gran escala de DEE comparado con métodos alternativos de predicción y diseño de la estructura de proteínas revela que DEE converge de manera confiable a la solución óptima para las longitudes de proteínas para las que se ejecuta en una cantidad de tiempo razonable ^[2] . Supera significativamente las alternativas en consideración, que involucraban técnicas derivadas de la teoría del campo medio , algoritmos genéticos y el método de Monte Carlo . Sin embargo, los otros algoritmos son apreciablemente más rápidos que DEE y, por lo tanto, se pueden aplicar a problemas más grandes y complejos; su precisión relativa se puede extrapolar a partir de una comparación con la solución DEE dentro del alcance de los problemas accesibles a DEE.

Diseño de proteínas

La discusión anterior supuso implícitamente que los rotámeros son todas orientaciones diferentes de la misma cadena lateral de aminoácidos. Es decir, se supuso que la secuencia de la proteína era fija. También es posible permitir que múltiples cadenas laterales "comitan" por una posición al incluir ambos tipos de cadenas laterales en el conjunto de rotámeros para esa posición. Esto permite que se diseñe una secuencia novedosa en una estructura proteica dada. Un pliegue proteico de dedo de zinc corto se ha rediseñado de esta manera ^[3] . Sin embargo, esto aumenta en gran medida el número de rotámeros por posición y aún requiere una longitud de proteína fija. ${\displaystyle r_{k}}$ ${\displaystyle k}$

Generalizaciones

Se han introducido criterios más potentes y más generales que mejoran tanto la eficiencia como el poder de eliminación del método para aplicaciones tanto de predicción como de diseño. Un ejemplo es un refinamiento del criterio de eliminación de simples conocido como criterio de Goldstein ^[4] , que surge de una manipulación algebraica bastante sencilla antes de aplicar la minimización:

${\displaystyle E_{k}(r_{k}^{A})-E_{k}(r_{k}^{B})+\sum _{l=1}^{N}\min _{X}\left(E_{kl}(r_{k}^{A},r_{l}^{X})-E_{kl}(r_{k}^{B},r_{l}^{X})\right)>0}$

Por lo tanto, el rotámero puede eliminarse si cualquier rotámero alternativo del conjunto en contribuye menos a la energía total que . Esto es una mejora con respecto al criterio original, que requiere la comparación de la mejor contribución de energía posible (es decir, la más pequeña) de con la peor contribución posible de un rotámero alternativo. ${\displaystyle r_{k}^{A}}$ ${\displaystyle r_{k}}$ ${\displaystyle r_{k}^{A}}$ ${\displaystyle r_{k}^{A}}$

^{En [5]} se puede encontrar una discusión más extensa de los criterios DEE elaborados y un punto de referencia de su desempeño relativo .

Referencias

1. https://www.nobelprize.org/uploads/2024/10/advanced-chemistryprize2024.pdf

1. ^ Desmet J, de Maeyer M, Hazes B, Lasters I. (1992). El teorema de eliminación de callejón sin salida y su uso en el posicionamiento de la cadena lateral de proteínas. Nature , 356 , 539-542. PMID  21488406.
2. ^ Voigt CA, Gordon DB, Mayo SL. (2000). Intercambio de precisión por velocidad: una comparación cuantitativa de algoritmos de búsqueda en el diseño de secuencias de proteínas. J Mol Biol 299(3):789-803.
3. ^ Dahiyat BI, Mayo SL. (1997). Diseño de proteínas de novo: selección de secuencias totalmente automatizada. Ciencia 278(5335):82-7.
4. ^ Goldstein RF. (1994). Eliminación eficiente de rotámeros aplicada a cadenas laterales de proteínas y vidrios de espín relacionados. Biophys J 66(5):1335-40.
5. ^ Pierce NA, Spriet JA, Desmet J, Mayo SL. (2000). División conformacional: un criterio más poderoso para la eliminación de extremos muertos. J Comput Chem 21: 999-1009.