Optimal Alignment of Structures for Finite and Periodic Systems
Open Access
- 14 September 2017
- journal article
- research article
- Published by American Chemical Society (ACS) in Journal of Chemical Theory and Computation
- Vol. 13 (10) , 4914-4931
Abstract
Finding the optimal alignment between two structures is important for identifying the minimum root-mean-square distance (RMSD) between them and as a starting point for calculating pathways. Most current algorithms for aligning structures are stochastic, scale exponentially with the size of structure, and the performance can be unreliable. We present two complementary methods for aligning structures corresponding to isolated clusters of atoms and to condensed matter described by a periodic cubic supercell. The first method (Go-PERMDIST), a branch and bound algorithm, locates the global minimum RMSD deterministically in polynomial time. The run time increases for larger RMSDs. The second method (FASTOVERLAP) is a heuristic algorithm that aligns structures by finding the global maximum kernel correlation between them using fast Fourier transforms (FFTs) and fast SO(3) transforms (SOFTs). For periodic systems, FASTOVERLAP scales with the square of the number of identical atoms in the system, reliably finds the best alignment between structures that are not too distant, and shows significantly better performance than existing algorithms. The expected run time for Go-PERMDIST is longer than FASTOVERLAP for periodic systems. For finite clusters, the FASTOVERLAP algorithm is competitive with existing algorithms. The expected run time for Go-PERMDIST to find the global RMSD between two structures deterministically is generally longer than for existing stochastic algorithms. However, with an earlier exit condition, Go-PERMDIST exhibits similar or better performance.Keywords
Funding Information
- Engineering and Physical Sciences Research Council (EP/G037221/1)
This publication has 61 references indexed in Scilit:
- CCL: an algorithm for the efficient comparison of clustersJournal of Applied Crystallography, 2013
- Quasi-Continuous Interpolation Scheme for Pathways between Distant ConfigurationsJournal of Chemical Theory and Computation, 2012
- Binding Balls: Fast Detection of Binding Sites Using a Property of Spherical Fourier TransformJournal of Computational Biology, 2009
- A review of recent range image registration methods with accuracy evaluationImage and Vision Computing, 2007
- Generalized Neural-Network Representation of High-Dimensional Potential-Energy SurfacesPhysical Review Letters, 2007
- Using quaternions to calculate RMSDJournal of Computational Chemistry, 2004
- Robust registration of 2D and 3D point setsImage and Vision Computing, 2003
- Single-centre expansion of Gaussian basis functions and the angular decomposition of their overlap integralsJournal of Physics B: Atomic, Molecular and Optical Physics, 1989
- Numerical Experiments on the Stochastic Behavior of a Lennard-Jones Gas SystemPhysical Review A, 1973
- The Hungarian method for the assignment problemNaval Research Logistics Quarterly, 1955