An N log N approximation based on the natural organization of biomolecules for speeding up the computation of long range interactions
- 30 June 2009
- journal article
- research article
- Published by Wiley in Journal of Computational Chemistry
- Vol. 31 (4), 691-706
- https://doi.org/10.1002/jcc.21357
Abstract
Presented here is a method, the hierarchical charge partitioning (HCP) approximation, for speeding up computation of pairwise electrostatic interactions in biomolecular systems. The approximation is based on multiple levels of natural partitioning of biomolecular structures into a hierarchical set of its constituent structural components. The charge distribution in each component is systematically approximated by a small number of point charges, which, for the highest level component, are much fewer than the number of atoms in the component. For short distances from the point of interest, the HCP uses the full set of atomic charges available. For long-distance interactions, the approximate charge distributions with smaller sets of charges are used instead. For a structure consisting of N charges, the computational cost of computing the pairwise interactions via the HCP scales as O(N log N), under assumptions about the structural organization of biomolecular structures generally consistent with reality. A proof-of-concept implementation of the HCP shows that for large structures it can lead to speed-up factors of up to several orders of magnitude relative to the exact pairwise O(N2) all-atom computation used as a reference. For structures with more than 2000–3000 atoms the relative accuracy of the HCP (relative root-mean-square force error per atom), approaches the accuracy of the particle mesh Ewald (PME) method with parameter settings typical for biomolecular simulations. When averaged over a set of 600 representative biomolecular structures, the relative accuracies of the two methods are roughly equal. The HCP is also significantly more accurate than the spherical cutoff method. The HCP has been implemented in the freely available nucleic acids builder (NAB) molecular dynamics (MD) package in Amber tools. A 10 ns simulation of a small protein indicates that the HCP based MD simulation is stable, and that it can be faster than the spherical cutoff method. A critical benefit of the HCP approximation is that it is algorithmically very simple, and unlike the PME, the HCP is straightforward to use with implicit solvent models. © 2009 Wiley Periodicals, Inc. J Comput Chem, 2010Keywords
This publication has 92 references indexed in Scilit:
- An analytical approach to computing biomolecular electrostatic potential. II. Validation and applicationsThe Journal of Chemical Physics, 2008
- An analytical approach to computing biomolecular electrostatic potential. I. Derivation and analysisThe Journal of Chemical Physics, 2008
- Atomic level computational identification of ligand migration pathways between solvent and binding site in myoglobinProceedings of the National Academy of Sciences, 2008
- Continuum Polarizable Force Field within the Poisson−Boltzmann FrameworkThe Journal of Physical Chemistry B, 2008
- Comparison of multiple Amber force fields and development of improved protein backbone parametersProteins-Structure Function and Bioinformatics, 2006
- Molecular Dynamics: Survey of Methods for Simulating the Activity of ProteinsChemical Reviews, 2006
- Molecular dynamics simulations of biomoleculesNature Structural & Molecular Biology, 2002
- VMD: Visual molecular dynamicsJournal of Molecular Graphics, 1996
- Comparison of simple potential functions for simulating liquid waterThe Journal of Chemical Physics, 1983
- CHARMM: A program for macromolecular energy, minimization, and dynamics calculationsJournal of Computational Chemistry, 1983