{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,5,5]],"date-time":"2026-05-05T16:55:18Z","timestamp":1778000118440,"version":"3.51.4"},"reference-count":26,"publisher":"Oxford University Press (OUP)","issue":"4","license":[{"start":{"date-parts":[[2023,5,17]],"date-time":"2023-05-17T00:00:00Z","timestamp":1684281600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/academic.oup.com\/pages\/standard-publication-reuse-rights"}],"funder":[{"DOI":"10.13039\/501100001809","name":"National Natural Science Foundation of China","doi-asserted-by":"publisher","award":["62250028"],"award-info":[{"award-number":["62250028"]}],"id":[{"id":"10.13039\/501100001809","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100001809","name":"National Natural Science Foundation of China","doi-asserted-by":"publisher","award":["62271353"],"award-info":[{"award-number":["62271353"]}],"id":[{"id":"10.13039\/501100001809","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100001809","name":"National Natural Science Foundation of China","doi-asserted-by":"publisher","award":["62102065"],"award-info":[{"award-number":["62102065"]}],"id":[{"id":"10.13039\/501100001809","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100001809","name":"National Natural Science Foundation of China","doi-asserted-by":"publisher","award":["62001311"],"award-info":[{"award-number":["62001311"]}],"id":[{"id":"10.13039\/501100001809","id-type":"DOI","asserted-by":"publisher"}]},{"name":"Sichuan Provincial Science Fund for Distinguished Young Scholars","award":["2021JDJQ0025"],"award-info":[{"award-number":["2021JDJQ0025"]}]},{"DOI":"10.13039\/501100018542","name":"Natural Science Foundation of Sichuan Province","doi-asserted-by":"publisher","award":["2022NSFSC0926"],"award-info":[{"award-number":["2022NSFSC0926"]}],"id":[{"id":"10.13039\/501100018542","id-type":"DOI","asserted-by":"publisher"}]},{"name":"Municipal Government of Quzhou","award":["2022D020"],"award-info":[{"award-number":["2022D020"]}]},{"name":"Joint Funds for the Innovation of Science and Technology, Fujian Province","award":["2022J05055"],"award-info":[{"award-number":["2022J05055"]}]},{"name":"Fujian Medical University Research Foundation of Talented Scholars","award":["XRCZX2022003"],"award-info":[{"award-number":["XRCZX2022003"]}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2023,7,20]]},"abstract":"<jats:title>Abstract<\/jats:title>\n               <jats:p>Multiple sequence alignment is widely used for sequence analysis, such as identifying important sites and phylogenetic analysis. Traditional methods, such as progressive alignment, are time-consuming. To address this issue, we introduce StarTree, a novel method to fast construct a guide tree by combining sequence clustering and hierarchical clustering. Furthermore, we develop a new heuristic similar region detection algorithm using the FM-index and apply the k-banded dynamic program to the profile alignment. We also introduce a win-win alignment algorithm that applies the central star strategy within the clusters to fast the alignment process, then uses the progressive strategy to align the central-aligned profiles, guaranteeing the final alignment's accuracy. We present WMSA 2 based on these improvements and compare the speed and accuracy with other popular methods. The results show that the guide tree made by the StarTree clustering method can lead to better accuracy than that of PartTree while consuming less time and memory than that of UPGMA and mBed methods on datasets with thousands of sequences. During the alignment of simulated data sets, WMSA 2 can consume less time and memory while ranking at the top of Q and TC scores. The WMSA 2 is still better at the time, and memory efficiency on the real datasets and ranks at the top on the average sum of pairs score. For the alignment of 1 million SARS-CoV-2 genomes, the win-win mode of WMSA 2 significantly decreased the consumption time than the former version. The source code and data are available at https:\/\/github.com\/malabz\/WMSA2.<\/jats:p>","DOI":"10.1093\/bib\/bbad190","type":"journal-article","created":{"date-parts":[[2023,5,18]],"date-time":"2023-05-18T16:15:48Z","timestamp":1684426548000},"source":"Crossref","is-referenced-by-count":14,"title":["WMSA 2: a multiple DNA\/RNA sequence alignment tool implemented with accurate progressive mode and a fast win-win mode combining the center star and progressive strategies"],"prefix":"10.1093","volume":"24","author":[{"given":"Juntao","family":"Chen","sequence":"first","affiliation":[{"name":"Quzhou People\u2019s Hospital, Quzhou Affiliated Hospital of Wenzhou Medical University , Quzhou, China, , Quzhou, China, and the , Chengdu, China"},{"name":"Yangtze Delta Region Institute (Quzhou), University of Electronic Science and Technology of China , Quzhou, China, , Quzhou, China, and the , Chengdu, China"},{"name":"Institute of Fundamental and Frontier Sciences, University of Electronic Science and Technology of China , Quzhou, China, , Quzhou, China, and the , Chengdu, China"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Jiannan","family":"Chao","sequence":"additional","affiliation":[{"name":"Yangtze Delta Region Institute (Quzhou), University of Electronic Science and Technology of China , Quzhou, China, and the , Chengdu, China"},{"name":"Institute of Fundamental and Frontier Sciences, University of Electronic Science and Technology of China , Quzhou, China, and the , Chengdu, China"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Huan","family":"Liu","sequence":"additional","affiliation":[{"name":"School of Computer Science and Technology, Southwest University of Science and Technology , Mianyang, China"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Fenglong","family":"Yang","sequence":"additional","affiliation":[{"name":"Department of Bioinformatics, Fujian Key Laboratory of Medical Bioinformatics, School of Medical Technology and Engineering, Fujian Medical University , Fuzhou, China"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Quan","family":"Zou","sequence":"additional","affiliation":[{"name":"Yangtze Delta Region Institute (Quzhou), University of Electronic Science and Technology of China , Quzhou, China and the , Chengdu, China"},{"name":"Institute of Fundamental and Frontier Sciences, University of Electronic Science and Technology of China , Quzhou, China and the , Chengdu, China"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Furong","family":"Tang","sequence":"additional","affiliation":[{"name":"Quzhou People\u2019s Hospital, Quzhou Affiliated Hospital of Wenzhou Medical University, Quzhou, China, and Department of Basic Medical Sciences, School of Medicine, Tsinghua University , Beijing, China"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"286","published-online":{"date-parts":[[2023,5,17]]},"reference":[{"issue":"1","key":"2023072020053025600_ref1","doi-asserted-by":"crossref","first-page":"bbab519","DOI":"10.1093\/bib\/bbab519","article-title":"A novel fast multiple nucleotide sequence alignment method based on FM-index","volume":"23","author":"Liu","year":"2022","journal-title":"Brief Bioinform"},{"issue":"14","key":"2023072020053025600_ref2","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"},{"issue":"1","key":"2023072020053025600_ref3","doi-asserted-by":"crossref","first-page":"539","DOI":"10.1038\/msb.2011.75","article-title":"Fast, scalable generation of high-quality protein multiple sequence alignments using Clustal Omega","volume":"7","author":"Sievers","year":"2011","journal-title":"Mol Syst Biol"},{"issue":"1","key":"2023072020053025600_ref4","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1186\/1471-2105-5-113","article-title":"MUSCLE: a multiple sequence alignment method with reduced time and space complexity","volume":"5","author":"Edgar","year":"2004","journal-title":"BMC Bioinform"},{"issue":"6","key":"2023072020053025600_ref5","doi-asserted-by":"crossref","first-page":"1928","DOI":"10.1093\/bioinformatics\/btz795","article-title":"Kalign 3: multiple sequence alignment of large datasets","volume":"36","author":"Lassmann","year":"2020","journal-title":"Bioinformatics"},{"issue":"1","key":"2023072020053025600_ref6","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"},{"issue":"8","key":"2023072020053025600_ref7","doi-asserted-by":"crossref","first-page":"msac166","DOI":"10.1093\/molbev\/msac166","article-title":"HAlign 3: fast multiple alignment of ultra-large numbers of similar DNA\/RNA sequences","volume":"39","author":"Tang","year":"2022","journal-title":"Mol Biol Evol"},{"issue":"22","key":"2023072020053025600_ref8","doi-asserted-by":"crossref","first-page":"5019","DOI":"10.1093\/bioinformatics\/btac658","article-title":"WMSA: a novel method for multiple sequence alignment of DNA sequences","volume":"38","author":"Wei","year":"2022","journal-title":"Bioinformatics"},{"issue":"4","key":"2023072020053025600_ref9","doi-asserted-by":"crossref","first-page":"351","DOI":"10.1007\/BF02603120","article-title":"Progressive sequence alignment as a prerequisitetto correct phylogenetic trees","volume":"25","author":"Feng","year":"1987","journal-title":"J Mol Evol"},{"key":"2023072020053025600_ref10","first-page":"1409","article-title":"A statistical method for evaluating systematic relationships","volume":"38","author":"Sokal","year":"1958","journal-title":"Univ Kans Sci Bull"},{"issue":"4","key":"2023072020053025600_ref11","first-page":"406","article-title":"The neighbor-joining method: a new method for reconstructing phylogenetic trees","volume":"4","author":"Saitou","year":"1987","journal-title":"Mol Biol Evol"},{"issue":"6","key":"2023072020053025600_ref12","doi-asserted-by":"crossref","first-page":"205","DOI":"10.1016\/j.ipl.2007.07.002","article-title":"Optimal implementations of UPGMA and other common clustering algorithms","volume":"104","author":"Gronau","year":"2007","journal-title":"Inf Process Lett"},{"issue":"3","key":"2023072020053025600_ref13","doi-asserted-by":"crossref","first-page":"372","DOI":"10.1093\/bioinformatics\/btl592","article-title":"PartTree: an algorithm to build an approximate tree from a large number of unaligned sequences","volume":"23","author":"Katoh","year":"2007","journal-title":"Bioinformatics"},{"issue":"1","key":"2023072020053025600_ref14","doi-asserted-by":"crossref","first-page":"21","DOI":"10.1186\/1748-7188-5-21","article-title":"Sequence embedding for fast construction of guide trees for multiple sequence alignment","volume":"5","author":"Blackshields","year":"2010","journal-title":"Algorithms Mol Biol"},{"issue":"3","key":"2023072020053025600_ref15","doi-asserted-by":"crossref","first-page":"e9490","DOI":"10.1371\/journal.pone.0009490","article-title":"FastTree 2 \u2013 approximately maximum-likelihood trees for large alignments","volume":"5","author":"Price","year":"2010","journal-title":"PloS One"},{"issue":"5","key":"2023072020053025600_ref16","doi-asserted-by":"crossref","first-page":"377","DOI":"10.1089\/cmb.2014.0156","article-title":"PASTA: ultra-large multiple sequence alignment for nucleotide and amino-acid sequences","volume":"22","author":"Mirarab","year":"2015","journal-title":"J Comput Biol"},{"issue":"12","key":"2023072020053025600_ref17","doi-asserted-by":"crossref","first-page":"1666","DOI":"10.1093\/bioinformatics\/btaa992","article-title":"MAGUS: multiple sequence alignment using graph clustering","volume":"37","author":"Smirnov","year":"2021","journal-title":"Bioinformatics"},{"issue":"18","key":"2023072020053025600_ref18","doi-asserted-by":"crossref","first-page":"2948","DOI":"10.1093\/bioinformatics\/btx354","article-title":"PASTASpark: multiple sequence alignment meets big data","volume":"33","author":"Abu\u00edn","year":"2017","journal-title":"Bioinformatics"},{"issue":"10","key":"2023072020053025600_ref19","doi-asserted-by":"crossref","first-page":"e1008950","DOI":"10.1371\/journal.pcbi.1008950","article-title":"Recursive MAGUS: scalable and accurate multiple sequence alignment","volume":"17","author":"Smirnov","year":"2021","journal-title":"PLoS Comput Biol"},{"key":"2023072020053025600_ref20","doi-asserted-by":"crossref","first-page":"322","DOI":"10.1016\/j.phpro.2012.05.069","article-title":"A novel center star multiple sequence alignment algorithm based on affine gap penalty and k-band","volume":"33","author":"Zou","year":"2012","journal-title":"Physics Procedia"},{"issue":"15","key":"2023072020053025600_ref21","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"},{"issue":"1","key":"2023072020053025600_ref22","doi-asserted-by":"crossref","first-page":"25","DOI":"10.1186\/s13015-017-0116-x","article-title":"HAlign-II: efficient ultra-large multiple sequence alignment and phylogenetic tree reconstruction with distributed and parallel computing","volume":"12","author":"Wan","year":"2017","journal-title":"Algorithms Mol Biol"},{"issue":"22","key":"2023072020053025600_ref23","doi-asserted-by":"crossref","first-page":"3274","DOI":"10.1093\/bioinformatics\/btu541","article-title":"Fast construction of FM-index for long sequence reads","volume":"30","author":"Li","year":"2014","journal-title":"Bioinformatics"},{"key":"2023072020053025600_ref24","first-page":"1","volume-title":"2010 Gateway Computing Environments Workshop (GCE), 2010","author":"Miller"},{"issue":"6155","key":"2023072020053025600_ref25","doi-asserted-by":"crossref","first-page":"257","DOI":"10.1126\/science.1241844","article-title":"Ancient DNA reveals key stages in the formation of central European mitochondrial genetic diversity","volume":"342","author":"Brandt","year":"2013","journal-title":"Science"},{"issue":"7798","key":"2023072020053025600_ref26","doi-asserted-by":"crossref","first-page":"265","DOI":"10.1038\/s41586-020-2008-3","article-title":"A new coronavirus associated with human respiratory disease in China","volume":"579","author":"Wu","year":"2020","journal-title":"Nature"}],"container-title":["Briefings in Bioinformatics"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/academic.oup.com\/bib\/article-pdf\/24\/4\/bbad190\/50916761\/bbad190.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"syndication"},{"URL":"https:\/\/academic.oup.com\/bib\/article-pdf\/24\/4\/bbad190\/50916761\/bbad190.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,7,20]],"date-time":"2023-07-20T20:06:51Z","timestamp":1689883611000},"score":1,"resource":{"primary":{"URL":"https:\/\/academic.oup.com\/bib\/article\/doi\/10.1093\/bib\/bbad190\/7169135"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2023,5,17]]},"references-count":26,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2023,7,20]]}},"URL":"https:\/\/doi.org\/10.1093\/bib\/bbad190","relation":{},"ISSN":["1467-5463","1477-4054"],"issn-type":[{"value":"1467-5463","type":"print"},{"value":"1477-4054","type":"electronic"}],"subject":[],"published-other":{"date-parts":[[2023,7]]},"published":{"date-parts":[[2023,5,17]]},"article-number":"bbad190"}}