Bioinspired Algorithms for Multiple Sequence Alignment: A Systematic Review and Roadmap
Source abstract
Abstract
Multiple Sequence Alignment (MSA) plays a pivotal role in bioinformatics, facilitating various critical biological analyses, including the prediction of unknown protein structures and functions. While numerous methods are available for MSA, bioinspired algorithms stand out for their efficiency. Despite the growing research interest in addressing the MSA challenge, only a handful of comprehensive reviews have been undertaken in this domain. To bridge this gap, this study conducts a thorough analysis of bioinspired-based methods for MSA through a systematic literature review (SLR). By focusing on publications from 2010 to 2024, we aim to offer the most current insights into this field. Through rigorous eligibility criteria and quality standards, we identified 45 relevant papers for review. Our analysis predominantly concentrates on bioinspired-based techniques within the context of MSA. Notably, our findings highlight Genetic Algorithm and Memetic Optimization as the most commonly utilized algorithms for MSA. Furthermore, benchmark datasets such as BAliBASE and SABmark are frequently employed in evaluating MSA solutions. Structural-based methods emerge as the preferred approach for assessing MSA solutions, as revealed by our systematic literature review. Additionally, this study explores current trends, challenges, and unresolved issues in the realm of bioinspired algorithms for MSA, offering practitioners and researchers valuable insights and comprehensive understanding of the field.
Source: crossref · Quality: baseline
Research context
OpenAlex topics: Genomics and Phylogenetic Studies · Genome Rearrangement Algorithms · Algorithms and Data Compression
SciVX discovery tags are terminology-based. OpenAlex topics are source-provided classifications.
Affiliations
School of Computer Sciences, Universiti Sains Malaysia, Gelugor 11800, Penang, Malaysia
Department of Information Systems-Girls Section, King Khalid University, Mahayil 62529, Saudi Arabia
Computer & Information Sciences Department, Universiti Teknologi PETRONAS, Seri Iskandar 32610, Perak, Malaysia
Funding
The Deanship of Scientific Research at King Khalid University
References (100+)
Show source-provided references
1. Maiolo, L., Bruno, S.A., Lucarini, I., Pecora, A., De Iacovo, A., and Colace, L. (2018, January 28–31). Chemo-Resistive Gas Sensors Based on PbS Colloidal Quantum Dots. Proceedings of the 2018 IEEE SENSORS, New Delhi, India.10.1109/ICSENS.2018.8589724 ↗
2. Zika virus evolution and spread in the Americas10.1038/nature22402 ↗
3. Hybrid genetic algorithm method for efficient and robust evaluation of remaining useful life of supercapacitors10.1016/j.apenergy.2019.114169 ↗
4. Eddy, S.R. (2002). A memory-efficient dynamic programming algorithm for optimal alignment of a sequence to an RNA secondary structure. BMC Bioinform., 3.10.1186/1471-2105-3-18 ↗
5. Jakšić, Z., Devi, S., Jakšić, O., and Guha, K. (2023). A comprehensive review of bio-inspired optimization algorithms including applications in microelectronics and nanophotonics. Biomimetics, 8.10.3390/biomimetics8030278 ↗
6. Multiple sequence alignment modeling: Methods and applications10.1093/bib/bbv099 ↗
7. Amorim, A.R., Zafalon GF, D., de Godoi Contessoto, A., Valêncio, C.R., and Sato, L.M. (2021). Metaheuristics for multiple sequence alignment: A systematic review. Comput. Biol. Chem., 94.10.1016/j.compbiolchem.2021.107563 ↗
8. Comparing multi-objective metaheuristics for solving a three-objective formulation of multiple sequence alignment10.1007/s13748-017-0116-6 ↗
9. On the role of metaheuristic optimization in bioinformatics10.1111/itor.13164 ↗
10. Chaabane, L., Khelassi, A., Terziev, A., Andreopoulos, N., Jesus, M.D., and Estrela, V.V. (2021). Advances in Multidisciplinary Medical Technologies—Engineering, Modeling and Findings: Proceedings of the ICHSMT 2019, Springer International Publishing.
11. Solving multiple sequence alignment problems by using a swarm intelligent optimization based approach
12. Mishra, A., Tripathi, B.K., and Soam, S.S. (2020, January 2–4). A genetic algorithm based approach for the optimization of multiple sequence alignment. Proceedings of the 2020 International Conference on Computational Performance Evaluation (ComPE), Shillong, India.10.1109/ComPE49325.2020.9200060 ↗
13. Multiobjective artificial fish swarm algorithm for multiple sequence alignment
14. Yu, Y., Zhang, C., Ye, L., Yang, M., and Zhang, C. A Multi-objective Artificial Bee Colony Algorithm for Multiple Sequence Alignment. Proceedings of the International Conference on Simulation Tools and Techniques.
15. Hybrid multi-objective artificial bee colony for multiple sequence alignment10.1016/j.asoc.2015.12.034 ↗
16. Sequence alignment using machine learning for accurate template-based protein structure prediction10.1093/bioinformatics/btz483 ↗
17. Cascade and cluster of correlated reactions as causes of stochastic defects in extreme ultraviolet lithography10.1117/1.JMM.19.2.024601 ↗
18. Bawono, P., Dijkstra, M., Pirovano, W., Feenstra, A., Abeln, S., and Heringa, J. (2017). Bioinformatics: Data, Sequence Analysis, and Evolution, Springer.
19. Yadav, S.K., Jha, S.K., Singh, S., Dixit, P., Prakash, S., and Singh, A. (2022, January 23–25). Optimizing Multiple Sequence Alignment using Multi-objective Genetic Algorithms. Proceedings of the 2022 International Conference on Decision Aid Sciences and Applications (DASA) IEEE, Chiangrai, Thailand.10.1109/DASA54658.2022.9765131 ↗
20. A novel two-level particle swarm optimization approach for efficient multiple sequence alignment10.1007/s12293-015-0157-y ↗
21. MSA-GA: Multiple sequence alignment tool based on genetic approach
22. A Hybrid Approach using Progressive and Genetic Algorithms for Improvements in Multiple Sequence Alignments
23. Wang, J., Yu, L., Zhang, W., Gong, Y., Xu, Y., Wang, B., and Zhang, D. (2017, January 7–11). Irgan: A minimax game for unifying generative and discriminative information retrieval models. Proceedings of the 40th International ACM SIGIR Conference on Research and Development in Information Retrieval, Tokyo, Japan.10.1145/3077136.3080786 ↗
24. Ali, A.F., and Hassanien, A.E. (2015). Applications of Intelligent Optimization in Biology and Medicine: Current Trends and Open Problems, Springer International Publishing.
25. MAFFT: A novel method for rapid multiple sequence alignment based on fast Fourier transform10.1093/nar/gkf436 ↗
26. Who watches the watchmen? An appraisal of benchmarks for multiple sequence alignment10.1007/978-1-62703-646-7_4 ↗
27. Improved Hidden Markov Model training for multiple sequence alignment by a particle swarm optimization—Evolutionary algorithm hybrid10.1016/S0303-2647(03)00131-X ↗
28. MUMMALS: Multiple sequence alignment improved by using hidden Markov models with local structural information10.1093/nar/gkl514 ↗
29. Genetic algorithm with ant colony optimization (GA-ACO) for multiple sequence alignment10.1016/j.asoc.2006.10.012 ↗
30. SAGA: Sequence alignment by genetic algorithm10.1093/nar/24.8.1515 ↗
31. Nature Inspired Algorithms for Solving Multiple Sequence Alignment Problem: A Review10.1007/s11831-022-09769-w ↗
32. A comprehensive review on nature inspired computing algorithms for the diagnosis of chronic disorders in human beings10.1007/s13748-019-00191-1 ↗
33. Chatterjee, S., Hasibuzzaman, M.M., Iftiea, A., Mukharjee, T., and Nova, S.S. (2019, January 18–20). A hybrid genetic algorithm with chemical reaction optimization for multiple sequence alignment. Proceedings of the 22nd International Conference on Computer and Information Technology (ICCIT), Dhaka, Bangladesh.10.1109/ICCIT48885.2019.9038510 ↗
34. Review and classification of bio-inspired algorithms and their applications10.1007/s42235-020-0049-9 ↗
35. An exhaustive review of the metaheuristic algorithms for search and optimization: Taxonomy, applications, and open challenges10.1007/s10462-023-10470-y ↗
36. Chao, J., Tang, F., and Xu, L. (2022). Developments in algorithms for sequence alignment: A review. Biomolecules, 12.10.3390/biom12040546 ↗
37. MAFFT online service: Multiple sequence alignment, interactive sequence choice and visualization10.1093/bib/bbx108 ↗
38. MAFFT version 5: Improvement in accuracy of multiple sequence alignment10.1093/nar/gki198 ↗
39. Clustal Omega for making accurate alignments of many protein sequences10.1002/pro.3290 ↗
40. A review on multiple sequence alignment from the perspective of genetic algorithm10.1016/j.ygeno.2017.06.007 ↗
41. Parallel protein multiple sequence alignment approaches: A systematic literature review10.1007/s11227-022-04697-9 ↗
42. Comprehensive and systematic study on the fault tolerance architectures in cloud computing10.1142/S0218126620502400 ↗
43. Keele, S. (2007). Guidelines for Performing Systematic Literature Reviews in Software Engineering, Software Engineering Group. EBSE Technical Report EBSE-2007-01.
44. A systematic literature review: Opinion mining studies from mobile app store user reviews10.1016/j.jss.2016.11.027 ↗
45. Systematic literature reviews in software engineering–a systematic literature review10.1016/j.infsof.2008.09.009 ↗
46. Intelligent fraud detection in financial statements using machine learning and data mining: A systematic literature review10.1109/ACCESS.2021.3096799 ↗
47. An enhanced algorithm for multiple sequence alignment of protein sequences using genetic algorithm
48. Chentoufi, A., El Fatmi, A., Bekri, A., Benhlima, S., and Sabbane, M. (2017, January 17–19). Genetic algorithms and dynamic weighted sum method for RNA alignment. Proceedings of the 2017 Intelligent Systems and Computer Vision (ISCV), Fez, Morocco.10.1109/ISACV.2017.8054965 ↗
49. Multiple sequence alignment with affine gap by using multi-objective genetic algorithm10.1016/j.cmpb.2014.01.013 ↗
50. Amorim, A.R., Visotaky JM, V., de Godoi Contessoto, A., Neves, L.A., De Souza RC, G., Valêncio, C.R., and Zafalon GF, D. (2016, January 16–18). Performance improvement of genetic algorithm for multiple sequence alignment. Proceedings of the 2016 17th International Conference on Parallel and Distributed Computing, Applications and Technologies (PDCAT), Guangzhou, China.10.1109/PDCAT.2016.029 ↗
51. Progressive alignment method using genetic algorithm for multiple sequence alignment10.1109/TEVC.2011.2162849 ↗
52. Improvements in the sensibility of MSA-GA tool using COFFEE objective function
53. Rani, R.R., and Ramyachitra, D. (2017, January 26–28). Application of genetic algorithm by influencing the crossover parameters for multiple sequence alignment. Proceedings of the 2017 4th IEEE Uttar Pradesh Section International Conference on Electrical, Computer and Electronics 2017 (UPCON), Mathura, India.10.1109/UPCON.2017.8251018 ↗
54. Multi-objective formulation of multiple sequence alignment for phylogeny inference10.1109/TCYB.2020.3020308 ↗
55. Parallel multiple DNA sequence alignment using genetic algorithm and asynchronous advantage actor critic model10.1504/IJBRA.2022.128236 ↗
56. Multiple sequence alignments
57. A bi-objective function optimization approach for multiple sequence alignment using genetic algorithm10.1007/s00500-020-04917-5 ↗
58. Parallel niche pareto AlineaGA–an evolutionary multi-objective approach on multiple sequence alignment10.1515/jib-2011-174 ↗
59. Optimizing multiple sequence alignments using a genetic algorithm based on three objectives: Structural information, non-gaps percentage and totally conserved columns10.1093/bioinformatics/btt360 ↗
60. Cyclic genetic algorithm for multiple sequence alignment
61. Naznin, F., Sarker, R., and Essam, D. (2011). Vertical decomposition with genetic algorithm for multiple sequence alignment. BMC Bioinform., 12.10.1186/1471-2105-12-353 ↗
62. Luo, J., Zhang, L., and Liang, C. (2011, January 24–25). A multigroup parallel genetic algorithm for multiple sequence alignment. Proceedings of the Artificial Intelligence and Computational Intelligence: Third International Conference, AICI 2011, Taiyuan, China. Proceedings, Part I 3.
63. A new genetic algorithm for multiple sequence alignment10.1142/S146902681250023X ↗
64. Multiple sequence alignment with multi-objective metaheuristics. a comparative study10.1002/int.21892 ↗
65. NestMSA: A new multiple sequence alignment algorithm10.1007/s11227-020-03206-0 ↗
66. Multi-objective two-level swarm intelligence approach for multiple RNA sequence-structure alignment10.1016/j.swevo.2017.02.002 ↗
67. Zhan, Q., Wang, N., Jin, S., Tan, R., Jiang, Q., and Wang, Y. (2019). ProbPFP: A multiple sequence alignment algorithm combining hidden Markov model optimized by particle swarm optimization with partition function. BMC Bioinform., 20.10.1186/s12859-019-3132-7 ↗
68. A hybrid multi-objective memetic metaheuristic for multiple sequence alignment
69. Ibrahim, M.K., Yusof, U.K., Eisa, T.A.E., and Nasser, M. (2023). Enhanced Genetic Method for Optimizing Multiple Sequence Alignment. Mathematics, 11.10.3390/math11224578 ↗
70. Hybrid genetic algorithm and a fuzzy logic classifier for heart disease diagnosis10.1007/s12065-019-00327-1 ↗
71. Stakeholder-oriented multi-objective process optimization based on an improved genetic algorithm10.1016/j.compchemeng.2019.106618 ↗
72. A simple genetic algorithm for multiple sequence alignment
73. T-Coffee: A novel method for fast and accurate multiple sequence alignment10.1006/jmbi.2000.4042 ↗
74. Multiple sequence alignment using multi-objective based bacterial foraging optimization algorithm10.1016/j.biosystems.2016.10.005 ↗
75. BAliBASE 3.0: Latest developments of the multiple sequence alignment benchmark10.1002/prot.20527 ↗
76. MUSCLE: Multiple sequence alignment with high accuracy and high throughput10.1093/nar/gkh340 ↗
77. Multireservoir system operation optimization by hybrid quantum-behaved particle swarm optimization and heuristic constraint handling technique10.1016/j.jhydrol.2020.125477 ↗
78. A multimodal particle swarm optimization-based approach for image segmentation10.1016/j.eswa.2020.113233 ↗
79. Hybrid many-objective particle swarm optimization algorithm for green coal production problem10.1016/j.ins.2020.01.018 ↗
80. A deep learning model based on multi-objective particle swarm optimization for scene classification in unmanned aerial vehicles10.1109/ACCESS.2020.3011502 ↗
81. Classified perturbation mutation based particle swarm optimization algorithm for parameters extraction of photovoltaic models10.1016/j.enconman.2019.112138 ↗
82. Du, K.L., and Swamy, M.N. (2016). Search and Optimization by Metaheuristics: Techniques and Algorithms Inspired by Nature, Birkhäuser.10.1007/978-3-319-41192-7_3 ↗
83. Wang, C.R., Zhou, C.L., and Ma, J.W. (2005, January 18–21). An improved artificial fish-swarm algorithm and its application in feed-forward neural networks. Proceedings of the 2005 International Conference on Machine Learning and Cybernetics, Guangzhou, China.
84. IBBOMSA: An improved biogeography-based approach for multiple sequence alignment10.4137/EBO.S40457 ↗
85. MSAProbs: Multiple sequence alignment based on pair hidden Markov models and partition function posterior probabilities10.1093/bioinformatics/btq338 ↗
86. Rojas, M.G., Carballido, J.A., Olivera, A.C., and Vidal, P.J. (2020, January 1–4). A Memetic Cellular Genetic Algorithm for Multiple Sequence Alignment. Proceedings of the 2020 IEEE Congreso Bienal de Argentina 2020, (ARGENCON), Resistencia, Argentina.10.1109/ARGENCON49523.2020.9505544 ↗
87. Garg, P. (2010). A Comparison between Memetic algorithm and Genetic algorithm for the cryptanalysis of Simplified Data Encryption Standard algorithm. arXiv.
88. Rubio-Largo, Á., Vega-Rodríguez, M.A., and González-Álvarez, D.L. (2015, January 20–22). Parallel H4MSA for multiple sequence alignment. Proceedings of the Trustcom/BigDataSE/ISPA, Helsinki, Finland.10.1109/Trustcom.2015.639 ↗
89. A characteristic-based framework for multiple sequence aligners
90. DNA sequence compression using adaptive particle swarm optimization-based memetic algorithm10.1109/TEVC.2011.2160399 ↗
91. Yao, D., Jiang, M., You, X., Abulizi, A., and Hou, R. (2015, January 14–17). An algorithm of multiple sequence alignment based on consensus sequence searched by simulated annealing and star alignment. Proceedings of the 2015 International Symposium on Bioelectronics and Bioinformatics (ISBB), Beijing, China.10.1109/ISBB.2015.7344909 ↗
92. Hussein, A.M., Abdullah, R., AbdulRashid, N., and Ali, A.N.B. (2017, January 17–18). Protein multiple sequence alignment by basic flower pollination algorithm. Proceedings of the 2017 8th International Conference on Information Technology (ICIT), Amman, Jordan.10.1109/ICITECH.2017.8079955 ↗
93. Hussein, A.M., Abdullah, R., and AbdulRashid, N. (2019, January 9–11). Flower pollination algorithm with profile technique for multiple sequence alignment. Proceedings of the 2019 IEEE Jordan International Joint Conference on Electrical Engineering and Information Technology (JEEIT), Amman, Jordan.10.1109/JEEIT.2019.8717513 ↗
94. Altwaijry, N., Almasoud, M., Almalki, A., and Al-Turaiki, I. (2020, January 19–21). Multiple sequence alignment using a multi-objective artificial bee colony algorithm. Proceedings of the 2020 3rd International Conference on Computer Applications & Information Security (ICCAIS), Riyadh, Saudi Arabia.10.1109/ICCAIS48893.2020.9096734 ↗
95. A Decomposition and Dominance-Based Multi-objective Artificial Bee Colony Algorithm for Multiple Sequence Alignment
96. The Pfam protein families database10.1093/nar/gkh121 ↗
97. Lei, X., Sun, J., Xu, X., and Guo, L. (2010, January 23–26). Artificial bee colony algorithm for solving multiple sequence alignment. Proceedings of the 2010 IEEE Fifth International Conference on Bio-Inspired Computing: Theories and Applications (BIC-TA), Changsha, Cina.
98. Zemali, E.A., and Boukra, A. (2016, January 6–8). A new hybrid bio-inspired approach to resolve the multiple sequence alignment problem. Proceedings of the 2016 International Conference on Control, Decision and Information Technologies (CoDIT), Saint Julian’s, Malta.10.1109/CoDIT.2016.7593544 ↗
99. Bacterial foraging optimization–genetic algorithm for multiple sequence alignment with multi-objectives10.1038/s41598-017-09499-1 ↗
100. Shuffled frog-leaping algorithm: A memetic meta-heuristic for discrete optimization10.1080/03052150500384759 ↗