Optimal Alignment of Structures for Finite and Periodic Systems

Area of Science:

• Computational chemistry
• Materials science
• Structural biology

Background:

• Accurate structure alignment is crucial for determining minimum root-mean-square distance (RMSD) and calculating pathways.
• Existing alignment algorithms are often stochastic, computationally expensive, and unreliable for large structures.

Purpose of the Study:

• To introduce two novel, efficient algorithms for aligning atomic structures.
• To address limitations of current methods for both finite clusters and periodic systems.

Main Methods:

• Go-PERMDIST: A deterministic branch and bound algorithm for finding the global minimum RMSD in polynomial time.
• FASTOVERLAP: A heuristic algorithm utilizing fast Fourier transforms (FFTs) and fast SO(3) transforms (SOFTs) for alignment via maximum kernel correlation.
• Application to isolated atomic clusters and periodic cubic supercells.

Main Results:

• Go-PERMDIST deterministically finds the global minimum RMSD, with runtime increasing for larger RMSDs.
• FASTOVERLAP demonstrates superior performance for periodic systems compared to existing algorithms, scaling quadratically with identical atoms.
• FASTOVERLAP is competitive for finite clusters, while Go-PERMDIST shows potential with an early exit condition.

Conclusions:

• The developed Go-PERMDIST and FASTOVERLAP algorithms offer robust and efficient solutions for structure alignment.
• These methods provide reliable alternatives to existing stochastic approaches, particularly for periodic materials.
• The choice between algorithms depends on system type (periodic vs. finite) and desired accuracy versus speed.