An Improved Multi-Start Particle Swarm-based Algorithm for Protein Structure Comparison

This paper proposes a novel particle-swarm based approach for protein structure alignment and comparison. Applying heuristic search to discover similar protein substructure patterns can be easily trapped in certain regions of the sparse and challenging problem search space. Diversification, or restarting the heuristic search, is one of the common strategies used to escape local optima. Agile Particle Swarm Optimization (APSO) is a recent multi-start PSO that addresses the question of when to best restart swarm particles. This paper focuses on where and how to restart the swarm. Another challenge of applying a heuristic search to protein structures is that the fitness landscape does not necessarily guide to the optimal region. To address this issue, we propose the Targeted Agile PSO (TA-PSO) that uses a dynamic windowbased search for automatic, variable-size pattern discovery in protein structures. The TA-PSO automatically builds a guiding list of potential patterns and uses it during the search process, which helps to find better solutions faster. The proposed TA-PSO showed up to 4 times improved performance that is similar to 3.5 times faster and 6 times more robust/consistent compared with the traditional 'non-targeted' search.