fbpx
Wikipedia

Constraint (computational chemistry)

In computational chemistry, a constraint algorithm is a method for satisfying the Newtonian motion of a rigid body which consists of mass points. A restraint algorithm is used to ensure that the distance between mass points is maintained. The general steps involved are: (i) choose novel unconstrained coordinates (internal coordinates), (ii) introduce explicit constraint forces, (iii) minimize constraint forces implicitly by the technique of Lagrange multipliers or projection methods.

Constraint algorithms are often applied to molecular dynamics simulations. Although such simulations are sometimes performed using internal coordinates that automatically satisfy the bond-length, bond-angle and torsion-angle constraints, simulations may also be performed using explicit or implicit constraint forces for these three constraints. However, explicit constraint forces give rise to inefficiency; more computational power is required to get a trajectory of a given length. Therefore, internal coordinates and implicit-force constraint solvers are generally preferred.

Constraint algorithms achieve computational efficiency by neglecting motion along some degrees of freedom. For instance, in atomistic molecular dynamics, typically the length of covalent bonds to hydrogen are constrained; however, constraint algorithms should not be used if vibrations along these degrees of freedom are important for the phenomenon being studied.

Mathematical background edit

The motion of a set of N particles can be described by a set of second-order ordinary differential equations, Newton's second law, which can be written in matrix form

 

where M is a mass matrix and q is the vector of generalized coordinates that describe the particles' positions. For example, the vector q may be a 3N Cartesian coordinates of the particle positions rk, where k runs from 1 to N; in the absence of constraints, M would be the 3Nx3N diagonal square matrix of the particle masses. The vector f represents the generalized forces and the scalar V(q) represents the potential energy, both of which are functions of the generalized coordinates q.

If M constraints are present, the coordinates must also satisfy M time-independent algebraic equations

 

where the index j runs from 1 to M. For brevity, these functions gi are grouped into an M-dimensional vector g below. The task is to solve the combined set of differential-algebraic (DAE) equations, instead of just the ordinary differential equations (ODE) of Newton's second law.

This problem was studied in detail by Joseph Louis Lagrange, who laid out most of the methods for solving it.[1] The simplest approach is to define new generalized coordinates that are unconstrained; this approach eliminates the algebraic equations and reduces the problem once again to solving an ordinary differential equation. Such an approach is used, for example, in describing the motion of a rigid body; the position and orientation of a rigid body can be described by six independent, unconstrained coordinates, rather than describing the positions of the particles that make it up and the constraints among them that maintain their relative distances. The drawback of this approach is that the equations may become unwieldy and complex; for example, the mass matrix M may become non-diagonal and depend on the generalized coordinates.

A second approach is to introduce explicit forces that work to maintain the constraint; for example, one could introduce strong spring forces that enforce the distances among mass points within a "rigid" body. The two difficulties of this approach are that the constraints are not satisfied exactly, and the strong forces may require very short time-steps, making simulations inefficient computationally.

A third approach is to use a method such as Lagrange multipliers or projection to the constraint manifold to determine the coordinate adjustments necessary to satisfy the constraints.

Finally, there are various hybrid approaches in which different sets of constraints are satisfied by different methods, e.g., internal coordinates, explicit forces and implicit-force solutions.

Internal coordinate methods edit

The simplest approach to satisfying constraints in energy minimization and molecular dynamics is to represent the mechanical system in so-called internal coordinates corresponding to unconstrained independent degrees of freedom of the system. For example, the dihedral angles of a protein are an independent set of coordinates that specify the positions of all the atoms without requiring any constraints. The difficulty of such internal-coordinate approaches is twofold: the Newtonian equations of motion become much more complex and the internal coordinates may be difficult to define for cyclic systems of constraints, e.g., in ring puckering or when a protein has a disulfide bond.

The original methods for efficient recursive energy minimization in internal coordinates were developed by Gō and coworkers.[2][3]

Efficient recursive, internal-coordinate constraint solvers were extended to molecular dynamics.[4][5] Analogous methods were applied later to other systems.[6][7][8]

Lagrange multiplier-based methods edit

 
Resolving the constraints of a rigid water molecule using Lagrange multipliers: a) the unconstrained positions are obtained after a simulation time-step, b) the gradients of each constraint over each particle are computed and c) the Lagrange multipliers are computed for each gradient such that the constraints are satisfied.

In most of molecular dynamics simulations that use constraint algorithms, constraints are enforced using the method of Lagrange multipliers. Given a set of n linear (holonomic) constraints at the time t,

 

where   and   are the positions of the two particles involved in the kth constraint at the time t and   is the prescribed inter-particle distance.

The forces due to these constraints are added in the equations of motion, resulting in, for each of the N particles in the system

 

Adding the constraint forces does not change the total energy, as the net work done by the constraint forces (taken over the set of particles that the constraints act on) is zero. Note that the sign on   is arbitrary and some references[9] have an opposite sign.

From integrating both sides of the equation with respect to the time, the constrained coordinates of particles at the time,  , are given,

 

where   is the unconstrained (or uncorrected) position of the ith particle after integrating the unconstrained equations of motion.

To satisfy the constraints   in the next timestep, the Lagrange multipliers should be determined as the following equation,

 

This implies solving a system of   non-linear equations

 

simultaneously for the   unknown Lagrange multipliers  .

This system of   non-linear equations in   unknowns is commonly solved using Newton–Raphson method where the solution vector   is updated using

 

where   is the Jacobian of the equations σk:

 

Since not all particles contribute to all of constraints,   is a block matrix and can be solved individually to block-unit of the matrix. In other words,   can be solved individually for each molecule.

Instead of constantly updating the vector  , the iteration can be started with  , resulting in simpler expressions for   and  . In this case

 

then   is updated to

 

After each iteration, the unconstrained particle positions are updated using

 

The vector is then reset to

 

The above procedure is repeated until the solution of constraint equations,  , converges to a prescribed tolerance of a numerical error.

Although there are a number of algorithms to compute the Lagrange multipliers, these difference is rely only on the methods to solve the system of equations. For this methods, quasi-Newton methods are commonly used.

The SETTLE algorithm edit

