Protein structure prediction based on particle swarm optimization and tabu search strategy

Shuchun Yu, Li Xianxiang, Tian Xue, Ming PangBMC Bioinformatics 2022 · DOI

TL;DR

This paper introduces a novel hybrid algorithm that combines Particle Swarm Optimization (PSO) and Tabu Search (TS) to predict the most stable 3D structure of proteins. By leveraging PSO for global exploration and TS for local refinement, the method achieves significantly lower potential energy values, indicating more stable protein structures compared to existing PSO and TS approaches.

What Problem Does This Paper Address?

Understanding the 3D structure of proteins is crucial in bioinformatics, as a protein's spatial arrangement dictates its function and is intimately linked to human health. Misfolded or mutated protein structures can lead to diseases. Predicting the most stable conformation of a protein, which corresponds to its lowest potential energy state, is a computationally challenging problem. Existing methods, while advancing the field, still struggle with accuracy and efficiency, especially given the vast search space of possible protein structures. This paper aims to improve the accuracy and efficiency of protein structure prediction by developing a more robust optimization strategy.

Methods

The core of this paper is a hybrid algorithm that fuses Particle Swarm Optimization (PSO) and Tabu Search (TS). The approach begins with PSO to globally explore the potential solution space and find a promising initial solution. This initial solution is then used to seed the Tabu Search algorithm. TS then takes over for local refinement, using its memory (tabu list) to avoid revisiting previously explored states and guide the search towards optimal solutions.

Specifically:

  • PSO for Initialization: PSO is used to generate an initial set of candidate solutions. The velocity and position of particles are updated using standard PSO equations, incorporating inertia weight and learning factors.
  • Tabu Search for Refinement: TS is employed to refine the solutions found by PSO.
  • Neighborhood Function: A "silk line of disturbance variation" is used to generate diverse neighborhood solutions.
  • Candidate Solution Set: The algorithm selects a subset of neighborhood solutions with the lowest fitness values.
  • Tabu List: A tabu list stores recently searched solutions to prevent cycling. The length of the tabu list is a critical parameter influencing search range and speed.
  • Tabu Criterion: A criterion is defined to determine if a candidate solution is "tabu," based on the difference in fitness values and the distance between solution vectors.

The protein structure is modeled using the AB non-lattice model, which is considered more realistic than the HP lattice model as it allows for variable angles between amino acid residues, better reflecting the spatial structure of proteins. The energy function for this model considers both the folding of the amino acid skeleton and interactions between non-adjacent residues.

Datasets

The paper uses four groups of artificial protein sequences for evaluation. These sequences vary in length and the proportion of hydrophilic (a) and hydrophobic (b) amino acids. The specific configurations of these sequences are illustrated in Figure 1. No new benchmark datasets were introduced; instead, commonly used artificial sequences were selected for experimental validation.

Key Insights and Ideas

  • Synergy of Global and Local Search: The paper highlights the power of combining global exploration (PSO) with focused local refinement (TS). PSO helps escape initial local optima, while TS efficiently searches the promising regions identified by PSO.
  • AB Non-Lattice Model Superiority: The AB non-lattice model is chosen for its ability to represent protein structures more realistically than the HP lattice model, leading to more accurate energy calculations.
  • Importance of Tabu List Management: The authors emphasize that the length of the tabu list is crucial. A well-tuned tabu list balances search breadth and convergence speed, preventing both exhaustive but slow searches and premature convergence to suboptimal solutions.
  • Potential Energy as a Stability Metric: The fundamental idea that lower potential energy equates to a more stable protein structure is central to the evaluation.

Key Results

The experimental results demonstrate that the proposed hybrid PSO-TS algorithm consistently achieves lower minimum potential energy values for the four groups of artificial protein sequences compared to standalone Tabu Search and Particle Swarm Optimization methods.

  • For the first group of protein sequences, the proposed method improved the prediction of minimum potential energy by 127% compared to the Tabu Search method and 7% compared to the Particle Swarm Optimization algorithm.
  • The paper states that the algorithm obtains "more reasonable protein stable structure" and that the effect is "obviously better than the other two comparison methods."

Limitations and Future Work

  • Dependence on Initial Solution: The paper acknowledges that Tabu Search can be dependent on the initial solution. While PSO mitigates this by providing a good starting point, the performance can still be influenced by the quality of the initial PSO convergence.
  • Parameter Tuning: The effectiveness of the hybrid algorithm relies on careful tuning of parameters for both PSO and TS (e.g., number of particles, iteration limits, learning factors, tabu list length, tabu criterion thresholds). The paper specifies some parameter values used in their experiments (e.g., L=40, Lc=6, LT=8, E0=0.10, r0=0.005), but optimal tuning for diverse protein types might require further investigation.
  • Computational Cost: While aiming for efficiency, complex optimization algorithms can still be computationally intensive. The paper does not explicitly detail the computational time savings or trade-offs compared to other methods.

Future work could involve applying this hybrid approach to a wider range of real protein sequences, exploring more sophisticated neighborhood generation strategies, and investigating adaptive parameter tuning mechanisms to further enhance performance and robustness.

Summary updated

BibTeX
@article{yu2022protein,
  author = {Shuchun Yu and Li Xianxiang and Tian Xue and Ming Pang},
  title = {{Protein structure prediction based on particle swarm optimization and tabu search strategy}},
  journal = {BMC Bioinformatics},
  year = {2022},
  doi = {10.1186/s12859-022-04888-4},
}
Figure