{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,7,2]],"date-time":"2026-07-02T05:07:43Z","timestamp":1782968863348,"version":"3.54.5"},"reference-count":44,"publisher":"MDPI AG","issue":"5","license":[{"start":{"date-parts":[[2024,5,10]],"date-time":"2024-05-10T00:00:00Z","timestamp":1715299200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"funder":[{"name":"Natural Sciences and Engineering Research Council of Canada (NSERC)","award":["RGPIN-2024-05641"],"award-info":[{"award-number":["RGPIN-2024-05641"]}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Algorithms"],"abstract":"<jats:p>The standard approach for constructing a phylogenetic tree from a set of sequences consists of two key stages. First, a multiple sequence alignment (MSA) of the sequences is computed. The aligned data are then used to reconstruct the phylogenetic tree. The accuracy of the resulting tree heavily relies on the quality of the MSA. The quality of the popularly used progressive sequence alignment depends on a guide tree, which determines the order of aligning sequences. Most MSA methods use pairwise comparisons to generate a distance matrix and reconstruct the guide tree. However, when dealing with highly diverged sequences, constructing a good guide tree is challenging. In this work, we propose an alternative approach using three-way dynamic programming alignment to generate the distance matrix and the guide tree. This three-way alignment incorporates information from additional sequences to compute evolutionary distances more accurately. Using simulated datasets on two symmetric and asymmetric trees, we compared MAFFT with its default guide tree with MAFFT with a guide tree produced using the three-way alignment. We found that (1) the three-way alignment can reconstruct better guide trees than those from the most accurate options of MAFFT, and (2) the better guide tree, on average, leads to more accurate phylogenetic reconstruction. However, the improvement over the L-INS-i option of MAFFT is small, attesting to the excellence of the alignment quality of MAFFT. Surprisingly, the two criteria for choosing the best MSA (phylogenetic accuracy and sum-of-pair score) conflict with each other.<\/jats:p>","DOI":"10.3390\/a17050205","type":"journal-article","created":{"date-parts":[[2024,5,10]],"date-time":"2024-05-10T05:25:47Z","timestamp":1715318747000},"page":"205","update-policy":"https:\/\/doi.org\/10.3390\/mdpi_crossmark_policy","source":"Crossref","is-referenced-by-count":4,"title":["Three-Way Alignment Improves Multiple Sequence Alignment of Highly Diverged Sequences"],"prefix":"10.3390","volume":"17","author":[{"given":"Mahbubeh","family":"Askari Rad","sequence":"first","affiliation":[{"name":"Department of Biology, University of Ottawa, 30 Marie Curie, P.O. Box 450, Ottawa, ON K1N 6N5, Canada"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-6074-8764","authenticated-orcid":false,"given":"Alibek","family":"Kruglikov","sequence":"additional","affiliation":[{"name":"Department of Biology, University of Ottawa, 30 Marie Curie, P.O. Box 450, Ottawa, ON K1N 6N5, Canada"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-3092-7566","authenticated-orcid":false,"given":"Xuhua","family":"Xia","sequence":"additional","affiliation":[{"name":"Department of Biology, University of Ottawa, 30 Marie Curie, P.O. Box 450, Ottawa, ON K1N 6N5, Canada"},{"name":"Ottawa Institute of Systems Biology, Ottawa, ON K1H 8M5, Canada"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"1968","published-online":{"date-parts":[[2024,5,10]]},"reference":[{"key":"ref_1","doi-asserted-by":"crossref","unstructured":"Xia, X. (2021). Post-Alignment Adjustment and Its Automation. Genes, 12.","DOI":"10.3390\/genes12111809"},{"key":"ref_2","doi-asserted-by":"crossref","first-page":"792","DOI":"10.1093\/molbev\/msi066","article-title":"Comparison of the Accuracies of Several Phylogenetic Methods Using Protein and DNA Sequences","volume":"22","author":"Hall","year":"2005","journal-title":"Mol. Biol. Evol."},{"key":"ref_3","doi-asserted-by":"crossref","first-page":"287","DOI":"10.1002\/(SICI)1521-1878(199804)20:4<287::AID-BIES4>3.0.CO;2-N","article-title":"Effects of Sequence Alignment Procedures on Estimates of Phylogeny","volume":"20","author":"Goldman","year":"1998","journal-title":"BioEssays"},{"key":"ref_4","doi-asserted-by":"crossref","first-page":"428","DOI":"10.1093\/oxfordjournals.molbev.a025779","article-title":"Effects of Nucleotide Sequence Alignment on Phylogeny Estimation: A Case Study of 18S rDNAs of Apicomplexa","volume":"14","author":"Morrison","year":"1997","journal-title":"Mol. Biol. Evol."},{"key":"ref_5","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_6","doi-asserted-by":"crossref","first-page":"909","DOI":"10.1038\/nbt0704-909","article-title":"What Is Dynamic Programming?","volume":"22","author":"Eddy","year":"2004","journal-title":"Nat. Biotechnol."},{"key":"ref_7","doi-asserted-by":"crossref","first-page":"35","DOI":"10.1137\/0128004","article-title":"Minimal Mutation Trees of Sequences","volume":"28","author":"Sankoff","year":"1975","journal-title":"SIAM J. Appl. Math."},{"key":"ref_8","doi-asserted-by":"crossref","first-page":"133","DOI":"10.1007\/BF01732471","article-title":"Frequency of Insertion-Deletion, Transversion, and Transition in the Evolution of 5S Ribosomal RNA","volume":"7","author":"Sankoff","year":"1976","journal-title":"J. Mol. Evol."},{"key":"ref_9","doi-asserted-by":"crossref","first-page":"341","DOI":"10.1145\/360825.360861","article-title":"A Linear Space Algorithm for Computing Maximal Common Subsequences","volume":"18","author":"Hirschberg","year":"1975","journal-title":"Commun. ACM"},{"key":"ref_10","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_11","doi-asserted-by":"crossref","first-page":"351","DOI":"10.1007\/BF02603120","article-title":"Progressive Sequence Alignment as a Prerequisite to Correct Phylogenetic Trees","volume":"25","author":"Feng","year":"1987","journal-title":"J. Mol. Evol."},{"key":"ref_12","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_13","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_14","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 alignment11Edited by J. Thornton","volume":"302","author":"Notredame","year":"2000","journal-title":"J. Mol. Biol."},{"key":"ref_15","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_16","doi-asserted-by":"crossref","first-page":"2682","DOI":"10.1093\/nar\/27.13.2682","article-title":"A Comprehensive Comparison of Multiple Sequence Alignment Programs","volume":"27","author":"Thompson","year":"1999","journal-title":"Nucleic Acids Res."},{"key":"ref_17","doi-asserted-by":"crossref","unstructured":"Noah, K.E., Hao, J., Li, L., Sun, X., Foley, B., Yang, Q., and Xia, X. (2020). Major Revisions in Arthropod Phylogeny through Improved Supermatrix, with Support for Two Possible Waves of Land Invasion by Chelicerates. Evol. Bioinform. Online, 16.","DOI":"10.1177\/1176934320903735"},{"key":"ref_18","doi-asserted-by":"crossref","first-page":"1079","DOI":"10.1038\/nature08742","article-title":"Arthropod Relationships Revealed by Phylogenomic Analysis of Nuclear Protein-Coding Sequences","volume":"463","author":"Regier","year":"2010","journal-title":"Nature"},{"key":"ref_19","doi-asserted-by":"crossref","first-page":"331","DOI":"10.1016\/j.ympev.2016.07.001","article-title":"PhyPA: Phylogenetic Method with Pairwise Sequence Alignment Outperforms Likelihood Methods in Phylogenetics Involving Highly Diverged Sequences","volume":"102","author":"Xia","year":"2016","journal-title":"Mol. Phylogenetics Evol."},{"key":"ref_20","doi-asserted-by":"crossref","unstructured":"Bellamy-Royds, A.B., and Turcotte, M. (2007). Can Clustal-Style Progressive Pairwise Alignment of Multiple Sequences Be Used in RNA Secondary Structure Prediction?. BMC Bioinform., 8.","DOI":"10.1186\/1471-2105-8-190"},{"key":"ref_21","doi-asserted-by":"crossref","first-page":"230","DOI":"10.1504\/IJBRA.2005.007581","article-title":"Simultaneous Alignment and Structure Prediction of Three RNA Sequences","volume":"1","author":"Masoumi","year":"2005","journal-title":"Int. J. Bioinform. Res. Appl."},{"key":"ref_22","doi-asserted-by":"crossref","first-page":"87","DOI":"10.1080\/10635150050207401","article-title":"Phylogenetic Relationship Among Horseshoe Crab Species: Effect of Substitution Models on Phylogenetic Analyses","volume":"49","author":"Xia","year":"2000","journal-title":"Syst. Biol."},{"key":"ref_23","doi-asserted-by":"crossref","first-page":"283","DOI":"10.1080\/10635150390196948","article-title":"18S Ribosomal RNA and Tetrapod Phylogeny","volume":"52","author":"Xia","year":"2003","journal-title":"Syst. Biol."},{"key":"ref_24","doi-asserted-by":"crossref","unstructured":"Zhan, Q., Ye, Y., Lam, T.-W., Yiu, S.-M., Wang, Y., and Ting, H.-F. (2015). Improving Multiple Sequence Alignment by Using Better Guide Trees. BMC Bioinform., 16.","DOI":"10.1186\/1471-2105-16-S5-S4"},{"key":"ref_25","doi-asserted-by":"crossref","first-page":"1011","DOI":"10.1093\/bioinformatics\/btt095","article-title":"Measuring Guide-Tree Dependency of Inferred Gaps in Progressive Aligners","volume":"29","year":"2013","journal-title":"Bioinformatics"},{"key":"ref_26","doi-asserted-by":"crossref","first-page":"1759","DOI":"10.1093\/molbev\/msq066","article-title":"An Alignment Confidence Score Capturing Robustness to Guide Tree Uncertainty","volume":"27","author":"Penn","year":"2010","journal-title":"Mol. Biol. Evol."},{"key":"ref_27","unstructured":"Nelesen, S., Liu, K., Zhao, D., Linder, C.R., and Warnow, T. (2007). Biocomputing 2008, World Scientific."},{"key":"ref_28","doi-asserted-by":"crossref","unstructured":"Ye, Y., Cheung, D.W., Wang, Y., Yiu, S.-M., Zhan, Q., Lam, T.-W., and Ting, H.-F. (2013, January 22\u201325). GLProbs: Aligning Multiple Sequences Adaptively. Proceedings of the International Conference on Bioinformatics, Computational Biology and Biomedical Informatics, Wshington, DC, USA.","DOI":"10.1145\/2506583.2506611"},{"key":"ref_29","doi-asserted-by":"crossref","unstructured":"Kruspe, M., and Stadler, P.F. (2007). Progressive Multiple Sequence Alignments from Triplets. BMC Bioinform., 8.","DOI":"10.1186\/1471-2105-8-254"},{"key":"ref_30","doi-asserted-by":"crossref","unstructured":"Chien, R.-T., Liao, Y.-L., Wang, C.-A., Li, Y.-C., and Lu, Y.-C. (2018, January 30\u201331). Three-Dimensional Dynamic Programming Accelerator for Multiple Sequence Alignment. Proceedings of the 2018 IEEE Nordic Circuits and Systems Conference (NORCAS): NORCHIP and International Symposium of System-on-Chip (SoC), Tallinn, Estonia.","DOI":"10.1109\/NORCHIP.2018.8573523"},{"key":"ref_31","doi-asserted-by":"crossref","first-page":"327","DOI":"10.1016\/S0022-5193(86)80112-6","article-title":"Alignment of Three Biological Sequences with an Efficient Traceback Procedure","volume":"121","author":"Gotoh","year":"1986","journal-title":"J. Theor. Biol."},{"key":"ref_32","doi-asserted-by":"crossref","first-page":"1073","DOI":"10.1137\/0148063","article-title":"The Multiple Sequence Alignment Problem in Biology","volume":"48","author":"Carrillo","year":"1988","journal-title":"SIAM J. Appl. Math."},{"key":"ref_33","doi-asserted-by":"crossref","first-page":"7","DOI":"10.1145\/381771.381773","article-title":"Alignment of Three Sequences in Quadratic Space","volume":"1","author":"Huang","year":"1993","journal-title":"SIGAPP Appl. Comput. Rev."},{"key":"ref_34","doi-asserted-by":"crossref","unstructured":"Ly-Trong, N., Naser-Khdour, S., Lanfear, R., and Minh, B.Q. (2022). AliSim: A Fast and Versatile Phylogenetic Sequence Simulator for the Genomic Era. Mol. Biol. Evol., 39.","DOI":"10.1093\/molbev\/msac092"},{"key":"ref_35","doi-asserted-by":"crossref","first-page":"275","DOI":"10.1093\/bioinformatics\/8.3.275","article-title":"The Rapid Generation of Mutation Data Matrices from Protein Sequences","volume":"8","author":"Jones","year":"1992","journal-title":"Bioinformatics"},{"key":"ref_36","doi-asserted-by":"crossref","first-page":"307","DOI":"10.1093\/sysbio\/syq010","article-title":"New Algorithms and Methods to Estimate Maximum-Likelihood Phylogenies: Assessing the Performance of PhyML 3.0","volume":"59","author":"Guindon","year":"2010","journal-title":"Syst. Biol."},{"key":"ref_37","doi-asserted-by":"crossref","first-page":"131","DOI":"10.1016\/0025-5564(81)90043-2","article-title":"Comparison of Phylogenetic Trees","volume":"53","author":"Robinson","year":"1981","journal-title":"Math. Biosci."},{"key":"ref_38","doi-asserted-by":"crossref","first-page":"289","DOI":"10.1093\/bioinformatics\/btg412","article-title":"APE: Analyses of Phylogenetics and Evolution in R Language","volume":"20","author":"Paradis","year":"2004","journal-title":"Bioinformatics"},{"key":"ref_39","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_40","doi-asserted-by":"crossref","first-page":"543","DOI":"10.1093\/bioinformatics\/11.5.543","article-title":"A Weighting System and Aigorithm for Aligning Many Phylogenetically Related Sequences","volume":"11","author":"Gotoh","year":"1995","journal-title":"Bioinformatics"},{"key":"ref_41","doi-asserted-by":"crossref","first-page":"647","DOI":"10.1016\/0022-2836(89)90234-9","article-title":"Weights for Data Related by a Tree","volume":"207","author":"Altschul","year":"1989","journal-title":"J. Mol. Biol."},{"key":"ref_42","doi-asserted-by":"crossref","first-page":"127","DOI":"10.1002\/prot.20527","article-title":"BAliBASE 3.0: Latest Developments of the Multiple Sequence Alignment Benchmark","volume":"61","author":"Thompson","year":"2005","journal-title":"Proteins Struct. Funct. Bioinform."},{"key":"ref_43","doi-asserted-by":"crossref","first-page":"6968","DOI":"10.1038\/s41467-022-34630-w","article-title":"Muscle5: High-Accuracy Alignment Ensembles Enable Unbiased Assessments of Sequence Homology and Phylogeny","volume":"13","author":"Edgar","year":"2022","journal-title":"Nat. Commun."},{"key":"ref_44","doi-asserted-by":"crossref","first-page":"509","DOI":"10.1007\/BF02462264","article-title":"Consistency of Optimal Sequence Alignments","volume":"52","author":"Gotoh","year":"1990","journal-title":"Bull. Math. Biol."}],"container-title":["Algorithms"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.mdpi.com\/1999-4893\/17\/5\/205\/pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,10,10]],"date-time":"2025-10-10T14:43:26Z","timestamp":1760107406000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.mdpi.com\/1999-4893\/17\/5\/205"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2024,5,10]]},"references-count":44,"journal-issue":{"issue":"5","published-online":{"date-parts":[[2024,5]]}},"alternative-id":["a17050205"],"URL":"https:\/\/doi.org\/10.3390\/a17050205","relation":{},"ISSN":["1999-4893"],"issn-type":[{"value":"1999-4893","type":"electronic"}],"subject":[],"published":{"date-parts":[[2024,5,10]]}}}