The SETTLE algorithm[10] solves the system of non-linear equations analytically for   constraints in constant time. Although it does not scale to larger numbers of constraints, it is very often used to constrain rigid water molecules, which are present in almost all biological simulations and are usually modelled using three constraints (e.g. SPC/E and TIP3P water models).

The SHAKE algorithm edit

The SHAKE algorithm was first developed for satisfying a bond geometry constraint during molecular dynamics simulations.[11] The method was then generalised to handle any holonomic constraint, such as those required to maintain constant bond angles, or molecular rigidity.[12]

In SHAKE algorithm, the system of non-linear constraint equations is solved using the Gauss–Seidel method which approximates the solution of the linear system of equations using the Newton–Raphson method;

 

This amounts to assuming that   is diagonally dominant and solving the  th equation only for the   unknown. In practice, we compute

 

for all   iteratively until the constraint equations   are solved to a given tolerance.

The calculation cost of each iteration is  , and the iterations themselves converge linearly.

A noniterative form of SHAKE was developed later on.[13]

Several variants of the SHAKE algorithm exist. Although they differ in how they compute or apply the constraints themselves, the constraints are still modelled using Lagrange multipliers which are computed using the Gauss–Seidel method.

The original SHAKE algorithm is capable of constraining both rigid and flexible molecules (eg. water, benzene and biphenyl) and introduces negligible error or energy drift into a molecular dynamics simulation.[14] One issue with SHAKE is that the number of iterations required to reach a certain level of convergence does rise as molecular geometry becomes more complex. To reach 64 bit computer accuracy (a relative tolerance of  ) in a typical molecular dynamics simulation at a temperature of 310K, a 3-site water model having 3 constraints to maintain molecular geometry requires an average of 9 iterations (which is 3 per site per time-step). A 4-site butane model with 5 constraints needs 17 iterations (22 per site), a 6-site benzene model with 12 constraints needs 36 iterations (72 per site), while a 12-site biphenyl model with 29 constraints requires 92 iterations (229 per site per time-step).[14] Hence the CPU requirements of the SHAKE algorithm can become significant, particularly if a molecular model has a high degree of rigidity.

A later extension of the method, QSHAKE (Quaternion SHAKE) was developed as a faster alternative for molecules composed of rigid units, but it is not as general purpose.[15] It works satisfactorily for rigid loops such as aromatic ring systems but QSHAKE fails for flexible loops, such as when a protein has a disulfide bond.[16]

Further extensions include RATTLE,[17] WIGGLE,[18] and MSHAKE.[19]

While RATTLE works the same way as SHAKE,[20] yet using the Velocity Verlet time integration scheme, WIGGLE extends SHAKE and RATTLE by using an initial estimate for the Lagrange multipliers   based on the particle velocities. It is worth mentioning that MSHAKE computes corrections on the constraint forces, achieving better convergence.

A final modification to the SHAKE algorithm is the P-SHAKE algorithm[21] that is applied to very rigid or semi-rigid molecules. P-SHAKE computes and updates a pre-conditioner which is applied to the constraint gradients before the SHAKE iteration, causing the Jacobian   to become diagonal or strongly diagonally dominant. The thus de-coupled constraints converge much faster (quadratically as opposed to linearly) at a cost of  .

The M-SHAKE algorithm edit

The M-SHAKE algorithm[22] solves the non-linear system of equations using Newton's method directly. In each iteration, the linear system of equations

 

is solved exactly using an LU decomposition. Each iteration costs   operations, yet the solution converges quadratically, requiring fewer iterations than SHAKE.

This solution was first proposed in 1986 by Ciccotti and Ryckaert[12] under the title "the matrix method", yet differed in the solution of the linear system of equations. Ciccotti and Ryckaert suggest inverting the matrix   directly, yet doing so only once, in the first iteration. The first iteration then costs   operations, whereas the following iterations cost only   operations (for the matrix-vector multiplication). This improvement comes at a cost though, since the Jacobian is no longer updated, convergence is only linear, albeit at a much faster rate than for the SHAKE algorithm.

Several variants of this approach based on sparse matrix techniques were studied by Barth et al..[23]

SHAPE algorithm edit

The SHAPE algorithm[24] is a multicenter analog of SHAKE for constraining rigid bodies of three or more centers. Like SHAKE, an unconstrained step is taken and then corrected by directly calculating and applying the rigid body rotation matrix that satisfies:

 

This approach involves a single 3×3 matrix diagonalization followed by three or four rapid Newton iterations to determine the rotation matrix. SHAPE provides the identical trajectory that is provided with fully converged iterative SHAKE, yet it is found to be more efficient and more accurate than SHAKE when applied to systems involving three or more centers. It extends the ability of SHAKE like constraints to linear systems with three or more atoms, planar systems with four or more atoms, and to significantly larger rigid structures where SHAKE is intractable. It also allows rigid bodies to be linked with one or two common centers (e.g. peptide planes) by solving rigid body constraints iteratively in the same basic manner that SHAKE is used for atoms involving more than one SHAKE constraint.

LINCS algorithm edit

An alternative constraint method, LINCS (Linear Constraint Solver) was developed in 1997 by Hess, Bekker, Berendsen and Fraaije,[25] and was based on the 1986 method of Edberg, Evans and Morriss (EEM),[26] and a modification thereof by Baranyai and Evans (BE).[27]

LINCS applies Lagrange multipliers to the constraint forces and solves for the multipliers by using a series expansion to approximate the inverse of the Jacobian  :

 

in each step of the Newton iteration. This approximation only works for matrices with eigenvalues smaller than 1, making the LINCS algorithm suitable only for molecules with low connectivity.

LINCS has been reported to be 3–4 times faster than SHAKE.[25]

Hybrid methods edit

Hybrid methods have also been introduced in which the constraints are divided into two groups; the constraints of the first group are solved using internal coordinates whereas those of the second group are solved using constraint forces, e.g., by a Lagrange multiplier or projection method.[28][29][30] This approach was pioneered by Lagrange,[1] and result in Lagrange equations of the mixed type.[31]

See also edit

