Hispanopedia Wiki
Articulo de referencia

Eliminación de callejón sin salida

El algoritmo de eliminación de callejones sin salida ( DEE, por sus siglas en inglés) es un método para minimizar una función sobre un conjunto discreto de variables independien...

Hispanopedia WikiContenido en espanolLectura gratuita

El algoritmo de eliminación de callejones sin salida ( DEE, por sus siglas en inglés) 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, ya que siempre existe una forma de reemplazarlas por una mejor o equivalente. De esta manera, podemos abstenernos de seguir buscando dichas combinaciones. Por lo tanto, la eliminación de callejones sin salida es la imagen especular de la programación dinámica , en la que se identifican y exploran 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 estructuras de proteínas (y de esta manera fue citado en los Antecedentes Científicos del Premio Nobel de Química 2024 ). [ 1 ] Está estrechamente relacionado con la noción de dominancia en optimización, también conocida como sustituibilidad en un problema de satisfacción de restricciones . La descripción y demostración original del teorema de eliminación de callejones sin salida se puede encontrar en.

Requisitos básicos

Una implementación eficaz de DEE requiere cuatro datos:

  1. Un conjunto finito bien definido de variables independientes discretas
  2. Un valor numérico precalculado (considerado la "energía") asociado a cada elemento del conjunto de variables (y posiblemente a sus pares, tríos, 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 de energía") que debe minimizarse.

Cabe señalar que los criterios pueden invertirse fácilmente para identificar también el máximo de una función dada.

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

La eliminación de callejones sin salida se ha utilizado eficazmente para predecir la estructura de las cadenas laterales en una estructura de esqueleto proteico dada , minimizando una función de energía.mi{\displaystyle E}El espacio de búsqueda del ángulo diedro de las cadenas laterales se restringe 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 puede ampliarse.

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

miTOT=∑kmik(rk)+∑k≠lmikl(rk,rl){\displaystyle E_{TOT}=\sum _ {k}E_ {k}(r_ {k})+\sum _ {k\neq l}E_ {kl}(r_ {k},r_ {l})\,}

Dóndemik(rk){\displaystyle E_{k}(r_{k})}representa la " autoenergía " de un rotámero en particularrk{\displaystyle r_{k}}, ymikl(rk,rl){\displaystyle E_{kl}(r_{k},r_{l})}representa la "energía de pares" de los rotámerosrk,rj{\displaystyle r_{k},r_{j}}.

Tenga en cuenta también quemikk(rkA,rkA){\displaystyle E_{kk}(r_{k}^{A},r_{k}^{A})}(Es decir, la energía de interacción entre un rotámero y sí mismo) se considera cero y, por lo tanto, no afecta a las sumas. Esta notación simplifica la descripción del criterio de pares que se presenta a continuación.

Criterio de eliminación de solteros

Si un rotámero en particularrkA{\displaystyle r_{k}^{A}}de cadena lateralk{\displaystyle k}No puede proporcionar una energía mejor que otro rotámero.rkB{\displaystyle r_{k}^{B}}Si la cadena lateral es la misma, 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

mik(rkA)+∑l=1norteminincógnitamikl(rkA,rlincógnita)>mik(rkB)+∑l=1nortemáximoincógnitamikl(rkB,rlincógnita){\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})}

dóndeminincógnitamikl(rkA,rlincógnita){\displaystyle \min _{X}E_{kl}(r_{k}^{A},r_{l}^{X})}es la energía mínima (mejor) posible entre rotámerosrkA{\displaystyle r_{k}^{A}}de cadena lateralk{\displaystyle k}y cualquier rotámero X de cadena laterall{\displaystyle l}. Similarmente,máximoincógnitamikl(rkB,rlincógnita){\displaystyle \max _{X}E_{kl}(r_{k}^{B},r_{l}^{X})}es la energía máxima (peor) posible entre rotámerosrkB{\displaystyle r_{k}^{B}}de cadena lateralk{\displaystyle k}y cualquier rotámero X de cadena laterall{\displaystyle l}.

Criterio de eliminación de pares

El criterio de pares es más difícil de describir e implementar, pero añade un poder de eliminación significativo. Para mayor brevedad, definimos la variable abreviada.UklAB{\displaystyle U_{kl}^{AB}}esa es la energía intrínseca de un par de rotámerosA{\displaystyle A}yB{\displaystyle B}en posicionesk{\displaystyle k}yl{\displaystyle l}respectivamente

UklAB =dmiF mik(rkA)+mil(rlB)+mikl(rkA,rlB){\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 de rotámeros dadoA{\displaystyle A}yB{\displaystyle B}en posicionesk{\displaystyle k}yl{\displaystyle l}, respectivamente, no pueden estar ambos en la solución final (aunque uno u otro sí puede estarlo) si hay otro pardo{\displaystyle C}yD{\displaystyle D}Eso siempre da mejor energía. Expresado matemáticamente,

UklAB+∑i=1norteminincógnita(miki(rkA,riincógnita)+milj(rlB,rjincógnita))>UkldoD+∑i=1nortemáximoincógnita(miki(rkdo,riincógnita)+milj(rlD,rjincógnita)){\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)}

