{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,4,9]],"date-time":"2026-04-09T00:09:58Z","timestamp":1775693398610,"version":"3.50.1"},"reference-count":46,"publisher":"Oxford University Press (OUP)","license":[{"start":{"date-parts":[[2026,1,5]],"date-time":"2026-01-05T00:00:00Z","timestamp":1767571200000},"content-version":"vor","delay-in-days":4,"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":["62472344"],"award-info":[{"award-number":["62472344"]}],"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":["62452107"],"award-info":[{"award-number":["62452107"]}],"id":[{"id":"10.13039\/501100001809","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100005320","name":"Xidian University","doi-asserted-by":"publisher","award":["TZJH2024027"],"award-info":[{"award-number":["TZJH2024027"]}],"id":[{"id":"10.13039\/501100005320","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2026,1,21]]},"abstract":"<jats:title>Abstract<\/jats:title>\n                  <jats:sec>\n                    <jats:title>Background<\/jats:title>\n                    <jats:p>Multiple sequence alignment (MSA) continues to be a central challenge in comparative genomics, where the quality of alignment plays a crucial role in determining the accuracy of downstream analyses. However, the challenge of large-scale alignment remains significant.<\/jats:p>\n                  <\/jats:sec>\n                  <jats:sec>\n                    <jats:title>Findings<\/jats:title>\n                    <jats:p>This article introduces deMEM, a novel and effective framework for DNA multiple sequence alignment, which enables existing MSA methods such as MAFFT to handle extremely large sequences. deMEM is a 3-stage alignment process: (i) representing maximum exact matches using a de Bruijn graph and clustering them based on their area, (ii) employing a novel divide-and-conquer framework for alignment, and (iii) providing profile\u2013profile alignment between different clusters.<\/jats:p>\n                  <\/jats:sec>\n                  <jats:sec>\n                    <jats:title>Conclusions<\/jats:title>\n                    <jats:p>DeMEM enables existing methods like MAFFT to align an extremely large number of sequences, including long sequences that cannot be directly aligned, such as those in a dataset of a thousand monkeypox virus genomes. The deMEM package is free and available at https:\/\/github.com\/malabz\/deMEM.<\/jats:p>\n                  <\/jats:sec>","DOI":"10.1093\/gigascience\/giaf163","type":"journal-article","created":{"date-parts":[[2026,1,3]],"date-time":"2026-01-03T12:24:58Z","timestamp":1767443098000},"source":"Crossref","is-referenced-by-count":2,"title":["deMEM: a novel divide-and-conquer framework based on de Bruijn graph for scalable multiple sequence alignment"],"prefix":"10.1093","volume":"15","author":[{"ORCID":"https:\/\/orcid.org\/0000-0003-4843-3350","authenticated-orcid":false,"given":"Yanming","family":"Wei","sequence":"first","affiliation":[{"name":"School of Computer Science and Technology, Xidian University , No. 266, Xinglong Section of Xifeng Road, Chang\u2019an Zone, Xi\u2019an, 710126 ,","place":["China"]},{"name":"Institute of Digital Health, Yangtze Delta Region Institute (Quzhou), University of Electronic Science and Technology of China , University of Electronic Science and Technology of China, No. 1, Chengdian Road, Kecheng Zone, Quzhou, 324003 ,","place":["China"]}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0009-0005-1546-1437","authenticated-orcid":false,"given":"Zhaoyang","family":"Huang","sequence":"additional","affiliation":[{"name":"School of Computer Science and Technology, Xidian University , No. 266, Xinglong Section of Xifeng Road, Chang\u2019an Zone, Xi\u2019an, 710126 ,","place":["China"]}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0009-0002-1788-3084","authenticated-orcid":false,"given":"Pinglu","family":"Zhang","sequence":"additional","affiliation":[{"name":"Institute of Digital Health, Yangtze Delta Region Institute (Quzhou), University of Electronic Science and Technology of China , University of Electronic Science and Technology of China, No. 1, Chengdian Road, Kecheng Zone, Quzhou, 324003 ,","place":["China"]},{"name":"Institute of Fundamental and Frontier Sciences, University of Electronic Science and Technology of China , No. 2006, Xiyuan Avenue, Pidu Zone, Chengdu, 610054 ,","place":["China"]}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-3475-5431","authenticated-orcid":false,"given":"Yizheng","family":"Wang","sequence":"additional","affiliation":[{"name":"Institute of Digital Health, Yangtze Delta Region Institute (Quzhou), University of Electronic Science and Technology of China , University of Electronic Science and Technology of China, No. 1, Chengdian Road, Kecheng Zone, Quzhou, 324003 ,","place":["China"]},{"name":"Institute of Fundamental and Frontier Sciences, University of Electronic Science and Technology of China , No. 2006, Xiyuan Avenue, Pidu Zone, Chengdu, 610054 ,","place":["China"]}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Yan","family":"Li","sequence":"additional","affiliation":[{"name":"School of Management, Xi\u2019an Polytechnic University , No.19, Jinhua South Road, Xi\u2019an, 710048 ,","place":["China"]}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-8351-3332","authenticated-orcid":false,"given":"Liang","family":"Yu","sequence":"additional","affiliation":[{"name":"School of Computer Science and Technology, Xidian University , No. 266, Xinglong Section of Xifeng Road, Chang\u2019an Zone, Xi\u2019an, 710126 ,","place":["China"]}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-6406-1142","authenticated-orcid":false,"given":"Quan","family":"Zou","sequence":"additional","affiliation":[{"name":"Institute of Digital Health, Yangtze Delta Region Institute (Quzhou), University of Electronic Science and Technology of China , University of Electronic Science and Technology of China, No. 1, Chengdian Road, Kecheng Zone, Quzhou, 324003 ,","place":["China"]},{"name":"Institute of Fundamental and Frontier Sciences, University of Electronic Science and Technology of China , No. 2006, Xiyuan Avenue, Pidu Zone, Chengdu, 610054 ,","place":["China"]}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"286","published-online":{"date-parts":[[2026,1,5]]},"reference":[{"key":"2026020607364484500_bib1","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1155\/2015\/690873","article-title":"Bioinformatics methods and biological interpretation for next-generation sequencing data","volume":"2015","author":"Wang","year":"2015","journal-title":"Biomed Res Int"},{"key":"2026020607364484500_bib2","doi-asserted-by":"publisher","first-page":"btae046","DOI":"10.1093\/bioinformatics\/btae046","article-title":"NanoCon: contrastive learning-based deep hybrid network for nanopore methylation detection","volume":"40","author":"Yin","year":"2024","journal-title":"Bioinformatics"},{"key":"2026020607364484500_bib3","doi-asserted-by":"publisher","first-page":"915","DOI":"10.1038\/nbt.1966","article-title":"Efficient de novo assembly of single-cell bacterial genomes from short-read data sets","volume":"29","author":"Chitsaz","year":"2011","journal-title":"Nat Biotechnol"},{"key":"2026020607364484500_bib4","doi-asserted-by":"publisher","first-page":"23","DOI":"10.1093\/bib\/bbw096","article-title":"The present and future of de novo whole-genome assembly","volume":"19","author":"Sohn","year":"2018","journal-title":"Brief Bioinform"},{"key":"2026020607364484500_bib5","doi-asserted-by":"publisher","first-page":"758","DOI":"10.1038\/s41587-023-01863-z","article-title":"De novo detection of somatic mutations in high-throughput single-cell profiling data sets","volume":"42","author":"Muyas","year":"2024","journal-title":"Nat Biotechnol"},{"key":"2026020607364484500_bib6","doi-asserted-by":"publisher","first-page":"evae102","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 Evolut"},{"key":"2026020607364484500_bib7","doi-asserted-by":"publisher","first-page":"40","DOI":"10.1016\/j.ins.2023.01.149","article-title":"A deep multiple kernel learning-based higher-order fuzzy inference system for identifying DNA N4-methylcytosine sites","volume":"630","author":"Wang","year":"2023","journal-title":"Inform Sci"},{"key":"2026020607364484500_bib8","doi-asserted-by":"publisher","first-page":"546","DOI":"10.3390\/biom12040546","article-title":"Developments in algorithms for sequence alignment: a review","volume":"12","author":"Chao","year":"2022","journal-title":"Biomolecules"},{"key":"2026020607364484500_bib9","doi-asserted-by":"publisher","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":"2026020607364484500_bib10","doi-asserted-by":"publisher","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"},{"key":"2026020607364484500_bib11","doi-asserted-by":"publisher","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"},{"key":"2026020607364484500_bib12","doi-asserted-by":"publisher","first-page":"btae718","DOI":"10.1093\/bioinformatics\/btae718","article-title":"HAlign 4: a new strategy for rapidly aligning millions of sequences","volume":"40","author":"Zhou","year":"2024","journal-title":"Bioinformatics"},{"key":"2026020607364484500_bib13","doi-asserted-by":"publisher","first-page":"237","DOI":"10.1016\/0378-1119(88)90330-7","article-title":"CLUSTAL: a package for performing multiple sequence alignment on a microcomputer","volume":"73","author":"Higgins","year":"1988","journal-title":"Gene"},{"key":"2026020607364484500_bib14","doi-asserted-by":"publisher","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":"2026020607364484500_bib15","doi-asserted-by":"publisher","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":"2026020607364484500_bib16","doi-asserted-by":"publisher","first-page":"33964","DOI":"10.1038\/srep33964","article-title":"FAMSA: fast and accurate multiple sequence alignment of huge protein families","volume":"6","author":"Deorowicz","year":"2016","journal-title":"Sci Rep"},{"key":"2026020607364484500_bib17","doi-asserted-by":"publisher","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"},{"key":"2026020607364484500_bib18","doi-asserted-by":"publisher","first-page":"265","DOI":"10.1186\/1471-2105-15-265","article-title":"ReformAlign: improved multiple sequence alignments using a profile-based meta-alignment approach","volume":"15","author":"Lyras","year":"2014","journal-title":"BMC Bioinf"},{"key":"2026020607364484500_bib19","doi-asserted-by":"publisher","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":"2026020607364484500_bib20","doi-asserted-by":"publisher","first-page":"lqae170","DOI":"10.1093\/nargab\/lqae170","article-title":"ReAlign-N: an integrated realignment approach for multiple nucleic acid sequence alignment, combining global and local realignments","volume":"6","author":"Zhai","year":"2024","journal-title":"NAR Genomics Bioinformatics"},{"key":"2026020607364484500_bib21","doi-asserted-by":"publisher","first-page":"bbad320","DOI":"10.1093\/bib\/bbad320","article-title":"Sequence alignment\/map format: a comprehensive review of approaches and applications","volume":"24","author":"Liu","year":"2023","journal-title":"Briefings Bioinf"},{"key":"2026020607364484500_bib22","doi-asserted-by":"publisher","first-page":"e1011214","DOI":"10.1371\/journal.pcbi.1011214","article-title":"BioSeq-Diabolo: biological sequence similarity analysis using Diabolo","volume":"19","author":"Li","year":"2023","journal-title":"PLoS Comput Biol"},{"key":"2026020607364484500_bib23","doi-asserted-by":"publisher","first-page":"e129","DOI":"10.1093\/nar\/gkab829","article-title":"BioSeq-BLM: a platform for analyzing DNA, RNA, and protein sequences based on biological language models","volume":"49","author":"Li","year":"2021","journal-title":"Nucleic Acids Res"},{"key":"2026020607364484500_bib24","doi-asserted-by":"publisher","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":"2026020607364484500_bib25","doi-asserted-by":"publisher","first-page":"3662","DOI":"10.1093\/bioinformatics\/btaa175","article-title":"FAME: fast and memory efficient multiple sequences alignment tool through compatible chain of roots","volume":"36","author":"Naznooshsadat","year":"2020","journal-title":"Bioinformatics"},{"key":"2026020607364484500_bib26","doi-asserted-by":"publisher","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"},{"key":"2026020607364484500_bib27","doi-asserted-by":"crossref","unstructured":"Zhang P, Liu H, Wei Y, et al. \u00a0FMAlign2: a novel fast multiple nucleotide sequence alignment method for ultralong datasets. Bioinformatics. 2024;40:btae014. 10.1093\/bioinformatics\/btae014.","DOI":"10.1093\/bioinformatics\/btae014"},{"key":"2026020607364484500_bib28","doi-asserted-by":"publisher","first-page":"803","DOI":"10.1089\/106652703322756096","article-title":"An Eulerian path approach to global multiple alignment for DNA sequences","volume":"10","author":"Zhang","year":"2003","journal-title":"J Comput Biol"},{"key":"2026020607364484500_bib29","doi-asserted-by":"publisher","first-page":"1285","DOI":"10.1073\/pnas.0409240102","article-title":"An eulerian path approach to local multiple alignment for DNA sequences","volume":"102","author":"Zhang","year":"2005","journal-title":"Proc Natl Acad Sci USA"},{"key":"2026020607364484500_bib30","first-page":"758","article-title":"A combinatorial problem","volume-title":"Proc K Ned Akad Wet","author":"De\u00a0Bruijn","year":"1946"},{"key":"2026020607364484500_bib31","doi-asserted-by":"publisher","first-page":"452","DOI":"10.1093\/bioinformatics\/18.3.452","article-title":"Multiple sequence alignment using partial order graphs","volume":"18","author":"Lee","year":"2002","journal-title":"Bioinformatics"},{"key":"2026020607364484500_bib32","doi-asserted-by":"publisher","first-page":"2209","DOI":"10.1093\/bioinformatics\/btaa963","article-title":"abPOA: an SIMD-based C library for fast partial order alignment using adaptive band","volume":"37","author":"Gao","year":"2021","journal-title":"Bioinformatics"},{"key":"2026020607364484500_bib33","doi-asserted-by":"publisher","first-page":"3224","DOI":"10.1093\/bioinformatics\/btw371","article-title":"deBGA: read alignment with de Bruijn graph-based seed and extension","volume":"32","author":"Liu","year":"2016","journal-title":"Bioinformatics"},{"key":"2026020607364484500_bib34","doi-asserted-by":"publisher","first-page":"3476","DOI":"10.1093\/bioinformatics\/btu756","article-title":"SplitMEM: a graphical algorithm for pan-genome analysis with suffix skips","volume":"30","author":"Marcus","year":"2014","journal-title":"Bioinformatics"},{"key":"2026020607364484500_bib35","doi-asserted-by":"publisher","first-page":"497","DOI":"10.1093\/bioinformatics\/btv603","article-title":"Graphical pan-genome analysis with compressed suffix trees and the Burrows-Wheeler transform","volume":"32","author":"Baier","year":"2016","journal-title":"Bioinformatics"},{"key":"2026020607364484500_bib36","doi-asserted-by":"publisher","first-page":"e82138","DOI":"10.1371\/journal.pone.0082138","article-title":"SSW library: an SIMD Smith-Waterman C\/C++ library for use in genomic applications","volume":"8","author":"Zhao","year":"2013","journal-title":"PLoS One"},{"key":"2026020607364484500_bib37","doi-asserted-by":"publisher","first-page":"110","DOI":"10.1016\/0022-0000(79)90042-4","article-title":"A class of algorithms which require nonlinear time to maintain disjoint sets","volume":"18","author":"Tarjan","year":"1979","journal-title":"J Comput System Sci"},{"key":"2026020607364484500_bib38","doi-asserted-by":"crossref","unstructured":"Khan Z, Bloom JS, Kruglyak L, et al. \u00a0A practical algorithm for finding maximal exact matches in large sequence datasets using sparse suffix arrays. Bioinformatics. 2009;25:1609\u201316. 10.1093\/bioinformatics\/btp275.","DOI":"10.1093\/bioinformatics\/btp275"},{"key":"2026020607364484500_bib39","doi-asserted-by":"publisher","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":"2026020607364484500_bib40","doi-asserted-by":"publisher","first-page":"bbaf061","DOI":"10.1093\/bib\/bbaf061","article-title":"FORAlign: accelerating gap-affine DNA pairwise sequence alignment using FOR-blocks based on Four Russians approach with linear space complexity","volume":"26","author":"Wei","year":"2025","journal-title":"Brief Bioinform"},{"key":"2026020607364484500_bib41","doi-asserted-by":"publisher","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":"2026020607364484500_bib42","first-page":"84","article-title":"CUK-Band: a CUDA-based multiple genomic sequence alignment on GPU","author":"Kong","year":"2024"},{"key":"2026020607364484500_bib43","doi-asserted-by":"publisher","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":"Innovation"},{"key":"2026020607364484500_bib44","doi-asserted-by":"publisher","first-page":"bbad190","DOI":"10.1093\/bib\/bbad190","article-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","volume":"24","author":"Chen","year":"2023","journal-title":"Brief Bioinform"},{"key":"2026020607364484500_bib45","author":"Wei","year":"2025."},{"key":"2026020607364484500_bib46","doi-asserted-by":"crossref","unstructured":"Wei Y, Huang Z, Zhang P, et al. \u00a0deMEM: a novel divide-and-conquer framework based on de Bruijn graph for scalable multiple sequence alignment. Zenodo. 2025. 10.5281\/zenodo.14989520. Accessed 15 December 2025.","DOI":"10.1093\/gigascience\/giaf163"}],"container-title":["GigaScience"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/academic.oup.com\/gigascience\/advance-article-pdf\/doi\/10.1093\/gigascience\/giaf163\/66263799\/giaf163.pdf","content-type":"application\/pdf","content-version":"am","intended-application":"syndication"},{"URL":"https:\/\/academic.oup.com\/gigascience\/article-pdf\/doi\/10.1093\/gigascience\/giaf163\/66263799\/giaf163.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"syndication"},{"URL":"https:\/\/academic.oup.com\/gigascience\/article-pdf\/doi\/10.1093\/gigascience\/giaf163\/66263799\/giaf163.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,2,6]],"date-time":"2026-02-06T12:36:53Z","timestamp":1770381413000},"score":1,"resource":{"primary":{"URL":"https:\/\/academic.oup.com\/gigascience\/article\/doi\/10.1093\/gigascience\/giaf163\/8414073"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2026]]},"references-count":46,"URL":"https:\/\/doi.org\/10.1093\/gigascience\/giaf163","relation":{},"ISSN":["2047-217X"],"issn-type":[{"value":"2047-217X","type":"electronic"}],"subject":[],"published-other":{"date-parts":[[2026]]},"published":{"date-parts":[[2026]]},"article-number":"giaf163"}}