References and footnotes edit

  1. ^ a b Lagrange, GL (1788). Mécanique analytique.
  2. ^ Noguti T, Toshiyuki; Gō N (1983). "A Method of Rapid Calculation of a 2nd Derivative Matrix of Conformational Energy for Large Molecules". Journal of the Physical Society of Japan. 52 (10): 3685–3690. Bibcode:1983JPSJ...52.3685N. doi:10.1143/JPSJ.52.3685.
  3. ^ Abe, H; Braun W; Noguti T; Gō N (1984). "Rapid Calculation of 1st and 2nd Derivatives of Conformational Energy with respect to Dihedral Angles for Proteins: General Recurrent Equations". Computers and Chemistry. 8 (4): 239–247. doi:10.1016/0097-8485(84)85015-9.
  4. ^ Bae, D-S; Haug EJ (1988). "A Recursive Formulation for Constrained Mechanical System Dynamics: Part I. Open Loop Systems". Mechanics of Structures and Machines. 15 (3): 359–382. doi:10.1080/08905458708905124.
  5. ^ Jain, A; Vaidehi N; Rodriguez G (1993). "A Fast Recursive Algorithm for Molecular Dynamics Simulation". Journal of Computational Physics. 106 (2): 258–268. Bibcode:1993JCoPh.106..258J. doi:10.1006/jcph.1993.1106.
  6. ^ Rice, LM; Brünger AT (1994). "Torsion Angle Dynamics: Reduced Variable Conformational Sampling Enhances Crystallographic Structure Refinement". Proteins: Structure, Function, and Genetics. 19 (4): 277–290. doi:10.1002/prot.340190403. PMID 7984624. S2CID 25080482.
  7. ^ Mathiowetz, AM; Jain A; Karasawa N; Goddard III, WA (1994). "Protein Simulations Using Techniques Suitable for Very Large Systems: The Cell Multipole Method for Nonbond Interactions and the Newton-Euler Inverse Mass Operator Method for Internal Coordinate Dynamics". Proteins: Structure, Function, and Genetics. 20 (3): 227–247. doi:10.1002/prot.340200304. PMID 7892172. S2CID 25753031.
  8. ^ Mazur, AK (1997). "Quasi-Hamiltonian Equations of Motion for Internal Coordinate Molecular Dynamics of Polymers". Journal of Computational Chemistry. 18 (11): 1354–1364. arXiv:physics/9703019. doi:10.1002/(SICI)1096-987X(199708)18:11<1354::AID-JCC3>3.0.CO;2-K.
  9. ^ Miyamoto, S; Kollman PA (1992). "SETTLE: An Analytical Version of the SHAKE and RATTLE Algorithm for Rigid Water Models". Journal of Computational Chemistry. 13 (8): 952–962. doi:10.1002/jcc.540130805. S2CID 122506495.
  10. ^ Miyamoto, S; Kollman PA (1992). "SETTLE: An Analytical Version of the SHAKE and RATTLE Algorithm for Rigid Water Models". Journal of Computational Chemistry. 13 (8): 952–962. doi:10.1002/jcc.540130805. S2CID 122506495.
  11. ^ Ryckaert, J-P; Ciccotti G; Berendsen HJC (1977). "Numerical Integration of the Cartesian Equations of Motion of a System with Constraints: Molecular Dynamics of n-Alkanes". Journal of Computational Physics. 23 (3): 327–341. Bibcode:1977JCoPh..23..327R. CiteSeerX 10.1.1.399.6868. doi:10.1016/0021-9991(77)90098-5.
  12. ^ a b Ciccotti, G.; J. P. Ryckaert (1986). "Molecular Dynamics Simulation of Rigid Molecules". Computer Physics Reports. 4 (6): 345–392. Bibcode:1986CoPhR...4..346C. doi:10.1016/0167-7977(86)90022-5.
  13. ^ Yoneya, M; Berendsen HJC; Hirasawa K (1994). "A Noniterative Matrix Method for Constraint Molecular-Dynamics Simulations". Molecular Simulations. 13 (6): 395–405. doi:10.1080/08927029408022001.
  14. ^ a b Hammonds, KD; Heyes DM (2020). "Shadow Hamiltonian in classical NVE molecular dynamics simulations: A path to long time stability". Journal of Chemical Physics. 152 (2): 024114_1–024114_15. doi:10.1063/1.5139708. PMID 31941339. S2CID 210333551.
  15. ^ Forester, TR; Smith W (1998). "SHAKE, Rattle, and Roll: Efficient Constraint Algorithms for Linked Rigid Bodies". Journal of Computational Chemistry. 19: 102–111. doi:10.1002/(SICI)1096-987X(19980115)19:1<102::AID-JCC9>3.0.CO;2-T.
  16. ^ McBride, C; Wilson MR; Howard JAK (1998). "Molecular dynamics simulations of liquid crystal phases using atomistic potentials". Molecular Physics. 93 (6): 955–964. Bibcode:1998MolPh..93..955C. doi:10.1080/002689798168655.
  17. ^ Andersen, Hans C. (1983). "RATTLE: A "Velocity" Version of the SHAKE Algorithm for Molecular Dynamics Calculations". Journal of Computational Physics. 52 (1): 24–34. Bibcode:1983JCoPh..52...24A. CiteSeerX 10.1.1.459.5668. doi:10.1016/0021-9991(83)90014-1.
  18. ^ Lee, Sang-Ho; Kim Palmo; Samuel Krimm (2005). "WIGGLE: A new constrained molecular dynamics algorithm in Cartesian coordinates". Journal of Computational Physics. 210 (1): 171–182. Bibcode:2005JCoPh.210..171L. doi:10.1016/j.jcp.2005.04.006.
  19. ^ Lambrakos, S. G.; J. P. Boris; E. S. Oran; I. Chandrasekhar; M. Nagumo (1989). "A Modified SHAKE algorithm for Maintaining Rigid Bonds in Molecular Dynamics Simulations of Large Molecules". Journal of Computational Physics. 85 (2): 473–486. Bibcode:1989JCoPh..85..473L. doi:10.1016/0021-9991(89)90160-5.
  20. ^ Leimkuhler, Benedict; Robert Skeel (1994). "Symplectic numerical integrators in constrained Hamiltonian systems". Journal of Computational Physics. 112 (1): 117–125. Bibcode:1994JCoPh.112..117L. doi:10.1006/jcph.1994.1085.
  21. ^ Gonnet, Pedro (2007). "P-SHAKE: A quadratically convergent SHAKE in  ". Journal of Computational Physics. 220 (2): 740–750. Bibcode:2007JCoPh.220..740G. doi:10.1016/j.jcp.2006.05.032.
  22. ^ Kräutler, Vincent; W. F. van Gunsteren; P. H. Hünenberger (2001). "A Fast SHAKE Algorithm to Solve Distance Constraint Equations for Small Molecules in Molecular Dynamics Simulations". Journal of Computational Chemistry. 22 (5): 501–508. doi:10.1002/1096-987X(20010415)22:5<501::AID-JCC1021>3.0.CO;2-V. S2CID 6187100.
  23. ^ Barth, Eric; K. Kuczera; B. Leimkuhler; R. Skeel (1995). "Algorithms for constrained molecular dynamics". Journal of Computational Chemistry. 16 (10): 1192–1209. doi:10.1002/jcc.540161003. S2CID 38109923.
  24. ^ Tao, Peng; Xiongwu Wu; Bernard R. Brooks (2012). "Maintain rigid structures in Verlet based Cartesian molecular dynamics simulations". The Journal of Chemical Physics. 137 (13): 134110. Bibcode:2012JChPh.137m4110T. doi:10.1063/1.4756796. PMC 3477181. PMID 23039588.
  25. ^ a b Hess, B; Bekker H; Berendsen HJC; Fraaije JGEM (1997). "LINCS: A Linear Constraint Solver for Molecular Simulations". Journal of Computational Chemistry. 18 (12): 1463–1472. CiteSeerX 10.1.1.48.2727. doi:10.1002/(SICI)1096-987X(199709)18:12<1463::AID-JCC4>3.0.CO;2-H.
  26. ^ Edberg, R; Evans DJ; Morriss GP (1986). "Constrained Molecular-Dynamics Simulations of Liquid Alkanes with a New Algorithm". Journal of Chemical Physics. 84 (12): 6933–6939. Bibcode:1986JChPh..84.6933E. doi:10.1063/1.450613.
  27. ^ Baranyai, A; Evans DJ (1990). "New Algorithm for Constrained Molecular-Dynamics Simulation of Liquid Benzene and Naphthalene". Molecular Physics. 70 (1): 53–63. Bibcode:1990MolPh..70...53B. doi:10.1080/00268979000100841.
  28. ^ Mazur, AK (1999). "Symplectic integration of closed chain rigid body dynamics with internal coordinate equations of motion". Journal of Chemical Physics. 111 (4): 1407–1414. Bibcode:1999JChPh.111.1407M. doi:10.1063/1.479399.
  29. ^ Bae, D-S; Haug EJ (1988). "A Recursive Formulation for Constrained Mechanical System Dynamics: Part II. Closed Loop Systems". Mechanics of Structures and Machines. 15 (4): 481–506. doi:10.1080/08905458708905130.
  30. ^ Rodriguez, G; Jain A; Kreutz-Delgado K (1991). "A Spatial Operator Algebra for Manipulator Modeling and Control". The International Journal of Robotics Research. 10 (4): 371–381. doi:10.1177/027836499101000406. hdl:2060/19900020578. S2CID 12166182.
  31. ^ Sommerfeld, Arnold (1952). Lectures on Theoretical Physics, Vol. I: Mechanics. New York: Academic Press. ISBN 978-0-12-654670-5.

