FAST ADAPTIVE MULTIPOLE METHOD FOR COMPUTATION OF ELECTROSTATIC ENERGY IN SIMULATIONS OF POLYELECTROLYTE DNA

This article presents a fast adaptive method for the computation of lo ng-range electrostatic interactions in computer simulations of polyele ctrolyte DNA. Classically, the computation of electrostatic energy inv olves a direct summation of all pairwise interactions due to the charg ed phosphate groups in the molecule. This results in an N-body interac tion problem with an asymptotic time complexity of O(N-2) which is com putationally very expensive and limits the number of phosphate groups that can be used in computer simulations of polyelectrolyte DNA to at most several hundred. We describe an effort to speed up computer simul ations of polyelectrolyte DNA with the use of a fast adaptive hierarch ical algorithm for the computation of electrostatic energy (i.e., modi fied Debye-Huckel energy). The asymptotic time complexity is reduced t o O(N) with the implementation of the fast hierarchical algorithm on s erial computers. This is achieved by grouping phosphate groups into an adaptive hierarchical data structure and computing the interactions b etween groups using low order multipole and Taylor series expansions e xpressed in Cartesian coordinates. We first examine the accuracy and s peed enhancements of the fast hierarchical method in the computation o f the electrostatic energy of circular DNA at zero and high salt conce ntrations. The fast hierarchical method is further tested in a one-ste p Monte Carlo (MC) simulated annealing algorithm for closed circular s upercoiled DNA. In all cases, we observe order of magnitude reductions in the computation time with negligible loss of numerical accuracy in the electrostatic energy computation. (C) 1996 by John Wiley & Sons, Inc.