{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,11,15]],"date-time":"2025-11-15T17:22:49Z","timestamp":1763227369038,"version":"build-2065373602"},"reference-count":66,"publisher":"MDPI AG","issue":"2","license":[{"start":{"date-parts":[[2024,2,9]],"date-time":"2024-02-09T00:00:00Z","timestamp":1707436800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Computation"],"abstract":"<jats:p>Multiple sequence alignment (MSA) stands as a critical tool for understanding the evolutionary and functional relationships among biological sequences. Obtaining an exact solution for MSA, termed exact-MSA, is a significant challenge due to the combinatorial nature of the problem. Using the dynamic programming technique to solve MSA is recognized as a highly computationally complex algorithm. To cope with the computational demands of MSA, parallel computing offers the potential for significant speedup in MSA. In this study, we investigated the utilization of parallelization to solve the exact-MSA using three proposed novel approaches. In these approaches, we used multi-threading techniques to improve the performance of the dynamic programming algorithms in solving the exact-MSA. We developed and employed three parallel approaches, named diagonal traversing, blocking, and slicing, to improve MSA performance. The proposed method accelerated the exact-MSA algorithm by around 4\u00d7. The suggested approaches could be basic approaches to be combined with many existing techniques. These proposed approaches could serve as foundational elements, offering potential integration with existing techniques for comprehensive MSA enhancement.<\/jats:p>","DOI":"10.3390\/computation12020032","type":"journal-article","created":{"date-parts":[[2024,2,9]],"date-time":"2024-02-09T11:42:05Z","timestamp":1707478925000},"page":"32","update-policy":"https:\/\/doi.org\/10.3390\/mdpi_crossmark_policy","source":"Crossref","is-referenced-by-count":3,"title":["Accelerating Multiple Sequence Alignments Using Parallel Computing"],"prefix":"10.3390","volume":"12","author":[{"ORCID":"https:\/\/orcid.org\/0000-0003-4722-6632","authenticated-orcid":false,"given":"Qanita","family":"Bani Baker","sequence":"first","affiliation":[{"name":"Department of Computer Science, Jordan University of Science and Technology, P.O. Box 3030, Irbid 22110, Jordan"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-1185-6114","authenticated-orcid":false,"given":"Ruba A.","family":"Al-Hussien","sequence":"additional","affiliation":[{"name":"Department of Computer Science, Jordan University of Science and Technology, P.O. Box 3030, Irbid 22110, Jordan"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-9372-9076","authenticated-orcid":false,"given":"Mahmoud","family":"Al-Ayyoub","sequence":"additional","affiliation":[{"name":"Department of Information Technology, College of Engineering and IT, Ajman University, Ajman P.O. Box 346, United Arab Emirates"}]}],"member":"1968","published-online":{"date-parts":[[2024,2,9]]},"reference":[{"key":"ref_1","doi-asserted-by":"crossref","unstructured":"Diab, S., Nassereldine, A., Alser, M., G\u00f3mez Luna, J., Mutlu, O., and El Hajj, I. (2023). A framework for high-throughput sequence alignment using real processing-in-memory systems. Bioinformatics, 39.","DOI":"10.1093\/bioinformatics\/btad155"},{"key":"ref_2","doi-asserted-by":"crossref","first-page":"443","DOI":"10.1016\/0022-2836(70)90057-4","article-title":"A general method applicable to the search for similarities in the amino acid sequence of two proteins","volume":"48","author":"Needleman","year":"1970","journal-title":"J. Mol. Biol."},{"key":"ref_3","doi-asserted-by":"crossref","first-page":"195","DOI":"10.1016\/0022-2836(81)90087-5","article-title":"Identification of common molecular subsequences","volume":"147","author":"Smith","year":"1981","journal-title":"J. Mol. Biol."},{"key":"ref_4","doi-asserted-by":"crossref","first-page":"194","DOI":"10.1109\/TCBB.2009.69","article-title":"Pairwise statistical significance of local sequence alignment using sequence-specific and position-specific substitution matrices","volume":"8","author":"Agrawal","year":"2009","journal-title":"IEEE\/ACM Trans. Comput. Biol. Bioinform."},{"key":"ref_5","doi-asserted-by":"crossref","first-page":"368","DOI":"10.1016\/j.sbi.2006.04.004","article-title":"Multiple sequence alignment","volume":"16","author":"Edgar","year":"2006","journal-title":"Curr. Opin. Struct. Biol."},{"key":"ref_6","unstructured":"Bellman, R.E., and Dreyfus, S.E. (2015). Applied Dynamic Programming, Princeton University Press."},{"key":"ref_7","doi-asserted-by":"crossref","unstructured":"Chao, J., Tang, F., and Xu, L. (2022). Developments in algorithms for sequence alignment: A review. Biomolecules, 12.","DOI":"10.3390\/biom12040546"},{"key":"ref_8","doi-asserted-by":"crossref","unstructured":"Saeed, F., and Khokhar, A. (2009). An Overview of Multiple Sequence Alignment Systems. arXiv.","DOI":"10.1007\/978-3-642-00727-9_34"},{"key":"ref_9","doi-asserted-by":"crossref","first-page":"1009","DOI":"10.1093\/bib\/bbv099","article-title":"Multiple sequence alignment modeling: Methods and applications","volume":"17","author":"Chatzou","year":"2016","journal-title":"Briefings Bioinform."},{"key":"ref_10","doi-asserted-by":"crossref","unstructured":"Zemali, E.a., and Boukra, A. (2016, January 6\u20138). 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\u2019s, Malta.","DOI":"10.1109\/CoDIT.2016.7593544"},{"key":"ref_11","doi-asserted-by":"crossref","unstructured":"Amorim, A.R., Zafalon, G.F.D., de Godoi Contessoto, A., Val\u00eancio, C.R., and Sato, L.M. (2021). Metaheuristics for multiple sequence alignment: A systematic review. Comput. Biol. Chem., 94.","DOI":"10.1016\/j.compbiolchem.2021.107563"},{"key":"ref_12","doi-asserted-by":"crossref","first-page":"233","DOI":"10.1016\/S0304-3975(97)00023-6","article-title":"Approximation algorithms for multiple sequence alignment","volume":"182","author":"Bafna","year":"1997","journal-title":"Theor. Comput. Sci."},{"key":"ref_13","doi-asserted-by":"crossref","first-page":"871","DOI":"10.1089\/cmb.2018.0079","article-title":"Massively parallel implementation of sequence alignment with basic local alignment search tool using parallel computing in java library","volume":"25","author":"Nowicki","year":"2018","journal-title":"J. Comput. Biol."},{"key":"ref_14","unstructured":"Chiaromonte, F., Yap, V.B., and Miller, W. (2001). Biocomputing 2002, World Scientific."},{"key":"ref_15","doi-asserted-by":"crossref","unstructured":"Haque, W., Aravind, A., and Reddy, B. (2009, January 11\u201316). Pairwise sequence alignment algorithms: A survey. Proceedings of the 2009 Conference on Information Science, Technology and Applications, Sliema, Malta.","DOI":"10.1145\/1551950.1551980"},{"key":"ref_16","doi-asserted-by":"crossref","first-page":"1301","DOI":"10.1093\/bioinformatics\/bth090","article-title":"A comparison of scoring functions for protein sequence profile alignment","volume":"20","author":"Edgar","year":"2004","journal-title":"Bioinformatics"},{"key":"ref_17","doi-asserted-by":"crossref","first-page":"473","DOI":"10.1093\/bib\/bbq015","article-title":"A survey of sequence alignment algorithms for next-generation sequencing","volume":"11","author":"Li","year":"2010","journal-title":"Briefings Bioinform."},{"key":"ref_18","doi-asserted-by":"crossref","first-page":"996","DOI":"10.1093\/bioinformatics\/btt098","article-title":"Improvements on bicriteria pairwise sequence alignment: Algorithms and applications","volume":"29","author":"Abbasi","year":"2013","journal-title":"Bioinformatics"},{"key":"ref_19","doi-asserted-by":"crossref","first-page":"705","DOI":"10.1016\/0022-2836(82)90398-9","article-title":"An improved algorithm for matching biological sequences","volume":"162","author":"Gotoh","year":"1982","journal-title":"J. Mol. Biol."},{"key":"ref_20","doi-asserted-by":"crossref","first-page":"63","DOI":"10.1016\/0076-6879(90)83007-V","article-title":"Rapid and sensitive sequence comparison with FASTP and FASTA","volume":"183","author":"Pearson","year":"1990","journal-title":"Methods Enzym."},{"key":"ref_21","doi-asserted-by":"crossref","first-page":"403","DOI":"10.1016\/S0022-2836(05)80360-2","article-title":"Basic local alignment search tool","volume":"215","author":"Altschul","year":"1990","journal-title":"J. Mol. Biol."},{"key":"ref_22","doi-asserted-by":"crossref","first-page":"276","DOI":"10.1016\/S0168-9525(00)02024-2","article-title":"EMBOSS: The European molecular biology open software suite","volume":"16","author":"Rice","year":"2000","journal-title":"Trends Genet."},{"key":"ref_23","doi-asserted-by":"crossref","unstructured":"Daily, J. (2016). Parasail: SIMD C library for global, semi-global, and local pairwise sequence alignments. BMC Bioinform., 17.","DOI":"10.1186\/s12859-016-0930-z"},{"key":"ref_24","doi-asserted-by":"crossref","first-page":"3094","DOI":"10.1093\/bioinformatics\/bty191","article-title":"Minimap2: Pairwise alignment for nucleotide sequences","volume":"34","author":"Li","year":"2018","journal-title":"Bioinformatics"},{"key":"ref_25","doi-asserted-by":"crossref","first-page":"56","DOI":"10.1016\/j.eswa.2018.01.019","article-title":"ASCA-PSO: Adaptive sine cosine optimization algorithm integrated with particle swarm for pairwise local sequence alignment","volume":"99","author":"Issa","year":"2018","journal-title":"Expert Syst. Appl."},{"key":"ref_26","doi-asserted-by":"crossref","unstructured":"Aguado-Puig, Q., Marco-Sola, S., Moure, J.C., Matzoros, C., Castells-Rufas, D., Espinosa, A., and Moreto, M. (2022). WFA-GPU: Gap-affine pairwise alignment using GPUs. bioRxiv.","DOI":"10.1101\/2022.04.18.488374"},{"key":"ref_27","first-page":"012028","article-title":"Accelerating Smith-Waterman Algorithm for Faster Sequence Alignment using Graphical Processing Unit","volume":"Volume 2161","author":"Kaur","year":"2022","journal-title":"Proceedings of the Journal of Physics: Conference Series"},{"key":"ref_28","doi-asserted-by":"crossref","unstructured":"Fakirah, M., Shehab, M.A., Jararweh, Y., and Al-Ayyoub, M. (2015, January 17\u201320). Accelerating needleman-wunsch global alignment algorithm with gpus. Proceedings of the 2015 IEEE\/ACS 12th International Conference of Computer Systems and Applications (AICCSA), Marrakech, Morocco.","DOI":"10.1109\/AICCSA.2015.7507113"},{"key":"ref_29","doi-asserted-by":"crossref","unstructured":"Balhaf, K., Shehab, M.A., Wala\u2019a, T., Al-Ayyoub, M., Al-Saleh, M., and Jararweh, Y. (2016, January 5\u20137). Using gpus to speed-up levenshtein edit distance computation. Proceedings of the 2016 7th International Conference on Information and Communication Systems (ICICS), Irbid, Jordan.","DOI":"10.1109\/IACS.2016.7476090"},{"key":"ref_30","doi-asserted-by":"crossref","first-page":"3961","DOI":"10.1007\/s11042-017-5092-0","article-title":"Improving the performance of the needleman-wunsch algorithm using parallelization and vectorization techniques","volume":"78","author":"Jararweh","year":"2019","journal-title":"Multimed. Tools Appl."},{"key":"ref_31","doi-asserted-by":"crossref","unstructured":"Shehab, M.A., Ghadawi, A.A., Alawneh, L., Al-Ayyoub, M., and Jararweh, Y. (2017, January 4\u20136). A hybrid CPU-GPU implementation to accelerate multiple pairwise protein sequence alignment. Proceedings of the 2017 8th International Conference on Information and Communication Systems (ICICS), Irbid, Jordan.","DOI":"10.1109\/IACS.2017.7921938"},{"key":"ref_32","doi-asserted-by":"crossref","first-page":"105","DOI":"10.1007\/978-1-62703-646-7_6","article-title":"Clustal Omega, accurate alignment of very large numbers of sequences","volume":"1079","author":"Sievers","year":"2014","journal-title":"Mult. Seq. Alignment Methods"},{"key":"ref_33","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1186\/s13015-015-0057-1","article-title":"Instability in progressive multiple sequence alignment algorithms","volume":"10","author":"Boyce","year":"2015","journal-title":"Algorithms Mol. Biol."},{"key":"ref_34","doi-asserted-by":"crossref","first-page":"1408","DOI":"10.1093\/bioinformatics\/bti159","article-title":"Evaluation of iterative alignment algorithms for multiple alignment","volume":"21","author":"Wallace","year":"2005","journal-title":"Bioinformatics"},{"key":"ref_35","doi-asserted-by":"crossref","unstructured":"Notredame, C. (2007). Recent evolutions of multiple sequence alignment algorithms. PLoS Comput. Biol., 3.","DOI":"10.1371\/journal.pcbi.0030123"},{"key":"ref_36","unstructured":"Ali, A.F., and Hassanien, A.E. (2015). Applications of Intelligent Optimization in Biology and Medicine: Current Trends and Open Problems, Springer."},{"key":"ref_37","unstructured":"Riaz, T., Wang, Y., and Li, K.B. (2004, January 18\u201322). Multiple sequence alignment using tabu search. Proceedings of the Second Conference on Asia-Pacific Bioinformatics, Dunedin, New Zealand."},{"key":"ref_38","doi-asserted-by":"crossref","first-page":"419","DOI":"10.1093\/bioinformatics\/10.4.419","article-title":"Multiple sequence alignment using simulated annealing","volume":"10","author":"Kim","year":"1994","journal-title":"Bioinformatics"},{"key":"ref_39","unstructured":"Xu, F., and Chen, Y. (2009, January 16\u201319). A method for multiple sequence alignment based on particle swarm optimization. Proceedings of the Emerging Intelligent Computing Technology and Applications. With Aspects of Artificial Intelligence: 5th International Conference on Intelligent Computing, ICIC 2009, Ulsan, Republic of Korea. Proceedings 5."},{"key":"ref_40","doi-asserted-by":"crossref","first-page":"419","DOI":"10.1016\/j.ygeno.2017.06.007","article-title":"A review on multiple sequence alignment from the perspective of genetic algorithm","volume":"109","author":"Chowdhury","year":"2017","journal-title":"Genomics"},{"key":"ref_41","doi-asserted-by":"crossref","first-page":"195","DOI":"10.1007\/s13748-017-0116-6","article-title":"Comparing multi-objective metaheuristics for solving a three-objective formulation of multiple sequence alignment","volume":"6","author":"Nebro","year":"2017","journal-title":"Prog. Artif. Intell."},{"key":"ref_42","doi-asserted-by":"crossref","unstructured":"Smirnov, V. (2021). Recursive MAGUS: Scalable and accurate multiple sequence alignment. PLoS Comput. Biol., 17.","DOI":"10.1101\/2021.04.09.439137"},{"key":"ref_43","doi-asserted-by":"crossref","unstructured":"Steenwyk, J.L., Buida III, T.J., Li, Y., Shen, X.X., and Rokas, A. (2020). ClipKIT: A multiple sequence alignment trimming software for accurate phylogenomic inference. PLoS Biol., 18.","DOI":"10.1101\/2020.06.08.140384"},{"key":"ref_44","doi-asserted-by":"crossref","unstructured":"Lassmann, T., and Sonnhammer, E.L. (2005). Kalign\u2014An accurate and fast multiple sequence alignment algorithm. BMC Bioinform., 6.","DOI":"10.1186\/1471-2105-6-298"},{"key":"ref_45","doi-asserted-by":"crossref","first-page":"330","DOI":"10.1101\/gr.2821705","article-title":"ProbCons: Probabilistic consistency-based multiple sequence alignment","volume":"15","author":"Do","year":"2005","journal-title":"Genome Res."},{"key":"ref_46","doi-asserted-by":"crossref","first-page":"1792","DOI":"10.1093\/nar\/gkh340","article-title":"MUSCLE: Multiple sequence alignment with high accuracy and high throughput","volume":"32","author":"Edgar","year":"2004","journal-title":"Nucleic Acids Res."},{"key":"ref_47","doi-asserted-by":"crossref","first-page":"3059","DOI":"10.1093\/nar\/gkf436","article-title":"MAFFT: A novel method for rapid multiple sequence alignment based on fast Fourier transform","volume":"30","author":"Katoh","year":"2002","journal-title":"Nucleic Acids Res."},{"key":"ref_48","doi-asserted-by":"crossref","first-page":"205","DOI":"10.1006\/jmbi.2000.4042","article-title":"T-Coffee: A novel method for fast and accurate multiple sequence alignment","volume":"302","author":"Notredame","year":"2000","journal-title":"J. Mol. Biol."},{"key":"ref_49","doi-asserted-by":"crossref","first-page":"211","DOI":"10.1093\/bioinformatics\/15.3.211","article-title":"DIALIGN 2: Improvement of the segment-to-segment approach to multiple sequence alignment","volume":"15","author":"Morgenstern","year":"1999","journal-title":"Bioinformatics"},{"key":"ref_50","doi-asserted-by":"crossref","first-page":"4673","DOI":"10.1093\/nar\/22.22.4673","article-title":"CLUSTAL W: Improving the sensitivity of progressive multiple sequence alignment through sequence weighting, position-specific gap penalties and weight matrix choice","volume":"22","author":"Thompson","year":"1994","journal-title":"Nucleic Acids Res."},{"key":"ref_51","unstructured":"Mojbak, J., and Pedersen, C. (2010). Exact Multiple Sequence Alignment Using Forward Dynamic Programming, Bioinformatics Research Center."},{"key":"ref_52","first-page":"721","article-title":"Exact multiple sequence alignment by synchronized decision diagrams","volume":"33","author":"Hosseininasab","year":"2021","journal-title":"INFORMS J. Comput."},{"key":"ref_53","unstructured":"Gonz\u00e1lez-Dom\u00ednguez, J. (2021). Multiple Sequence Alignment, Springer."},{"key":"ref_54","doi-asserted-by":"crossref","first-page":"2535","DOI":"10.1038\/s41467-021-22869-8","article-title":"CopulaNet: Learning residue co-evolution directly from multiple sequence alignment for protein structure prediction","volume":"12","author":"Ju","year":"2021","journal-title":"Nat. Commun."},{"key":"ref_55","doi-asserted-by":"crossref","first-page":"1201","DOI":"10.1007\/s11227-022-04697-9","article-title":"Parallel protein multiple sequence alignment approaches: A systematic literature review","volume":"79","author":"Chavoya","year":"2023","journal-title":"J. Supercomput."},{"key":"ref_56","doi-asserted-by":"crossref","unstructured":"Helal, M., El-Gindy, H., Mullin, L., and Gaeta, B. (2008, January 10\u201312). Parallelizing optimal multiple sequence alignment by dynamic programming. Proceedings of the 2008 IEEE International Symposium on Parallel and Distributed Processing with Applications, Sydney, NSW, Australia.","DOI":"10.1109\/ISPA.2008.93"},{"key":"ref_57","doi-asserted-by":"crossref","first-page":"62","DOI":"10.1016\/j.compbiolchem.2015.05.004","article-title":"CUDA ClustalW: An efficient parallel algorithm for progressive multiple sequence alignment on Multi-GPUs","volume":"58","author":"Hung","year":"2015","journal-title":"Comput. Biol. Chem."},{"key":"ref_58","doi-asserted-by":"crossref","first-page":"267","DOI":"10.1093\/bioinformatics\/9.3.267","article-title":"Multiple sequence alignment by parallel simulated annealing","volume":"9","author":"Ishikawa","year":"1993","journal-title":"Bioinformatics"},{"key":"ref_59","doi-asserted-by":"crossref","first-page":"32","DOI":"10.1016\/j.jpdc.2012.04.004","article-title":"G-MSA\u2014A GPU-based, fast and accurate algorithm for multiple sequence alignment","volume":"73","author":"Blazewicz","year":"2013","journal-title":"J. Parallel Distrib. Comput."},{"key":"ref_60","doi-asserted-by":"crossref","first-page":"2475","DOI":"10.1093\/bioinformatics\/btv177","article-title":"HAlign: Fast multiple similar DNA\/RNA sequence alignment based on the centre star strategy","volume":"31","author":"Zou","year":"2015","journal-title":"Bioinformatics"},{"key":"ref_61","doi-asserted-by":"crossref","unstructured":"Wan, S., and Zou, Q. (2017). HAlign-II: Efficient ultra-large multiple sequence alignment and phylogenetic tree reconstruction with distributed and parallel computing. Algorithms Mol. Biol., 12.","DOI":"10.1186\/s13015-017-0116-x"},{"key":"ref_62","doi-asserted-by":"crossref","unstructured":"Zou, Q., Wan, S., Zeng, X., and Ma, Z.S. (2017). Reconstructing evolutionary trees in parallel for massive sequences. BMC Syst. Biol., 11.","DOI":"10.1186\/s12918-017-0476-3"},{"key":"ref_63","doi-asserted-by":"crossref","first-page":"1230","DOI":"10.1089\/cmb.2017.0040","article-title":"Multiple sequence alignment based on a suffix tree and center-star strategy: A linear method for multiple nucleotide sequence alignment on spark parallel framework","volume":"24","author":"Su","year":"2017","journal-title":"J. Comput. Biol."},{"key":"ref_64","doi-asserted-by":"crossref","unstructured":"Chen, X., Wang, C., Tang, S., Yu, C., and Zou, Q. (2017). CMSA: A heterogeneous CPU\/GPU computing system for multiple similar RNA\/DNA sequence alignment. BMC Bioinform., 18.","DOI":"10.1186\/s12859-017-1725-6"},{"key":"ref_65","doi-asserted-by":"crossref","unstructured":"Siriwardena, T., and Ranasinghe, D. (2010, January 17\u201319). Accelerating global sequence alignment using CUDA compatible multi-core GPU. Proceedings of the 2010 Fifth International Conference on Information and Automation for Sustainability, Colombo, Sri Lanka.","DOI":"10.1109\/ICIAFS.2010.5715660"},{"key":"ref_66","doi-asserted-by":"crossref","unstructured":"Al-Hussien, R.A., Baker, Q.B., and Al-Ayyoub, M. (2018, January 29\u201331). Fast exact sequence alignment using parallel computing. Proceedings of the 2018 9th International Conference on Information and Communication Systems (ICICS), Security Lille, France.","DOI":"10.1109\/IACS.2018.8355464"}],"container-title":["Computation"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.mdpi.com\/2079-3197\/12\/2\/32\/pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,10,10]],"date-time":"2025-10-10T13:58:06Z","timestamp":1760104686000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.mdpi.com\/2079-3197\/12\/2\/32"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2024,2,9]]},"references-count":66,"journal-issue":{"issue":"2","published-online":{"date-parts":[[2024,2]]}},"alternative-id":["computation12020032"],"URL":"https:\/\/doi.org\/10.3390\/computation12020032","relation":{},"ISSN":["2079-3197"],"issn-type":[{"type":"electronic","value":"2079-3197"}],"subject":[],"published":{"date-parts":[[2024,2,9]]}}}