constraint, computational, chemistry, computational, chemistry, constraint, algorithm, method, satisfying, newtonian, motion, rigid, body, which, consists, mass, points, restraint, algorithm, used, ensure, that, distance, between, mass, points, maintained, gen. In computational chemistry a constraint algorithm is a method for satisfying the Newtonian motion of a rigid body which consists of mass points A restraint algorithm is used to ensure that the distance between mass points is maintained The general steps involved are i choose novel unconstrained coordinates internal coordinates ii introduce explicit constraint forces iii minimize constraint forces implicitly by the technique of Lagrange multipliers or projection methods Constraint algorithms are often applied to molecular dynamics simulations Although such simulations are sometimes performed using internal coordinates that automatically satisfy the bond length bond angle and torsion angle constraints simulations may also be performed using explicit or implicit constraint forces for these three constraints However explicit constraint forces give rise to inefficiency more computational power is required to get a trajectory of a given length Therefore internal coordinates and implicit force constraint solvers are generally preferred Constraint algorithms achieve computational efficiency by neglecting motion along some degrees of freedom For instance in atomistic molecular dynamics typically the length of covalent bonds to hydrogen are constrained however constraint algorithms should not be used if vibrations along these degrees of freedom are important for the phenomenon being studied Contents 1 Mathematical background 2 Internal coordinate methods 3 Lagrange multiplier based methods 3 1 The SETTLE algorithm 3 2 The SHAKE algorithm 3 3 The M SHAKE algorithm 3 4 SHAPE algorithm 3 5 LINCS algorithm 4 Hybrid methods 5 See also 6 References and footnotesMathematical background editThe motion of a set of N particles can be described by a set of second order ordinary differential equations Newton s second law which can be written in matrix form M d 2 q d t 2 f V q displaystyle mathbf M cdot frac d 2 mathbf q dt 2 mathbf f frac partial V partial mathbf q nbsp where M is a mass matrix and q is the vector of generalized coordinates that describe the particles positions For example the vector q may be a 3N Cartesian coordinates of the particle positions rk where k runs from 1 to N in the absence of constraints M would be the 3Nx3N diagonal square matrix of the particle masses The vector f represents the generalized forces and the scalar V q represents the potential energy both of which are functions of the generalized coordinates q If M constraints are present the coordinates must also satisfy M time independent algebraic equations g j q 0 displaystyle g j mathbf q 0 nbsp where the index j runs from 1 to M For brevity these functions gi are grouped into an M dimensional vector g below The task is to solve the combined set of differential algebraic DAE equations instead of just the ordinary differential equations ODE of Newton s second law This problem was studied in detail by Joseph Louis Lagrange who laid out most of the methods for solving it 1 The simplest approach is to define new generalized coordinates that are unconstrained this approach eliminates the algebraic equations and reduces the problem once again to solving an ordinary differential equation Such an approach is used for example in describing the motion of a rigid body the position and orientation of a rigid body can be described by six independent unconstrained coordinates rather than describing the positions of the particles that make it up and the constraints among them that maintain their relative distances The drawback of this approach is that the equations may become unwieldy and complex for example the mass matrix M may become non diagonal and depend on the generalized coordinates A second approach is to introduce explicit forces that work to maintain the constraint for example one could introduce strong spring forces that enforce the distances among mass points within a rigid body The two difficulties of this approach are that the constraints are not satisfied exactly and the strong forces may require very short time steps making simulations inefficient computationally A third approach is to use a method such as Lagrange multipliers or projection to the constraint manifold to determine the coordinate adjustments necessary to satisfy the constraints Finally there are various hybrid approaches in which different sets of constraints are satisfied by different methods e g internal coordinates explicit forces and implicit force solutions Internal coordinate methods editThe simplest approach to satisfying constraints in energy minimization and molecular dynamics is to represent the mechanical system in so called internal coordinates corresponding to unconstrained independent degrees of freedom of the system For example the dihedral angles of a protein are an independent set of coordinates that specify the positions of all the atoms without requiring any constraints The difficulty of such internal coordinate approaches is twofold the Newtonian equations of motion become much more complex and the internal coordinates may be difficult to define for cyclic systems of constraints e g in ring puckering or when a protein has a disulfide bond The original methods for efficient recursive energy minimization in internal coordinates were developed by Gō and coworkers 2 3 Efficient recursive internal coordinate constraint solvers were extended to molecular dynamics 4 5 Analogous methods were applied later to other systems 6 7 8 Lagrange multiplier based methods edit nbsp Resolving the constraints of a rigid water molecule using Lagrange multipliers a the unconstrained positions are obtained after a simulation time step b the gradients of each constraint over each particle are computed and c the Lagrange multipliers are computed for each gradient such that the constraints are satisfied In most of molecular dynamics simulations that use constraint algorithms constraints are enforced using the method of Lagrange multipliers Given a set of n linear holonomic constraints at the time t s k t x k a t x k b t 2 d k 2 0 k 1 n displaystyle sigma k t mathbf x k alpha t mathbf x k beta t 2 d k 2 0 quad k 1 ldots n nbsp where x k a t displaystyle scriptstyle mathbf x k alpha t nbsp and x k b t displaystyle scriptstyle mathbf x k beta t nbsp are the positions of the two particles involved in the kth constraint at the time t and d k displaystyle d k nbsp is the prescribed inter particle distance The forces due to these constraints are added in the equations of motion resulting in for each of the N particles in the system 2 x i t t 2 m i x i V x i t k 1 n l k s k t i 1 N displaystyle frac partial 2 mathbf x i t partial t 2 m i frac partial partial mathbf x i left V mathbf x i t sum k 1 n lambda k sigma k t right quad i 1 ldots N nbsp Adding the constraint forces does not change the total energy as the net work done by the constraint forces taken over the set of particles that the constraints act on is zero Note that the sign on l k displaystyle lambda k nbsp is arbitrary and some references 9 have an opposite sign From integrating both sides of the equation with respect to the time the constrained coordinates of particles at the time t D t displaystyle t Delta t nbsp are given x i t D t x i t D t k 1 n l k s k t x i D t 2 m i 1 i 1 N displaystyle mathbf x i t Delta t hat mathbf x i t Delta t sum k 1 n lambda k frac partial sigma k t partial mathbf x i left Delta t right 2 m i 1 quad i 1 ldots N nbsp where x i t D t displaystyle hat mathbf x i t Delta t nbsp is the unconstrained or uncorrected position of the ith particle after integrating the unconstrained equations of motion To satisfy the constraints s k t D t displaystyle sigma k t Delta t nbsp in the next timestep the Lagrange multipliers should be determined as the following equation s k t D t x k a t D t x k b t D t 2 d k 2 0 displaystyle sigma k t Delta t left mathbf x k alpha t Delta t mathbf x k beta t Delta t right 2 d k 2 0 nbsp This implies solving a system of n displaystyle n nbsp non linear equations s j t D t x j a t D t x j b t D t k 1 n l k D t 2 s k t x j a m j a 1 s k t x j b m j b 1 2 d j 2 0 j 1 n displaystyle sigma j t Delta t left hat mathbf x j alpha t Delta t hat mathbf x j beta t Delta t sum k 1 n lambda k left Delta t right 2 left frac partial sigma k t partial mathbf x j alpha m j alpha 1 frac partial sigma k t partial mathbf x j beta m j beta 1 right right 2 d j 2 0 quad j 1 ldots n nbsp simultaneously for the n displaystyle n nbsp unknown Lagrange multipliers l k displaystyle lambda k nbsp This system of n displaystyle n nbsp non linear equations in n displaystyle n nbsp unknowns is commonly solved using Newton Raphson method where the solution vector l displaystyle underline lambda nbsp is updated using l l 1 l l J s 1 s t D t displaystyle underline lambda l 1 leftarrow underline lambda l mathbf J sigma 1 underline sigma t Delta t nbsp where J s displaystyle mathbf J sigma nbsp is the Jacobian of the equations sk J s 1 l 1 s 1 l 2 s 1 l n s 2 l 1 s 2 l 2 s 2 l n s n l 1 s n l 2 s n l n displaystyle mathbf J left begin array cccc frac partial sigma 1 partial lambda 1 amp frac partial sigma 1 partial lambda 2 amp cdots amp frac partial sigma 1 partial lambda n 5pt frac partial sigma 2 partial lambda 1 amp frac partial sigma 2 partial lambda 2 amp cdots amp frac partial sigma 2 partial lambda n 5pt vdots amp vdots amp ddots amp vdots 5pt frac partial sigma n partial lambda 1 amp frac partial sigma n partial lambda 2 amp cdots amp frac partial sigma n partial lambda n end array right nbsp Since not all particles contribute to all of constraints J s displaystyle mathbf J sigma nbsp is a block matrix and can be solved individually to block unit of the matrix In other words J s displaystyle mathbf J sigma nbsp can be solved individually for each molecule Instead of constantly updating the vector l displaystyle underline lambda nbsp the iteration can be started with l 0 0 displaystyle underline lambda 0 mathbf 0 nbsp resulting in simpler expressions for s k t displaystyle sigma k t nbsp and s k t l j displaystyle frac partial sigma k t partial lambda j nbsp In this case J i j s j l i l 0 2 x j a x j b s i x j a m j a 1 s i x j b m j b 1 displaystyle J ij left frac partial sigma j partial lambda i right mathbf lambda 0 2 left hat x j alpha hat x j beta right left frac partial sigma i partial x j alpha m j alpha 1 frac partial sigma i partial x j beta m j beta 1 right nbsp then l displaystyle lambda nbsp is updated to l j J 1 x j a t D t x j b t D t 2 d j 2 displaystyle mathbf lambda j mathbf J 1 left left hat mathbf x j alpha t Delta t hat mathbf x j beta t Delta t right 2 d j 2 right nbsp After each iteration the unconstrained particle positions are updated using x i t D t x i t D t k 1 n l k s k x i D t 2 m i 1 displaystyle hat mathbf x i t Delta t leftarrow hat mathbf x i t Delta t sum k 1 n lambda k frac partial sigma k partial mathbf x i left Delta t right 2 m i 1 nbsp The vector is then reset to l 0 displaystyle underline lambda mathbf 0 nbsp The above procedure is repeated until the solution of constraint equations s k t D t displaystyle sigma k t Delta t nbsp converges to a prescribed tolerance of a numerical error Although there are a number of algorithms to compute the Lagrange multipliers these difference is rely only on the methods to solve the system of equations For this methods quasi Newton methods are commonly used The SETTLE algorithm edit The SETTLE algorithm 10 solves the system of non linear equations analytically for n 3 displaystyle n 3 nbsp constraints in constant time Although it does not scale to larger numbers of constraints it is very often used to constrain rigid water molecules which are present in almost all biological simulations and are usually modelled using three constraints e g SPC E and TIP3P water models The SHAKE algorithm edit The SHAKE algorithm was first developed for satisfying a bond geometry constraint during molecular dynamics simulations 11 The method was then generalised to handle any holonomic constraint such as those required to maintain constant bond angles or molecular rigidity 12 In SHAKE algorithm the system of non linear constraint equations is solved using the Gauss Seidel method which approximates the solution of the linear system of equations using the Newton Raphson method l J s 1 s displaystyle underline lambda mathbf J sigma 1 underline sigma nbsp This amounts to assuming that J s displaystyle mathbf J sigma nbsp is diagonally dominant and solving the k displaystyle k nbsp th equation only for the k displaystyle k nbsp unknown In practice we compute l k s k t s k t l k x k a x k a l k s k t x k a x k b x k b l k s k t x k b displaystyle begin aligned lambda k amp leftarrow frac sigma k t partial sigma k t partial lambda k 5pt mathbf x k alpha amp leftarrow mathbf x k alpha lambda k frac partial sigma k t partial mathbf x k alpha 5pt mathbf x k beta amp leftarrow mathbf x k beta lambda k frac partial sigma k t partial mathbf x k beta end aligned nbsp for all k 1 n displaystyle k 1 ldots n nbsp iteratively until the constraint equations s k t D t displaystyle sigma k t Delta t nbsp are solved to a given tolerance The calculation cost of each iteration is O n displaystyle mathcal O n nbsp and the iterations themselves converge linearly A noniterative form of SHAKE was developed later on 13 Several variants of the SHAKE algorithm exist Although they differ in how they compute or apply the constraints themselves the constraints are still modelled using Lagrange multipliers which are computed using the Gauss Seidel method The original SHAKE algorithm is capable of constraining both rigid and flexible molecules eg water benzene and biphenyl and introduces negligible error or energy drift into a molecular dynamics simulation 14 One issue with SHAKE is that the number of iterations required to reach a certain level of convergence does rise as molecular geometry becomes more complex To reach 64 bit computer accuracy a relative tolerance of 10 16 displaystyle approx 10 16 nbsp in a typical molecular dynamics simulation at a temperature of 310K a 3 site water model having 3 constraints to maintain molecular geometry requires an average of 9 iterations which is 3 per site per time step A 4 site butane model with 5 constraints needs 17 iterations 22 per site a 6 site benzene model with 12 constraints needs 36 iterations 72 per site while a 12 site biphenyl model with 29 constraints requires 92 iterations 229 per site per time step 14 Hence the CPU requirements of the SHAKE algorithm can become significant particularly if a molecular model has a high degree of rigidity A later extension of the method QSHAKE Quaternion SHAKE was developed as a faster alternative for molecules composed of rigid units but it is not as general purpose 15 It works satisfactorily for rigid loops such as aromatic ring systems but QSHAKE fails for flexible loops such as when a protein has a disulfide bond 16 Further extensions include RATTLE 17 WIGGLE 18 and MSHAKE 19 While RATTLE works the same way as SHAKE 20 yet using the Velocity Verlet time integration scheme WIGGLE extends SHAKE and RATTLE by using an initial estimate for the Lagrange multipliers l k displaystyle lambda k nbsp based on the particle velocities It is worth mentioning that MSHAKE computes corrections on the constraint forces achieving better convergence A final modification to the SHAKE algorithm is the P SHAKE algorithm 21 that is applied to very rigid or semi rigid molecules P SHAKE computes and updates a pre conditioner which is applied to the constraint gradients before the SHAKE iteration causing the Jacobian J s displaystyle mathbf J sigma nbsp to become diagonal or strongly diagonally dominant The thus de coupled constraints converge much faster quadratically as opposed to linearly at a cost of O n 2 displaystyle mathcal O n 2 nbsp The M SHAKE algorithm edit The M SHAKE algorithm 22 solves the non linear system of equations using Newton s method directly In each iteration the linear system of equations l J s 1 s displaystyle underline lambda mathbf J sigma 1 underline sigma nbsp is solved exactly using an LU decomposition Each iteration costs O n 3 displaystyle mathcal O n 3 nbsp operations yet the solution converges quadratically requiring fewer iterations than SHAKE This solution was first proposed in 1986 by Ciccotti and Ryckaert 12 under the title the matrix method yet differed in the solution of the linear system of equations Ciccotti and Ryckaert suggest inverting the matrix J s displaystyle mathbf J sigma nbsp directly yet doing so only once in the first iteration The first iteration then costs O n 3 displaystyle mathcal O n 3 nbsp operations whereas the following iterations cost only O n 2 displaystyle mathcal O n 2 nbsp operations for the matrix vector multiplication This improvement comes at a cost though since the Jacobian is no longer updated convergence is only linear albeit at a much faster rate than for the SHAKE algorithm Several variants of this approach based on sparse matrix techniques were studied by Barth et al 23 SHAPE algorithm edit The SHAPE algorithm 24 is a multicenter analog of SHAKE for constraining rigid bodies of three or more centers Like SHAKE an unconstrained step is taken and then corrected by directly calculating and applying the rigid body rotation matrix that satisfies L rigid t D t 2 L nonrigid t D t 2 displaystyle L text rigid left t frac Delta t 2 right L text nonrigid left t frac Delta t 2 right nbsp This approach involves a single 3 3 matrix diagonalization followed by three or four rapid Newton iterations to determine the rotation matrix SHAPE provides the identical trajectory that is provided with fully converged iterative SHAKE yet it is found to be more efficient and more accurate than SHAKE when applied to systems involving three or more centers It extends the ability of SHAKE like constraints to linear systems with three or more atoms planar systems with four or more atoms and to significantly larger rigid structures where SHAKE is intractable It also allows rigid bodies to be linked with one or two common centers e g peptide planes by solving rigid body constraints iteratively in the same basic manner that SHAKE is used for atoms involving more than one SHAKE constraint LINCS algorithm edit An alternative constraint method LINCS Linear Constraint Solver was developed in 1997 by Hess Bekker Berendsen and Fraaije 25 and was based on the 1986 method of Edberg Evans and Morriss EEM 26 and a modification thereof by Baranyai and Evans BE 27 LINCS applies Lagrange multipliers to the constraint forces and solves for the multipliers by using a series expansion to approximate the inverse of the Jacobian J s displaystyle mathbf J sigma nbsp I J s 1 I J s J s 2 J s 3 displaystyle mathbf I mathbf J sigma 1 mathbf I mathbf J sigma mathbf J sigma 2 mathbf J sigma 3 cdots nbsp in each step of the Newton iteration This approximation only works for matrices with eigenvalues smaller than 1 making the LINCS algorithm suitable only for molecules with low connectivity LINCS has been reported to be 3 4 times faster than SHAKE 25 Hybrid methods editHybrid methods have also been introduced in which the constraints are divided into two groups the constraints of the first group are solved using internal coordinates whereas those of the second group are solved using constraint forces e g by a Lagrange multiplier or projection method 28 29 30 This approach was pioneered by Lagrange 1 and result in Lagrange equations of the mixed type 31 See also editMolecular dynamics Software for molecular mechanics modelingReferences and footnotes edit a b Lagrange GL 1788 Mecanique analytique Noguti T Toshiyuki Gō N 1983 A Method of Rapid Calculation of a 2nd Derivative Matrix of Conformational Energy for Large Molecules Journal of the Physical Society of Japan 52 10 3685 3690 Bibcode 1983JPSJ 52 3685N doi 10 1143 JPSJ 52 3685 Abe H Braun W Noguti T Gō N 1984 Rapid Calculation of 1st and 2nd Derivatives of Conformational Energy with respect to Dihedral Angles for Proteins General Recurrent Equations Computers and Chemistry 8 4 239 247 doi 10 1016 0097 8485 84 85015 9 Bae D S Haug EJ 1988 A Recursive Formulation for Constrained Mechanical System Dynamics Part I Open Loop Systems Mechanics of Structures and Machines 15 3 359 382 doi 10 1080 08905458708905124 Jain A Vaidehi N Rodriguez G 1993 A Fast Recursive Algorithm for Molecular Dynamics Simulation Journal of Computational Physics 106 2 258 268 Bibcode 1993JCoPh 106 258J doi 10 1006 jcph 1993 1106 Rice LM Brunger AT 1994 Torsion Angle Dynamics Reduced Variable Conformational Sampling Enhances Crystallographic Structure Refinement Proteins Structure Function and Genetics 19 4 277 290 doi 10 1002 prot 340190403 PMID 7984624 S2CID 25080482 Mathiowetz AM Jain A Karasawa N Goddard III WA 1994 Protein Simulations Using Techniques Suitable for Very Large Systems The Cell Multipole Method for Nonbond Interactions and the Newton Euler Inverse Mass Operator Method for Internal Coordinate Dynamics Proteins Structure Function and Genetics 20 3 227 247 doi 10 1002 prot 340200304 PMID 7892172 S2CID 25753031 Mazur AK 1997 Quasi Hamiltonian Equations of Motion for Internal Coordinate Molecular Dynamics of Polymers Journal of Computational Chemistry 18 11 1354 1364 arXiv physics 9703019 doi 10 1002 SICI 1096 987X 199708 18 11 lt 1354 AID JCC3 gt 3 0 CO 2 K Miyamoto S Kollman PA 1992 SETTLE An Analytical Version of the SHAKE and RATTLE Algorithm for Rigid Water Models Journal of Computational Chemistry 13 8 952 962 doi 10 1002 jcc 540130805 S2CID 122506495 Miyamoto S Kollman PA 1992 SETTLE An Analytical Version of the SHAKE and RATTLE Algorithm for Rigid Water Models Journal of Computational Chemistry 13 8 952 962 doi 10 1002 jcc 540130805 S2CID 122506495 Ryckaert J P Ciccotti G Berendsen HJC 1977 Numerical Integration of the Cartesian Equations of Motion of a System with Constraints Molecular Dynamics of n Alkanes Journal of Computational Physics 23 3 327 341 Bibcode 1977JCoPh 23 327R CiteSeerX 10 1 1 399 6868 doi 10 1016 0021 9991 77 90098 5 a b Ciccotti G J P Ryckaert 1986 Molecular Dynamics Simulation of Rigid Molecules Computer Physics Reports 4 6 345 392 Bibcode 1986CoPhR 4 346C doi 10 1016 0167 7977 86 90022 5 Yoneya M Berendsen HJC Hirasawa K 1994 A Noniterative Matrix Method for Constraint Molecular Dynamics Simulations Molecular Simulations 13 6 395 405 doi 10 1080 08927029408022001 a b Hammonds KD Heyes DM 2020 Shadow Hamiltonian in classical NVE molecular dynamics simulations A path to long time stability Journal of Chemical Physics 152 2 024114 1 024114 15 doi 10 1063 1 5139708 PMID 31941339 S2CID 210333551 Forester TR Smith W 1998 SHAKE Rattle and Roll Efficient Constraint Algorithms for Linked Rigid Bodies Journal of Computational Chemistry 19 102 111 doi 10 1002 SICI 1096 987X 19980115 19 1 lt 102 AID JCC9 gt 3 0 CO 2 T McBride C Wilson MR Howard JAK 1998 Molecular dynamics simulations of liquid crystal phases using atomistic potentials Molecular Physics 93 6 955 964 Bibcode 1998MolPh 93 955C doi 10 1080 002689798168655 Andersen Hans C 1983 RATTLE A Velocity Version of the SHAKE Algorithm for Molecular Dynamics Calculations Journal of Computational Physics 52 1 24 34 Bibcode 1983JCoPh 52 24A CiteSeerX 10 1 1 459 5668 doi 10 1016 0021 9991 83 90014 1 Lee Sang Ho Kim Palmo Samuel Krimm 2005 WIGGLE A new constrained molecular dynamics algorithm in Cartesian coordinates Journal of Computational Physics 210 1 171 182 Bibcode 2005JCoPh 210 171L doi 10 1016 j jcp 2005 04 006 Lambrakos S G J P Boris E S Oran I Chandrasekhar M Nagumo 1989 A Modified SHAKE algorithm for Maintaining Rigid Bonds in Molecular Dynamics Simulations of Large Molecules Journal of Computational Physics 85 2 473 486 Bibcode 1989JCoPh 85 473L doi 10 1016 0021 9991 89 90160 5 Leimkuhler Benedict Robert Skeel 1994 Symplectic numerical integrators in constrained Hamiltonian systems Journal of Computational Physics 112 1 117 125 Bibcode 1994JCoPh 112 117L doi 10 1006 jcph 1994 1085 Gonnet Pedro 2007 P SHAKE A quadratically convergent SHAKE in O n 2 displaystyle mathcal O n 2 nbsp Journal of Computational Physics 220 2 740 750 Bibcode 2007JCoPh 220 740G doi 10 1016 j jcp 2006 05 032 Krautler Vincent W F van Gunsteren P H Hunenberger 2001 A Fast SHAKE Algorithm to Solve Distance Constraint Equations for Small Molecules in Molecular Dynamics Simulations Journal of Computational Chemistry 22 5 501 508 doi 10 1002 1096 987X 20010415 22 5 lt 501 AID JCC1021 gt 3 0 CO 2 V S2CID 6187100 Barth Eric K Kuczera B Leimkuhler R Skeel 1995 Algorithms for constrained molecular dynamics Journal of Computational Chemistry 16 10 1192 1209 doi 10 1002 jcc 540161003 S2CID 38109923 Tao Peng Xiongwu Wu Bernard R Brooks 2012 Maintain rigid structures in Verlet based Cartesian molecular dynamics simulations The Journal of Chemical Physics 137 13 134110 Bibcode 2012JChPh 137m4110T doi 10 1063 1 4756796 PMC 3477181 PMID 23039588 a b Hess B Bekker H Berendsen HJC Fraaije JGEM 1997 LINCS A Linear Constraint Solver for Molecular Simulations Journal of Computational Chemistry 18 12 1463 1472 CiteSeerX 10 1 1 48 2727 doi 10 1002 SICI 1096 987X 199709 18 12 lt 1463 AID JCC4 gt 3 0 CO 2 H Edberg R Evans DJ Morriss GP 1986 Constrained Molecular Dynamics Simulations of Liquid Alkanes with a New Algorithm Journal of Chemical Physics 84 12 6933 6939 Bibcode 1986JChPh 84 6933E doi 10 1063 1 450613 Baranyai A Evans DJ 1990 New Algorithm for Constrained Molecular Dynamics Simulation of Liquid Benzene and Naphthalene Molecular Physics 70 1 53 63 Bibcode 1990MolPh 70 53B doi 10 1080 00268979000100841 Mazur AK 1999 Symplectic integration of closed chain rigid body dynamics with internal coordinate equations of motion Journal of Chemical Physics 111 4 1407 1414 Bibcode 1999JChPh 111 1407M doi 10 1063 1 479399 Bae D S Haug EJ 1988 A Recursive Formulation for Constrained Mechanical System Dynamics Part II Closed Loop Systems Mechanics of Structures and Machines 15 4 481 506 doi 10 1080 08905458708905130 Rodriguez G Jain A Kreutz Delgado K 1991 A Spatial Operator Algebra for Manipulator Modeling and Control The International Journal of Robotics Research 10 4 371 381 doi 10 1177 027836499101000406 hdl 2060 19900020578 S2CID 12166182 Sommerfeld Arnold 1952 Lectures on Theoretical Physics Vol I Mechanics New York Academic Press ISBN 978 0 12 654670 5 Retrieved from https en wikipedia org w index php title Constraint computational chemistry amp oldid 1178415913, wikipedia, wiki, book, books, library,

article

, read, download, free, free download, mp3, video, mp4, 3gp, jpg, jpeg, gif, png, picture, music, song, movie, book, game, games.