{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,9,8]],"date-time":"2026-09-08T14:07:53Z","timestamp":1788876473064,"version":"build-2803163510"},"reference-count":24,"publisher":"Oxford University Press (OUP)","issue":"12","license":[{"start":{"date-parts":[[2024,11,28]],"date-time":"2024-11-28T00:00:00Z","timestamp":1732752000000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"funder":[{"DOI":"10.13039\/501100001809","name":"National Natural Science Foundation of China","doi-asserted-by":"publisher","award":["62425107"],"award-info":[{"award-number":["62425107"]}],"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":["62450002"],"award-info":[{"award-number":["62450002"]}],"id":[{"id":"10.13039\/501100001809","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2024,11,28]]},"abstract":"<jats:title>Abstract<\/jats:title>\n               <jats:sec>\n                  <jats:title>Motivation<\/jats:title>\n                  <jats:p>HAlign is a high-performance multiple sequence alignment software based on the star alignment strategy, which is the preferred choice for rapidly aligning large numbers of sequences. HAlign3, implemented in Java, is the latest version capable of aligning an ultra-large number of similar DNA\/RNA sequences. However, HAlign3 still struggles with long sequences and extremely large numbers of sequences.<\/jats:p>\n               <\/jats:sec>\n               <jats:sec>\n                  <jats:title>Results<\/jats:title>\n                  <jats:p>To address this issue, we have implemented HAlign4 in C++. In this version, we replaced the original suffix tree with Burrows\u2013Wheeler Transform and introduced the wavefront alignment algorithm to further optimize both time and memory efficiency. Experiments show that HAlign4 significantly outperforms HAlign3 in runtime and memory usage in both single-threaded and multi-threaded configurations, while maintains high alignment accuracy comparable to MAFFT. HAlign4 can complete the alignment of 10 million coronavirus disease 2019 (COVID-19) sequences in about 12\u2009min and 300\u00a0GB of memory using 96 threads, demonstrating its efficiency and practicality for large-scale alignment on standard workstations.<\/jats:p>\n               <\/jats:sec>\n               <jats:sec>\n                  <jats:title>Availability and implementation<\/jats:title>\n                  <jats:p>Source code is available at https:\/\/github.com\/malabz\/HAlign-4, dataset is available at https:\/\/zenodo.org\/records\/13934503.<\/jats:p>\n               <\/jats:sec>","DOI":"10.1093\/bioinformatics\/btae718","type":"journal-article","created":{"date-parts":[[2024,11,28]],"date-time":"2024-11-28T16:56:55Z","timestamp":1732813015000},"source":"Crossref","is-referenced-by-count":20,"title":["HAlign 4: a new strategy for rapidly aligning millions of sequences"],"prefix":"10.1093","volume":"40","author":[{"ORCID":"https:\/\/orcid.org\/0009-0001-3743-2304","authenticated-orcid":false,"given":"Tong","family":"Zhou","sequence":"first","affiliation":[{"name":"Institute of Fundamental and Frontier Sciences, University of Electronic Science and Technology of China , Chengdu, Sichuan 610054,","place":["China"]},{"name":"Yangtze Delta Region Institute (Quzhou), University of Electronic Science and Technology of China , Quzhou, Zhejiang 324003,","place":["China"]}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0009-0002-1788-3084","authenticated-orcid":false,"given":"Pinglu","family":"Zhang","sequence":"additional","affiliation":[{"name":"Institute of Fundamental and Frontier Sciences, University of Electronic Science and Technology of China , Chengdu, Sichuan 610054,","place":["China"]},{"name":"Yangtze Delta Region Institute (Quzhou), University of Electronic Science and Technology of China , Quzhou, Zhejiang 324003,","place":["China"]}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-6406-1142","authenticated-orcid":false,"given":"Quan","family":"Zou","sequence":"additional","affiliation":[{"name":"Institute of Fundamental and Frontier Sciences, University of Electronic Science and Technology of China , Chengdu, Sichuan 610054,","place":["China"]},{"name":"Yangtze Delta Region Institute (Quzhou), University of Electronic Science and Technology of China , Quzhou, Zhejiang 324003,","place":["China"]}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Wu","family":"Han","sequence":"additional","affiliation":[{"name":"Department of Statistics, Stanford University , Stanford, CA 94305-4065,","place":["United States"]}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"286","published-online":{"date-parts":[[2024,11,28]]},"reference":[{"key":"2024121419110430700_btae718-B1","doi-asserted-by":"crossref","first-page":"297","DOI":"10.1016\/S0022-5193(89)80196-1","article-title":"Gap costs for multiple sequence alignment","volume":"138","author":"Altschul","year":"1989","journal-title":"J Theor Biol"},{"key":"2024121419110430700_btae718-B2","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":"2024121419110430700_btae718-B4","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":"2024121419110430700_btae718-B5","doi-asserted-by":"crossref","first-page":"1879","DOI":"10.1093\/molbev\/msp098","article-title":"INDELible: a flexible simulator of biological sequence evolution","volume":"26","author":"Fletcher","year":"2009","journal-title":"Mol Biol Evol"},{"key":"2024121419110430700_btae718-B6","doi-asserted-by":"crossref","first-page":"1466","DOI":"10.1038\/s41587-019-0333-6","article-title":"Large multiple sequence alignments with a root-to-leaf regressive method","volume":"37","author":"Garriga","year":"2019","journal-title":"Nat Biotechnol"},{"key":"2024121419110430700_btae718-B7","doi-asserted-by":"crossref","first-page":"D749","DOI":"10.1093\/nar\/gkj010","article-title":"mtDB: human mitochondrial genome database, a resource for population genetics and medical sciences","volume":"34","author":"Ingman","year":"2006","journal-title":"Nucleic Acids Res"},{"key":"2024121419110430700_btae718-B8","doi-asserted-by":"crossref","first-page":"558","DOI":"10.1145\/368996.369025","article-title":"Topological sorting of large networks","volume":"5","author":"Kahn","year":"1962","journal-title":"Commun ACM"},{"key":"2024121419110430700_btae718-B9","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":"2024121419110430700_btae718-B10","doi-asserted-by":"crossref","first-page":"100296","DOI":"10.1016\/j.xinn.2022.100296","article-title":"MPoxVR: a comprehensive genomic resource for monkeypox virus variant surveillance","volume":"3","author":"Ma","year":"2022","journal-title":"The Innovation"},{"key":"2024121419110430700_btae718-B11","doi-asserted-by":"crossref","first-page":"e1005944","DOI":"10.1371\/journal.pcbi.1005944","article-title":"MUMmer4: a fast and versatile genome alignment system","volume":"14","author":"Mar\u00e7ais","year":"2018","journal-title":"PLoS Comput Biol"},{"key":"2024121419110430700_btae718-B12","doi-asserted-by":"crossref","first-page":"btad074","DOI":"10.1093\/bioinformatics\/btad074","article-title":"Optimal gap-affine alignment in O (s) space","volume":"39","author":"Marco-Sola","year":"2023","journal-title":"Bioinformatics"},{"key":"2024121419110430700_btae718-B13","doi-asserted-by":"crossref","first-page":"456","DOI":"10.1093\/bioinformatics\/btaa777","article-title":"Fast gap-affine pairwise alignment using the wavefront algorithm","volume":"37","author":"Marco-Sola","year":"2021","journal-title":"Bioinformatics"},{"key":"2024121419110430700_btae718-B14","doi-asserted-by":"crossref","first-page":"D568","DOI":"10.1093\/nar\/gkt919","article-title":"IMG\/M 4 version of the integrated metagenome comparative analysis system","volume":"42","author":"Markowitz","year":"2014","journal-title":"Nucleic Acids Res"},{"key":"2024121419110430700_btae718-B15","author":"Michael Burrows","year":"1994"},{"key":"2024121419110430700_btae718-B16","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":"Methods Mol Biol"},{"key":"2024121419110430700_btae718-B17","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":"Molecular Biology and Evolution"},{"key":"2024121419110430700_btae718-B18","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1093\/gbe\/evae102","article-title":"Application and comparison of machine learning and database-based methods in taxonomic classification of high-throughput sequencing data","volume":"16","author":"Tian","year":"2024","journal-title":"Genome Biol Evol"},{"key":"2024121419110430700_btae718-B19","doi-asserted-by":"crossref","first-page":"249","DOI":"10.1007\/BF01206331","article-title":"On-line construction of suffix trees","volume":"14","author":"Ukkonen","year":"1995","journal-title":"Algorithmica"},{"key":"2024121419110430700_btae718-B20","doi-asserted-by":"crossref","first-page":"1","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"},{"key":"2024121419110430700_btae718-B21","doi-asserted-by":"crossref","first-page":"337","DOI":"10.1089\/cmb.1994.1.337","article-title":"On the complexity of multiple sequence alignment","volume":"1","author":"Wang","year":"1994","journal-title":"J Comput Biol"},{"key":"2024121419110430700_btae718-B22","doi-asserted-by":"crossref","first-page":"D590","DOI":"10.1093\/nar\/gkv1322","article-title":"The MG-RAST metagenomics database and portal in 2015","volume":"44","author":"Wilke","year":"2016","journal-title":"Nucleic Acids Res"},{"key":"2024121419110430700_btae718-B23","doi-asserted-by":"crossref","first-page":"e1011988","DOI":"10.1371\/journal.pcbi.1011988","article-title":"TPMA: a two pointers meta-alignment tool to ensemble different multiple nucleic acid sequence alignments","volume":"20","author":"Zhai","year":"2024","journal-title":"PLoS Comput Biol"},{"key":"2024121419110430700_btae718-B24","doi-asserted-by":"crossref","first-page":"btae014","DOI":"10.1093\/bioinformatics\/btae014","article-title":"FMAlign2: a novel fast multiple nucleotide sequence alignment method for ultralong datasets","volume":"40","author":"Zhang","year":"2024","journal-title":"Bioinformatics"},{"key":"2024121419110430700_btae718-B25","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"}],"container-title":["Bioinformatics"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/academic.oup.com\/bioinformatics\/advance-article-pdf\/doi\/10.1093\/bioinformatics\/btae718\/60896115\/btae718.pdf","content-type":"application\/pdf","content-version":"am","intended-application":"syndication"},{"URL":"https:\/\/academic.oup.com\/bioinformatics\/article-pdf\/40\/12\/btae718\/61165112\/btae718.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"syndication"},{"URL":"https:\/\/academic.oup.com\/bioinformatics\/article-pdf\/40\/12\/btae718\/61165112\/btae718.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,12,14]],"date-time":"2024-12-14T19:11:22Z","timestamp":1734203482000},"score":1,"resource":{"primary":{"URL":"https:\/\/academic.oup.com\/bioinformatics\/article\/doi\/10.1093\/bioinformatics\/btae718\/7912339"}},"subtitle":[],"editor":[{"given":"Xin","family":"Gao","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"editor"}]}],"short-title":[],"issued":{"date-parts":[[2024,11,28]]},"references-count":24,"journal-issue":{"issue":"12","published-print":{"date-parts":[[2024,11,28]]}},"URL":"https:\/\/doi.org\/10.1093\/bioinformatics\/btae718","relation":{},"ISSN":["1367-4811"],"issn-type":[{"value":"1367-4811","type":"electronic"}],"subject":[],"published-other":{"date-parts":[[2024,12]]},"published":{"date-parts":[[2024,11,28]]},"article-number":"btae718"}}