En química computacional , un algoritmo de restricción es un método para satisfacer el movimiento newtoniano de un cuerpo rígido que consta de puntos de masa. Un algoritmo de restricción se utiliza para garantizar que se mantenga la distancia entre los puntos de masa. Los pasos generales involucrados son: (i) elegir nuevas coordenadas no restringidas (coordenadas internas), (ii) introducir fuerzas de restricción explícitas, (iii) minimizar las fuerzas de restricción implícitamente mediante la técnica de multiplicadores de Lagrange o métodos de proyección.
Los algoritmos de restricción se aplican a menudo a simulaciones de dinámica molecular . Aunque a veces dichas simulaciones se realizan utilizando coordenadas internas que satisfacen automáticamente las restricciones de longitud de enlace, ángulo de enlace y ángulo de torsión, también se pueden realizar simulaciones utilizando fuerzas de restricción explícitas o implícitas para estas tres restricciones. Sin embargo, las fuerzas de restricción explícitas dan lugar a ineficiencia; se requiere más potencia computacional para obtener una trayectoria de una longitud determinada. Por lo tanto, generalmente se prefieren las coordenadas internas y los solucionadores de restricciones de fuerza implícita.
Los algoritmos de restricción logran eficiencia computacional al descuidar el movimiento a lo largo de algunos grados de libertad. Por ejemplo, en dinámica molecular atomística, normalmente la longitud de los enlaces covalentes al hidrógeno está restringida; sin embargo, no se deben utilizar algoritmos de restricción si las vibraciones a lo largo de estos grados de libertad son importantes para el fenómeno que se está estudiando.
El movimiento de un conjunto de N partículas se puede describir mediante un conjunto de ecuaciones diferenciales ordinarias de segundo orden, la segunda ley de Newton, que se puede escribir en forma matricial.
donde M es una matriz de masas y q es el vector de coordenadas generalizadas que describen las posiciones de las partículas. Por ejemplo, el vector q puede ser una matriz cartesiana de 3N de las posiciones de las partículas r k , donde k va de 1 a N ; en ausencia de restricciones, M sería la matriz cuadrada diagonal de 3N x 3N de las masas de las partículas. El vector f representa las fuerzas generalizadas y el escalar V ( q ) representa la energía potencial, ambas funciones de las coordenadas generalizadas q .
Si existen M restricciones, las coordenadas también deben satisfacer M ecuaciones algebraicas independientes del tiempo
donde el índice j va de 1 a M . Para abreviar, estas funciones g i se agrupan en un vector g de dimensión M a continuación. La tarea consiste en resolver el conjunto combinado de ecuaciones diferenciales algebraicas (DAE), en lugar de solo las ecuaciones diferenciales ordinarias (EDO) de la segunda ley de Newton.
Este problema fue estudiado en detalle por Joseph Louis Lagrange , quien expuso la mayoría de los métodos para resolverlo. [1] El enfoque más simple es definir nuevas coordenadas generalizadas que no tengan restricciones; este enfoque elimina las ecuaciones algebraicas y reduce el problema una vez más a la solución de una ecuación diferencial ordinaria. Este enfoque se utiliza, por ejemplo, para describir el movimiento de un cuerpo rígido; la posición y la orientación de un cuerpo rígido se pueden describir mediante seis coordenadas independientes y sin restricciones, en lugar de describir las posiciones de las partículas que lo componen y las restricciones entre ellas que mantienen sus distancias relativas. El inconveniente de este enfoque es que las ecuaciones pueden volverse difíciles de manejar y complejas; por ejemplo, la matriz de masa M puede volverse no diagonal y depender de las coordenadas generalizadas.
Un segundo enfoque consiste en introducir fuerzas explícitas que trabajen para mantener la restricción; por ejemplo, se podrían introducir fuerzas de resorte fuertes que impongan las distancias entre los puntos de masa dentro de un cuerpo "rígido". Las dos dificultades de este enfoque son que las restricciones no se satisfacen exactamente y las fuerzas fuertes pueden requerir pasos de tiempo muy cortos, lo que hace que las simulaciones sean ineficientes desde el punto de vista computacional.
Un tercer enfoque es utilizar un método como los multiplicadores de Lagrange o la proyección a la variedad de restricciones para determinar los ajustes de coordenadas necesarios para satisfacer las restricciones.
Por último, existen varios enfoques híbridos en los que se satisfacen diferentes conjuntos de restricciones mediante diferentes métodos, por ejemplo, coordenadas internas, fuerzas explícitas y soluciones de fuerza implícita.
El enfoque más simple para satisfacer las restricciones en la minimización de la energía y la dinámica molecular es representar el sistema mecánico en las llamadas coordenadas internas que corresponden a los grados de libertad independientes sin restricciones del sistema. Por ejemplo, los ángulos diedros de una proteína son un conjunto independiente de coordenadas que especifican las posiciones de todos los átomos sin requerir ninguna restricción. La dificultad de estos enfoques de coordenadas internas es doble: las ecuaciones de movimiento newtonianas se vuelven mucho más complejas y las coordenadas internas pueden ser difíciles de definir para sistemas cíclicos de restricciones, por ejemplo, en el fruncimiento de anillos o cuando una proteína tiene un enlace disulfuro.
Los métodos originales para la minimización eficiente de la energía recursiva en coordenadas internas fueron desarrollados por Gō y colaboradores. [2] [3]
Los solucionadores de restricciones de coordenadas internas, recursivos y eficientes se extendieron a la dinámica molecular. [4] [5] Métodos análogos se aplicaron posteriormente a otros sistemas. [6] [7] [8]
En la mayoría de las simulaciones de dinámica molecular que utilizan algoritmos de restricción, las restricciones se aplican mediante el método de multiplicadores de Lagrange. Dado un conjunto de n restricciones lineales ( holonómicas ) en el momento t ,
donde y son las posiciones de las dos partículas involucradas en la restricción k en el tiempo t y es la distancia entre partículas prescrita.
Las fuerzas debidas a estas restricciones se suman en las ecuaciones de movimiento, lo que da como resultado, para cada una de las N partículas en el sistema
La suma de las fuerzas de restricción no modifica la energía total, ya que el trabajo neto realizado por las fuerzas de restricción (tomado sobre el conjunto de partículas sobre las que actúan las restricciones) es cero. Nótese que el signo es arbitrario y algunas referencias [9] tienen un signo opuesto.
Al integrar ambos lados de la ecuación con respecto al tiempo, se dan las coordenadas restringidas de las partículas en el tiempo,
donde es la posición sin restricciones (o sin corregir) de la i -ésima partícula después de integrar las ecuaciones de movimiento sin restricciones.
Para satisfacer las restricciones en el siguiente paso de tiempo, los multiplicadores de Lagrange deben determinarse como la siguiente ecuación,
Esto implica resolver un sistema de ecuaciones no lineales.
simultáneamente para los multiplicadores de Lagrange desconocidos .
Este sistema de ecuaciones no lineales con incógnitas se resuelve comúnmente utilizando el método de Newton-Raphson, donde el vector solución se actualiza utilizando
¿Dónde está el jacobiano de las ecuaciones σ k :
Dado que no todas las partículas contribuyen a todas las restricciones, es una matriz de bloques y se puede resolver individualmente para obtener la unidad de bloques de la matriz. En otras palabras, se puede resolver individualmente para cada molécula.
En lugar de actualizar constantemente el vector , la iteración puede iniciarse con , lo que da como resultado expresiones más simples para y . En este caso
luego se actualiza a
Después de cada iteración, las posiciones de partículas sin restricciones se actualizan utilizando
A continuación, el vector se restablece a
El procedimiento anterior se repite hasta que la solución de las ecuaciones de restricción, , converge a una tolerancia prescrita de un error numérico.
Aunque existen varios algoritmos para calcular los multiplicadores de Lagrange, estas diferencias dependen únicamente de los métodos para resolver el sistema de ecuaciones. Para estos métodos, se utilizan comúnmente los métodos cuasi-Newton .
El algoritmo SETTLE [10] resuelve el sistema de ecuaciones no lineales analíticamente para restricciones en tiempo constante. Aunque no se puede escalar a un mayor número de restricciones, se utiliza muy a menudo para restringir las moléculas de agua rígidas, que están presentes en casi todas las simulaciones biológicas y que suelen modelarse utilizando tres restricciones (por ejemplo, los modelos de agua SPC/E y TIP3P ).
El algoritmo SHAKE se desarrolló inicialmente para satisfacer una restricción de geometría de enlace durante simulaciones de dinámica molecular. [11] Luego, el método se generalizó para manejar cualquier restricción holonómica, como las requeridas para mantener ángulos de enlace constantes o rigidez molecular. [12]
En el algoritmo SHAKE, el sistema de ecuaciones de restricción no lineal se resuelve utilizando el método de Gauss-Seidel , que aproxima la solución del sistema lineal de ecuaciones utilizando el método de Newton-Raphson ;
Esto equivale a suponer que es diagonalmente dominante y resolver la ecuación sólo para la incógnita. En la práctica, calculamos
para todos iterativamente hasta que las ecuaciones de restricción se resuelvan a una tolerancia dada.
El coste de cálculo de cada iteración es , y las iteraciones en sí convergen linealmente.
Posteriormente se desarrolló una forma no iterativa de SHAKE. [13]
Existen varias variantes del algoritmo SHAKE. Si bien difieren en la forma en que calculan o aplican las restricciones, estas se modelan utilizando multiplicadores de Lagrange que se calculan mediante el método de Gauss-Seidel.
El algoritmo SHAKE original es capaz de restringir tanto moléculas rígidas como flexibles (por ejemplo, agua, benceno y bifenilo ) e introduce un error insignificante o una deriva de energía en una simulación de dinámica molecular. [14] Un problema con SHAKE es que el número de iteraciones necesarias para alcanzar un cierto nivel de convergencia aumenta a medida que la geometría molecular se vuelve más compleja. Para alcanzar una precisión de computadora de 64 bits (una tolerancia relativa de ) en una simulación de dinámica molecular típica a una temperatura de 310 K, un modelo de agua de 3 sitios que tiene 3 restricciones para mantener la geometría molecular requiere un promedio de 9 iteraciones (que es 3 por sitio por paso de tiempo). Un modelo de butano de 4 sitios con 5 restricciones necesita 17 iteraciones (22 por sitio), un modelo de benceno de 6 sitios con 12 restricciones necesita 36 iteraciones (72 por sitio), mientras que un modelo de bifenilo de 12 sitios con 29 restricciones requiere 92 iteraciones (229 por sitio por paso de tiempo). [14] Por lo tanto, los requisitos de CPU del algoritmo SHAKE pueden llegar a ser significativos, particularmente si un modelo molecular tiene un alto grado de rigidez.
Una extensión posterior del método, QSHAKE ( Quaternion SHAKE), se desarrolló como una alternativa más rápida para moléculas compuestas de unidades rígidas, pero no es de uso general. [15] Funciona satisfactoriamente para bucles rígidos como los sistemas de anillos aromáticos , pero QSHAKE falla para bucles flexibles, como cuando una proteína tiene un enlace disulfuro. [16]
Otras extensiones incluyen RATTLE, [17] WIGGLE, [18] y MSHAKE. [19]
Si bien RATTLE funciona de la misma manera que SHAKE, [20] pero utilizando el esquema de integración temporal de Velocity Verlet , WIGGLE extiende SHAKE y RATTLE al utilizar una estimación inicial para los multiplicadores de Lagrange basados en las velocidades de las partículas. Vale la pena mencionar que MSHAKE calcula correcciones en las fuerzas de restricción , logrando una mejor convergencia.
Una modificación final del algoritmo SHAKE es el algoritmo P-SHAKE [21] que se aplica a moléculas muy rígidas o semirrígidas . P-SHAKE calcula y actualiza un preacondicionador que se aplica a los gradientes de restricción antes de la iteración SHAKE, lo que hace que el jacobiano se vuelva diagonal o fuertemente diagonalmente dominante. Las restricciones así desacopladas convergen mucho más rápido (cuadráticamente en lugar de linealmente) a un costo de .
El algoritmo M-SHAKE [22] resuelve el sistema de ecuaciones no lineales utilizando directamente el método de Newton . En cada iteración, el sistema de ecuaciones lineales
se resuelve exactamente usando una descomposición LU . Cada iteración cuesta operaciones, pero la solución converge cuadráticamente , requiriendo menos iteraciones que SHAKE.
Esta solución fue propuesta por primera vez en 1986 por Ciccotti y Ryckaert [12] bajo el título "el método matricial", pero difería en la solución del sistema lineal de ecuaciones. Ciccotti y Ryckaert sugieren invertir la matriz directamente, pero hacerlo solo una vez, en la primera iteración. La primera iteración entonces cuesta operaciones, mientras que las iteraciones siguientes cuestan solo operaciones (para la multiplicación matriz-vector). Sin embargo, esta mejora tiene un costo, ya que el jacobiano ya no se actualiza, la convergencia es solo lineal , aunque a una velocidad mucho más rápida que para el algoritmo SHAKE.
Barth et al. estudiaron varias variantes de este enfoque basadas en técnicas de matriz dispersa . [23]
El algoritmo SHAPE [24] es un análogo multicéntrico de SHAKE para restringir cuerpos rígidos de tres o más centros. Al igual que SHAKE, se realiza un paso sin restricciones y luego se corrige calculando y aplicando directamente la matriz de rotación del cuerpo rígido que satisface:
Este enfoque implica una única diagonalización de la matriz 3×3 seguida de tres o cuatro iteraciones rápidas de Newton para determinar la matriz de rotación. SHAPE proporciona la misma trayectoria que se proporciona con SHAKE iterativo completamente convergente, pero se ha descubierto que es más eficiente y más preciso que SHAKE cuando se aplica a sistemas que involucran tres o más centros. Amplía la capacidad de las restricciones como SHAKE a sistemas lineales con tres o más átomos, sistemas planos con cuatro o más átomos y a estructuras rígidas significativamente más grandes donde SHAKE es intratable. También permite vincular cuerpos rígidos con uno o dos centros comunes (por ejemplo, planos de péptidos) al resolver restricciones de cuerpos rígidos de manera iterativa de la misma manera básica en que SHAKE se usa para átomos que involucran más de una restricción SHAKE.
Un método de restricción alternativo, LINCS (Linear Constraint Solver), fue desarrollado en 1997 por Hess, Bekker, Berendsen y Fraaije, [25] y se basó en el método de 1986 de Edberg, Evans y Morriss (EEM), [26] y una modificación del mismo de Baranyai y Evans (BE). [27]
LINCS aplica multiplicadores de Lagrange a las fuerzas de restricción y resuelve los multiplicadores utilizando una expansión en serie para aproximar la inversa del jacobiano :
en cada paso de la iteración de Newton. Esta aproximación solo funciona para matrices con valores propios menores que 1, lo que hace que el algoritmo LINCS sea adecuado solo para moléculas con baja conectividad.
Se ha informado que LINCS es 3 a 4 veces más rápido que SHAKE. [25]
También se han introducido métodos híbridos en los que las restricciones se dividen en dos grupos; las restricciones del primer grupo se resuelven utilizando coordenadas internas, mientras que las del segundo grupo se resuelven utilizando fuerzas de restricción, por ejemplo, mediante un multiplicador de Lagrange o un método de proyección. [28] [29] [30] Este enfoque fue iniciado por Lagrange, [1] y da como resultado ecuaciones de Lagrange del tipo mixto . [31]