{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,10,14]],"date-time":"2026-10-14T22:29:28Z","timestamp":1792016968864,"version":"4.4.0"},"reference-count":42,"publisher":"Oxford University Press (OUP)","issue":"1","license":[{"start":{"date-parts":[[2025,2,23]],"date-time":"2025-02-23T00:00:00Z","timestamp":1740268800000},"content-version":"vor","delay-in-days":93,"URL":"https:\/\/creativecommons.org\/licenses\/by-nc\/4.0\/"}],"funder":[{"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"}]},{"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\/501100001809","name":"National Natural Science Foundation of China","doi-asserted-by":"publisher","award":["62072353"],"award-info":[{"award-number":["62072353"]}],"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":["62272065"],"award-info":[{"award-number":["62272065"]}],"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,22]]},"abstract":"<jats:title>Abstract<\/jats:title>\n               <jats:p>Pairwise sequence alignment (PSA) serves as the cornerstone in computational bioinformatics, facilitating multiple sequence alignment and phylogenetic analysis. This paper introduces the FORAlign algorithm, leveraging the Four Russians algorithm with identical upper-bound time and space complexity as the Hirschberg divide-and-conquer PSA algorithm, aimed at accelerating Hirschberg PSA algorithm in parallel. Particularly notable is its capability to achieve up to 16.79 times speedup when aligning sequences with low sequence similarity, compared to the conventional Needleman-Wunsch PSA method using non-heuristic methods. Empirical evaluations underscore FORAlign\u2019s superiority over existing wavefront alignment (WFA) series software, especially in scenarios characterized by low sequence similarity during PSA tasks. Our method is capable of directly aligning monkeypox sequences with other sequences using non-heuristic methods. The algorithm was implemented within the FORAlign library, providing functionality for PSA and foundational support for multiple sequence alignment and phylogenetic trees. The FORAlign library is freely available at https:\/\/github.com\/malabz\/FORAlign.<\/jats:p>","DOI":"10.1093\/bib\/bbaf061","type":"journal-article","created":{"date-parts":[[2025,2,19]],"date-time":"2025-02-19T12:19:09Z","timestamp":1739967549000},"source":"Crossref","is-referenced-by-count":5,"title":["FORAlign: accelerating gap-affine DNA pairwise sequence alignment using FOR-blocks based on Four Russians approach with linear space complexity"],"prefix":"10.1093","volume":"26","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, No. 266, Xinglong Section of Xifeng Road, Chang'an Zone, Xidian University , Xi\u2019an 710126 ,","place":["China"]},{"name":"Institute of Digital Health, Yangtze Delta Region Institute (Quzhou), University of Electronic Science and Technology of China , No. 1, Chengdian Road, Kecheng Zone, Quzhou 324003 ,","place":["China"]}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Tong","family":"Zhou","sequence":"additional","affiliation":[{"name":"Institute of Digital Health, Yangtze Delta Region Institute (Quzhou), 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":[{"vocabulary":"crossref","role":"author"}]},{"given":"Yixiao","family":"Zhai","sequence":"additional","affiliation":[{"name":"Institute of Digital Health, Yangtze Delta Region Institute (Quzhou), 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":[{"vocabulary":"crossref","role":"author"}]},{"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, No. 266, Xinglong Section of Xifeng Road, Chang'an Zone, Xidian University , Xi\u2019an 710126 ,","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 Digital Health, Yangtze Delta Region Institute (Quzhou), 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":[{"vocabulary":"crossref","role":"author"}]}],"member":"286","published-online":{"date-parts":[[2025,2,23]]},"reference":[{"key":"2025022303024855800_ref1","doi-asserted-by":"publisher","first-page":"2","DOI":"10.47852\/bonviewMEDIN42022204","article-title":"Artificial intelligence with great potential in medical informatics: a brief review","volume":"1","author":"Lin","year":"2024","journal-title":"Medinformatics"},{"key":"2025022303024855800_ref2","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":"Brief Bioinform"},{"key":"2025022303024855800_ref3","doi-asserted-by":"publisher","first-page":"107660","DOI":"10.1016\/j.compbiomed.2023.107660","article-title":"ComDock: a novel approach for protein-protein docking with an efficient fusing strategy","volume":"167","author":"Meng","year":"2023","journal-title":"Comput Biol Med"},{"key":"2025022303024855800_ref4","doi-asserted-by":"publisher","first-page":"3017","DOI":"10.1093\/nar\/gkad055","article-title":"DeepBIO: an automated and interpretable deep-learning platform for high-throughput biological sequence prediction, functional annotation and visualization analysis","volume":"51","author":"Wang","year":"2023","journal-title":"Nucleic Acids Res"},{"key":"2025022303024855800_ref5","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":"2025022303024855800_ref6","doi-asserted-by":"publisher","first-page":"bbac069","DOI":"10.1093\/bib\/bbac069","article-title":"A survey on the algorithm and development of multiple sequence alignment","volume":"23","author":"Zhang","year":"2022","journal-title":"Brief Bioinform"},{"key":"2025022303024855800_ref7","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":"2025022303024855800_ref8","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":"2025022303024855800_ref9","doi-asserted-by":"publisher","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":"2025022303024855800_ref10","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":"2025022303024855800_ref11","doi-asserted-by":"publisher","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":"2025022303024855800_ref12","doi-asserted-by":"publisher","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":"2025022303024855800_ref13","doi-asserted-by":"publisher","first-page":"359","DOI":"10.1007\/BF02458577","article-title":"Optimal sequence alignment allowing for long gaps","volume":"52","author":"Gotoh","year":"1990","journal-title":"Bull Math Biol"},{"key":"2025022303024855800_ref14","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":"2025022303024855800_ref15","first-page":"1","volume-title":"NAFIPS 2009\u20132009 Annual Meeting of the North American Fuzzy Information Processing Society","author":"Mrozek","year":"2009"},{"key":"2025022303024855800_ref16","first-page":"1","article-title":"An optimal alignment of proteins energy characteristics with crisp and fuzzy similarity awards","volume":"2007","author":"Mrozek","year":"2007","journal-title":"IEEE International Fuzzy Systems Conference"},{"key":"2025022303024855800_ref17","doi-asserted-by":"publisher","DOI":"10.1016\/j.ins.2024.120105","article-title":"Towards retraining-free RNA modification prediction with incremental learning","volume":"660","author":"Qiao","year":"2024","journal-title":"Inform Sci"},{"key":"2025022303024855800_ref18","doi-asserted-by":"publisher","DOI":"10.1093\/bioinformatics\/btad487","article-title":"Block aligner: an adaptive SIMD-accelerated aligner for sequences and position-specific scoring matrices","volume":"39","author":"Liu","year":"2023","journal-title":"Bioinformatics"},{"key":"2025022303024855800_ref19","doi-asserted-by":"publisher","DOI":"10.1093\/bioinformatics\/btae032","article-title":"Exact global alignment using A* with chaining seed heuristic and match pruning","volume":"40","author":"Groot","year":"2024","journal-title":"Bioinformatics"},{"key":"2025022303024855800_ref20","volume-title":"24th International Workshop on Algorithms in Bioinformatics (WABI 2024)","author":"Groot","year":"2024"},{"key":"2025022303024855800_ref21","doi-asserted-by":"publisher","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":"2025022303024855800_ref22","doi-asserted-by":"publisher","first-page":"11","DOI":"10.1093\/bioinformatics\/4.1.11","article-title":"Optimal alignments in linear space","volume":"4","author":"Myers","year":"1988","journal-title":"Comput Appl Biosci"},{"key":"2025022303024855800_ref23","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":"Communications of the ACM"},{"key":"2025022303024855800_ref24","doi-asserted-by":"publisher","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":"2025022303024855800_ref25","first-page":"487","volume-title":"Doklady Akademii Nauk","author":"VLV","year":"1970"},{"key":"2025022303024855800_ref26","doi-asserted-by":"publisher","first-page":"173","DOI":"10.1016\/j.tcs.2016.04.028","article-title":"A space-efficient alphabet-independent four-Russians' lookup table and a multithreaded four-Russians' edit distance algorithm","volume":"656","author":"Kim","year":"2016","journal-title":"Theoretical Computer Science"},{"key":"2025022303024855800_ref27","doi-asserted-by":"publisher","first-page":"893","DOI":"10.1007\/978-3-540-69384-0_94","author":"Kundeti","year":"2008"},{"key":"2025022303024855800_ref28","doi-asserted-by":"crossref","first-page":"187","DOI":"10.1109\/IACS.2018.8355464","volume-title":"2018 9th International Conference on Information and Communication Systems (ICICS)","author":"Al-Hussien","year":"2018"},{"key":"2025022303024855800_ref29","doi-asserted-by":"publisher","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":"2025022303024855800_ref30","doi-asserted-by":"publisher","DOI":"10.1093\/gpbjnl\/qzae025","article-title":"BSAlign: a library for nucleotide sequence alignment","volume":"22","author":"Shao","year":"2024","journal-title":"Genomics Proteomics Bioinformatics"},{"key":"2025022303024855800_ref31","first-page":"499","volume-title":"Proceedings of the World Congress on Engineering","author":"Yang","year":"2010"},{"key":"2025022303024855800_ref32","doi-asserted-by":"publisher","first-page":"251","DOI":"10.1007\/BF01840446","article-title":"An O(ND) difference algorithm and its variations","volume":"1","author":"Myers","year":"1986","journal-title":"Algorithmica"},{"key":"2025022303024855800_ref33","doi-asserted-by":"publisher","first-page":"128","DOI":"10.1186\/1471-2105-5-128","article-title":"DIALIGN P: fast pair-wise and multiple sequence alignment using parallel processors","volume":"5","author":"Schmollinger","year":"2004","journal-title":"BMC Bioinformatics"},{"key":"2025022303024855800_ref34","doi-asserted-by":"crossref","first-page":"2049","DOI":"10.1109\/FSKD.2017.8393085","volume-title":"2017 13th International Conference on Natural Computation, Fuzzy Systems and Knowledge Discovery (ICNC-FSKD)","author":"Zhu","year":"2017"},{"key":"2025022303024855800_ref35","doi-asserted-by":"crossref","first-page":"36","DOI":"10.1145\/337449.337465","volume-title":"Proceedings of the ACM 2000 Conference on Java","author":"Lea","year":"2000"},{"key":"2025022303024855800_ref36","volume-title":"C++ Concurrency in Action","author":"Williams","year":"2019"},{"key":"2025022303024855800_ref37","doi-asserted-by":"publisher","first-page":"2","DOI":"10.2807\/1560-7917.ES.2017.22.13.30494","article-title":"GISAID: global initiative on sharing all influenza data - from vision to reality","volume":"22","author":"Shu","year":"2017","journal-title":"Eurosurveillance"},{"key":"2025022303024855800_ref38","doi-asserted-by":"publisher","first-page":"252","DOI":"10.1038\/s41586-021-04233-4","article-title":"Towards the biogeography of prokaryotic genes","volume":"601","author":"Coelho","year":"2022","journal-title":"Nature"},{"key":"2025022303024855800_ref39","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, the","volume":"3","author":"Ma","year":"2022","journal-title":"Innovation"},{"key":"2025022303024855800_ref40","volume-title":"Parallel Programming in OpenMP","author":"Chandra","year":"2001"},{"key":"2025022303024855800_ref41","doi-asserted-by":"publisher","first-page":"357","DOI":"10.1038\/nmeth.1923","article-title":"Fast gapped-read alignment with bowtie 2","volume":"9","author":"Langmead","year":"2012","journal-title":"Nat Methods"},{"key":"2025022303024855800_ref42","doi-asserted-by":"publisher","first-page":"3150","DOI":"10.1093\/bioinformatics\/bts565","article-title":"CD-HIT: accelerated for clustering the next-generation sequencing data","volume":"28","author":"Fu","year":"2012","journal-title":"Bioinformatics"}],"container-title":["Briefings in Bioinformatics"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/academic.oup.com\/bib\/article-pdf\/26\/1\/bbaf061\/62054622\/bbaf061.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"syndication"},{"URL":"https:\/\/academic.oup.com\/bib\/article-pdf\/26\/1\/bbaf061\/62054622\/bbaf061.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,2,23]],"date-time":"2025-02-23T03:03:17Z","timestamp":1740279797000},"score":1,"resource":{"primary":{"URL":"https:\/\/academic.oup.com\/bib\/article\/doi\/10.1093\/bib\/bbaf061\/8030539"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2024,11,22]]},"references-count":42,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2024,11,22]]}},"URL":"https:\/\/doi.org\/10.1093\/bib\/bbaf061","relation":{},"ISSN":["1467-5463","1477-4054"],"issn-type":[{"value":"1467-5463","type":"print"},{"value":"1477-4054","type":"electronic"}],"subject":[],"published-other":{"date-parts":[[2025,1]]},"published":{"date-parts":[[2024,11,22]]},"article-number":"bbaf061"}}