NP-Hard Optimization in HP Model Protein Folding: A Systematic Review of Simulated Annealing, Genetic Algorithm, Particle Swarm Optimization, and Tabu Search
DOI:
https://doi.org/10.61173/rrx24377Keywords:
Protein Folding Prediction, HP Model, Meta- heuristic Algorithms, Simulated Annealing, Computational BiologyAbstract
Protein folding prediction in the HP model is an NP-hard problem which highly needs effective heuristic methods to optimize. Protein folding prediction in the HP model is an NP-hard problem which highly needs effective heuristic methods to optimize. This paper reviews and compares four well-known meta-heuristic algorithms, namely Simulated Annealing (SA), Genetic Algorithm (GA), Particle Swarm Optimization (PSO), and Tabu Search (TS), focused on three main aspects: ability to cross the energy barrier, robustness to initial solutions, and computational cost. The results show that each algorithm has its strength, namely, SA searching exceling in early-stage exploration, GA providing a stable solution with population diversity, PSO efficiently achieving rapid convergence while maintaining moderate robustness, and TS escaping local minima. This study does not aim to identify a single optimal method, but to elucidate the contexts and conditions under which each heuristic approach can be effectively applied to the protein folding problem. The review will become a practical guide for selecting an optimization method for protein structure prediction where NP-hard problems exist.
References
[1] P. Carracedo-Reboredo, S. Liñares-Blanco, A. Rodríguez- Fernández, J. Cedrón-Cabo, H. Novoa, C. Carballal, et al., A review on machine learning approaches and trends in drug discovery. Briefings in Bioinformatics, vol. 22, no. 6, pp. 1–19
[2021] . https://doi.org/10.1093/bib/bbab159
[2] C.-H. Yang, Y.-S. Wu, and W.-C. Yeh, Protein folding prediction in the HP model using ions motion optimization with a greedy algorithm. BioData Mining, vol. 11, no. 17, pp. 1–19
[2018] . https://doi.org/10.1186/s13040-018-0170-2
[3] M. Traykov, K. Traykov, and D. Boiadjiev, Protein folding in 3D lattice HP model using heuristic optimization methods. WSEAS Transactions on Circuits and Systems, vol. 17, pp. 192–200 (2018).
[4] T. Guilmeau, J. F. Bonnans, and D. Chikhi, Simulated annealing: a review and a new scheme. In: Proceedings of the 2021 IEEE Statistical Signal Processing Workshop (SSP), pp. 31–35 (2021). https://doi.org/10.1109/SSP49050.2021.9513764
[5] C. Rajwar, P. K. Gupta, and R. Kumar, An exhaustive review of the metaheuristic algorithms for engineering problems. Mathematics, vol. 11, no. 3, pp. 1–40 (2023). https://doi. org/10.3390/math11030618
[6] A. Möbius, Simulated annealing in the hydrophobic-polar (HP) model: experiments on the 3D136 instance including restarts, comparison of final vs. best‐visited states, and cooling schedule effects. Journal of Innovative Materials in Extreme Conditions, vol. 5, issue 1, pp. 9–17 (2024).
[7] C. Zhang, Comparative Analysis of Simulated Annealing in Protein Folding Prediction Using HP Models. Theoretical and Natural Science, vol. 75, pp. 197–205 (2025).
[8] B. Bošković and J. Brest, Genetic algorithm with advanced mechanisms applied to the protein structure prediction in a hydrophobic–polar model and cubic lattice. Applied Soft Computing, vol. 45, pp. 61–70 (2016). https://doi.org/10.1016/ j.asoc.2016.04.001
[9] S. P. N. Dubey, R. Kumar, and S. K. Singh, A comparative study on single and multiple point crossovers in a genetic algorithm for HP model-based protein structure prediction. Informatics in Medicine Unlocked, vol. 12, pp. 92–100 (2018). https://doi.org/10.1016/j.imu.2018.07.003
[10] M. Rezaei, A. Ahmadi-Javid, B. Mahdavi, A novel algorithm based on a modified PSO to predict 3D structure for proteins in HP model using Transfer Learning. Expert Systems with Applications, vol. 211 (2024). https://doi.org/10.1016/ j.eswa.2023.121233
[11] Y. Shuchun, L. Xianxiang, T. Xue, M. Pang, Protein structure prediction based on particle swarm optimization and tabu search strategy. BMC Bioinformatics, vol. 23, article 352 (2022). https://doi.org/10.1186/s12859-022-04888-4
[12] S. Shmygelska and H. H. Hoos, An improved Tabu Search algorithm for the HP protein folding problem. BMC Bioinformatics, vol. 6, no. 30, pp. 1–19 (2015). https://doi. org/10.1186/1471-2105-6-30
[13] H. Chen, J. Zhang, and Q. Li, Hybrid tabu search strategies for protein structure prediction in HP model: adaptive tabu length and cooperative heuristics. Journal of Computational Biology, vol. 27, no. 12, pp. 1778–1792 (2020). https://doi. org/10.1089/cmb.2019.0325
[14] M. Zaki, A. Elsayed, and A. Kattan, Cooling schedules and performance trade-offs in simulated annealing for protein structure prediction. Journal of Computational Biology, vol. 27, no. 9, pp. 1342–1355 (2020). https://doi.org/10.1089/ cmb.2019.0187
[15] P. Singh and R. S. Chauhan, Improved genetic operators for hydrophobic–polar protein structure prediction. Journal of Bioinformatics and Computational Biology, vol. 19, no. 6, pp. 2150027 (2021). https://doi.org/10.1142/S0219720021500278
[16] L. Miao, Y. Wang, and C. Zhao, Hybrid particle swarm optimization for HP model-based protein folding prediction. IEEE Access, vol. 9, pp. 55021–55033 (2021). https://doi. org/10.1109/ACCESS.2021.3070000
[17] J. Wu and Q. Zhang, Dynamic tabu search strategies for complex protein folding landscapes. BMC Bioinformatics, vol. 22, no. 315, pp. 1–15 (2021). https://doi.org/10.1186/s12859- 021-04289-1
[18] L. Jumper, R. Evans, A. Pritzel, et al., Highly accurate protein structure prediction with AlphaFold. Nature, vol. 596, no. 7873, pp. 583–589 (2021). https://doi.org/10.1038/s41586- 021-03819-2
[19] P. Crescenzi, D. Goldman, C. Papadimitriou, et al., Protein structure is hard: complexity results for folding the HP model. Dean&Francis Chenyi Wang Journal of Computational Biology, vol. 27, no. 12, pp. 1678– 1690 (2020). https://doi.org/10.1089/cmb.2019.0331
[20] M. Mirjalili, S. Saremi, H. Faris, and S. Mirjalili, Advances in metaheuristic optimization for protein structure prediction: opportunities and challenges. IEEE Access, vol. 8, pp. 149159– 149180 (2020). https://doi.org/10.1109/ACCESS.2020.3016654
[21] Z. Yuan, L. Zhang, and H. Liu, Hybrid metaheuristic algorithms for complex optimization: a review and perspectives. Information Sciences, vol. 581, pp. 401–426 (2021). https://doi. org/10.1016/j.ins.2021.09.001
[22] H. Senior, R. Evans, J. Jumper, et al., Improved protein structure prediction using potentials from deep learning. Nature, vol. 577, no. 7792, pp. 706–710 (2020). https://doi.org/10.1038/ s41586-019-1923-7
Downloads
Published
Issue
Section
License
Copyright (c) 2025 by the authors.
This work is licensed under a Creative Commons Attribution 4.0 International License.