dóndeA≠do{\displaystyle A\neq C},B≠D{\displaystyle B\neq D}yk≠l{\displaystyle k\neq l}.

Matrices de energía

Para grandesnorte{\displaystyle N}Las matrices de energías precalculadas pueden resultar costosas de almacenar.norte{\displaystyle N}sea ​​el número de posiciones de aminoácidos, como se indicó anteriormente, y seapag{\displaystyle p}sea ​​el número de rotámeros en cada posición (esto suele ser, pero no necesariamente, constante en todas las posiciones). Cada matriz de autoenergía para una posición dada requierepag{\displaystyle p}entradas, por lo que el número total de autoenergías a almacenar esnortepag{\displaystyle Np}. Cada matriz de energía de par entre dos posicionesrk{\displaystyle r_{k}}yrl{\displaystyle r_{l}}, parapag{\displaystyle p}rotámeros discretos en cada posición, requiere unpag×pag{\displaystyle p\times p}matriz. Esto hace que el número total de entradas en una matriz de pares no reducida sea igual a...norte2pag2{\displaystyle N^{2}p^{2}}Esto se puede simplificar un poco, a costa de una mayor complejidad en la implementación, porque las energías de los pares son simétricas y la energía de par entre un rotámero y sí mismo es cero.

Implementación y eficiencia

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

Dado este modelo, es evidente que el algoritmo DEE garantiza encontrar la solución óptima; es decir, se trata de un proceso de optimización global . La búsqueda de un solo rotámero escala cuadráticamente en 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). Esto supone una mejora drástica con respecto a la enumeración por fuerza bruta, que escala comoO(pagnorte){\displaystyle O(p^{N})}.

Una evaluación comparativa a gran escala de DEE con métodos alternativos de predicción y diseño de estructuras proteicas revela que DEE converge de manera fiable a la solución óptima para longitudes de proteína para las que se ejecuta en un tiempo razonable.Supera significativamente a las alternativas consideradas, que incluían técnicas derivadas de la teoría de campo medio , algoritmos genéticos y el método de Monte Carlo . Sin embargo, los otros algoritmos son considerablemente más rápidos que DEE y, por lo tanto, pueden aplicarse a problemas más grandes y complejos; su precisión relativa puede extrapolarse a partir de una comparación con la solución de DEE dentro del ámbito de problemas accesibles para DEE.

Diseño de proteínas

La discusión anterior asumió implícitamente que los rotámerosrk{\displaystyle r_{k}}son todas orientaciones diferentes de la misma cadena lateral de aminoácido. Es decir, se asumió que la secuencia de la proteína era fija. También es posible permitir que múltiples cadenas laterales "compitan" por una posición.k{\displaystyle k}al incluir ambos tipos de cadenas laterales en el conjunto de rotámeros para esa posición. Esto permite diseñar una secuencia novedosa en una estructura proteica determinada. De esta manera se ha rediseñado un plegamiento proteico corto con dedos de zinc.Sin embargo, esto aumenta considerablemente el número de rotámeros por posición y aún requiere una longitud de proteína fija.

Generalizaciones

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

mik(rkA)−mik(rkB)+∑l=1norteminincógnita(mikl(rkA,rlincógnita)−mikl(rkB,rlincógnita))>0{\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, rotámerorkA{\displaystyle r_{k}^{A}}puede eliminarse si cualquier rotámero alternativo del conjunto enrk{\displaystyle r_{k}}contribuye menos a la energía total querkA{\displaystyle r_{k}^{A}}. Esto supone una mejora respecto al criterio original, que requiere la comparación de la mejor contribución energética posible (es decir, la más pequeña) derkA{\displaystyle r_{k}^{A}}con la peor contribución posible de un rotámero alternativo.

Una discusión ampliada de los elaborados criterios DEE y una evaluación comparativa de su rendimiento relativo se puede encontrar en.

Referencias

  1. ↑ Antecedentes científicos del Premio Nobel de Química 2024: Diseño computacional de proteínas y predicción de la estructura de las proteínas (PDF) , Real Academia Sueca de Ciencias, 9 de octubre de 2024
  1. ^ Desmet, J; de Maeyer, M; Hazes, B; Lasters, I (1992). "El teorema de eliminación de callejones sin salida y su uso en el posicionamiento de cadenas laterales de proteínas". Nature . 356 : 539–542 . PMID 21488406 . 
  2. ^ Voigt, CA; Gordon, DB; Mayo, SL (2000). "Intercambiando 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 secuencia 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 potente para la eliminación de callejones sin salida". J Comput Chem . 21 : 999–1009 .