{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,9,23]],"date-time":"2026-09-23T17:13:39Z","timestamp":1790183619012,"version":"4.1.0"},"reference-count":27,"publisher":"Oxford University Press (OUP)","issue":"1","license":[{"start":{"date-parts":[[2021,12,10]],"date-time":"2021-12-10T00:00:00Z","timestamp":1639094400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/academic.oup.com\/journals\/pages\/open_access\/funder_policies\/chorus\/standard_publication_model"}],"funder":[{"DOI":"10.13039\/501100001809","name":"National Nature Science Foundation of China","doi-asserted-by":"crossref","award":["61672480"],"award-info":[{"award-number":["61672480"]}],"id":[{"id":"10.13039\/501100001809","id-type":"DOI","asserted-by":"crossref"}]},{"name":"Fund for Foreign Scholars in University Research and Teaching Programs","award":["B07033"],"award-info":[{"award-number":["B07033"]}]},{"DOI":"10.13039\/501100001809","name":"National Natural Science Foundation of China","doi-asserted-by":"publisher","award":["61771331"],"award-info":[{"award-number":["61771331"]}],"id":[{"id":"10.13039\/501100001809","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2022,1,17]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>Multiple sequence alignment (MSA) is fundamental to many biological applications. But most classical MSA algorithms are difficult to handle large-scale multiple sequences, especially long sequences. Therefore, some recent aligners adopt an efficient divide-and-conquer strategy to divide long sequences into several short sub-sequences. Selecting the common segments (i.e. anchors) for division of sequences is very critical as it directly affects the accuracy and time cost. So, we proposed a novel algorithm, FMAlign, to improve the performance of multiple nucleotide sequence alignment. We use FM-index to extract long common segments at a low cost rather than using a space-consuming hash table. Moreover, after finding the longer optimal common segments, the sequences are divided by the longer common segments. FMAlign has been tested on virus and bacteria genome and human mitochondrial genome datasets, and compared with existing MSA methods such as MAFFT, HAlign and FAME. The experiments show that our method outperforms the existing methods in terms of running time, and has a high accuracy on long sequence sets. All the results demonstrate that our method is applicable to the large-scale nucleotide sequences in terms of sequence length and sequence number. The source code and related data are accessible in https:\/\/github.com\/iliuh\/FMAlign.<\/jats:p>","DOI":"10.1093\/bib\/bbab519","type":"journal-article","created":{"date-parts":[[2021,11,15]],"date-time":"2021-11-15T13:43:45Z","timestamp":1636983825000},"source":"Crossref","is-referenced-by-count":15,"title":["A novel fast multiple nucleotide sequence alignment method based on FM-index"],"prefix":"10.1093","volume":"23","author":[{"given":"Huan","family":"Liu","sequence":"first","affiliation":[{"name":"School of Computer Science, University of Science and Technology of China and Key Laboratory on High Performance Computing of Anhui, China"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Quan","family":"Zou","sequence":"additional","affiliation":[{"name":"Institute of basic and Frontier Sciences, University of Electronic Science and Technology of China and Yangtze Delta Region Institute (Quzhou), University of Electronic Science and Technology of China, Chengdu, Sichuan, China"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Yun","family":"Xu","sequence":"additional","affiliation":[{"name":"School of Computer Science, University of Science and Technology of China and Key Laboratory on High Performance Computing of Anhui, China"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"286","published-online":{"date-parts":[[2021,12,10]]},"reference":[{"issue":"4","key":"2022012000315975600_ref1","doi-asserted-by":"crossref","first-page":"472","DOI":"10.1093\/bioinformatics\/btt709","article-title":"Combining evolutionary information extracted from frequency profiles with sequence-based kernels for protein remote homology detection","volume":"30","author":"Liu","year":"2014","journal-title":"Bioinformatics"},{"issue":"10224","key":"2022012000315975600_ref2","doi-asserted-by":"crossref","first-page":"565","DOI":"10.1016\/S0140-6736(20)30251-8","article-title":"Genomic characterisation and epidemiology of 2019 novel coronavirus: implications for virus origins and receptor binding","volume":"395","author":"Lu","year":"2014","journal-title":"Lancet"},{"issue":"6","key":"2022012000315975600_ref3","doi-asserted-by":"crossref","first-page":"1009","DOI":"10.1093\/bib\/bbv099","article-title":"Multiple sequence alignment modeling: methods and applications","volume":"17","author":"Chatzou","year":"2016","journal-title":"Brief Bioinform"},{"issue":"6","key":"2022012000315975600_ref4","doi-asserted-by":"crossref","DOI":"10.1371\/journal.pone.0039475","article-title":"Secom: A novel hash seed and community detection based-approach for genome-scale protein domain identification","volume":"7","author":"Fan","year":"2012","journal-title":"PLOS ONE"},{"key":"2022012000315975600_ref5","first-page":"4325","article-title":"Earth biogenome project: Sequencing life for the future of life","volume-title":"Proceedings of the National Academy of Sciences of the United States of America","author":"Lewin","year":"2018"},{"issue":"4","key":"2022012000315975600_ref6","doi-asserted-by":"crossref","first-page":"337\u00e2","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"},{"issue":"15","key":"2022012000315975600_ref7","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":"5\u20136","key":"2022012000315975600_ref8","doi-asserted-by":"crossref","first-page":"419","DOI":"10.1016\/j.ygeno.2017.06.007","article-title":"A review on multiple sequence alignment from the perspective of genetic algorithm","volume":"109","author":"Chowdhury","year":"2017","journal-title":"Genomics"},{"issue":"1","key":"2022012000315975600_ref9","doi-asserted-by":"crossref","first-page":"135","DOI":"10.1002\/pro.3290","article-title":"Clustal omega for making accurate alignments of many protein sequences","volume":"27","author":"Sievers","year":"2018","journal-title":"Protein Sci"},{"key":"2022012000315975600_ref10","doi-asserted-by":"crossref","first-page":"298","DOI":"10.1186\/1471-2105-6-298","article-title":"Kalign - an accurate and fast multiple sequence alignment algorithm","volume":"6","author":"Lassmann","year":"2005","journal-title":"BMC Bioinformatics"},{"issue":"14","key":"2022012000315975600_ref11","doi-asserted-by":"crossref","first-page":"2490","DOI":"10.1093\/bioinformatics\/bty121","article-title":"Parallelization of mafft for large-scale multiple sequence alignments","volume":"34","author":"Nakamura","year":"2018","journal-title":"Bioinformatics"},{"issue":"4","key":"2022012000315975600_ref12","doi-asserted-by":"crossref","first-page":"1160","DOI":"10.1093\/bib\/bbx108","article-title":"Mafft online service: multiple sequence alignment, interactive sequence choice and visualization","volume":"20","author":"Katoh","year":"2019","journal-title":"Brief Bioinform"},{"key":"2022012000315975600_ref13","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 for Molecular Biology"},{"key":"2022012000315975600_ref14","doi-asserted-by":"crossref","first-page":"315","DOI":"10.1186\/s12859-017-1725-6","article-title":"Cmsa: a heterogeneous cpu\/gpu computing system for multiple similar rna\/dna sequence alignment","volume":"18","author":"Chen","year":"2017","journal-title":"BMC Bioinformatics"},{"issue":"12","key":"2022012000315975600_ref15","doi-asserted-by":"crossref","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"},{"issue":"18","key":"2022012000315975600_ref16","doi-asserted-by":"crossref","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"},{"issue":"5","key":"2022012000315975600_ref17","doi-asserted-by":"crossref","first-page":"1333","DOI":"10.1093\/bioinformatics\/btz742","article-title":"Novel algorithms for efficient subsequence searching and mapping in nanopore raw signals towards targeted sequencing","volume":"36","author":"Han","year":"2020","journal-title":"Bioinformatics"},{"issue":"17","key":"2022012000315975600_ref18","doi-asserted-by":"crossref","first-page":"722","DOI":"10.1093\/bioinformatics\/bty555","article-title":"An accurate and rapid continuous wavelet dynamic time warping algorithm for end-to-end mapping in ultra-long nanopore sequencing","volume":"34","author":"Han","year":"2018","journal-title":"Bioinformatics"},{"key":"2022012000315975600_ref19","doi-asserted-by":"crossref","first-page":"177","DOI":"10.1007\/978-3-319-05269-4_15","article-title":"Pasta: ultra-large multiple sequence alignment","volume-title":"International Conference on Research in Computational Molecular Biology","author":"Mirarab","year":"2014"},{"issue":"7","key":"2022012000315975600_ref20","doi-asserted-by":"crossref","first-page":"407","DOI":"10.1016\/j.jgg.2018.07.004","article-title":"Vcsra: A fast and accurate multiple sequence alignment algorithm with a high degree of parallelism","volume":"45","author":"Dong","year":"2018","journal-title":"J Genet Genomics"},{"key":"2022012000315975600_ref21","first-page":"31\u00e2","volume-title":"Practical aspects of compressed suffix arrays and fm-index in searching dna sequences","author":"Hon","year":"2004"},{"issue":"4","key":"2022012000315975600_ref22","doi-asserted-by":"crossref","first-page":"552","DOI":"10.1145\/1082036.1082039","article-title":"Indexing compressed text","volume":"52","author":"Ferragina","year":"2005","journal-title":"Journal of the ACM"},{"key":"2022012000315975600_ref23","article-title":"A block sorting lossless data compression algorithm","author":"Burrows","year":"1995","journal-title":"Technical report, Digital SRC Research Report"},{"key":"2022012000315975600_ref24","doi-asserted-by":"crossref","first-page":"17","DOI":"10.1016\/j.jda.2016.03.003","article-title":"Lightweight lcp construction for very large collections of strings","volume":"37","author":"Cox","year":"2016","journal-title":"Journal of Discrete Algorithms"},{"issue":"3","key":"2022012000315975600_ref25","doi-asserted-by":"crossref","first-page":"298","DOI":"10.1016\/j.tcs.2007.07.014","article-title":"An extension of the burrows-wheeler transform","volume":"387","author":"Mantaci","year":"2007","journal-title":"Theoretical Computer Science"},{"key":"2022012000315975600_ref26","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"},{"issue":"13","key":"2022012000315975600_ref27","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"}],"container-title":["Briefings in Bioinformatics"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/academic.oup.com\/bib\/article-pdf\/23\/1\/bbab519\/42230854\/bbab519.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"syndication"},{"URL":"https:\/\/academic.oup.com\/bib\/article-pdf\/23\/1\/bbab519\/42230854\/bbab519.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,11,12]],"date-time":"2023-11-12T17:00:56Z","timestamp":1699808456000},"score":1,"resource":{"primary":{"URL":"https:\/\/academic.oup.com\/bib\/article\/doi\/10.1093\/bib\/bbab519\/6458932"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2021,12,10]]},"references-count":27,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2022,1,17]]}},"URL":"https:\/\/doi.org\/10.1093\/bib\/bbab519","relation":{},"ISSN":["1467-5463","1477-4054"],"issn-type":[{"value":"1467-5463","type":"print"},{"value":"1477-4054","type":"electronic"}],"subject":[],"published-other":{"date-parts":[[2022,1]]},"published":{"date-parts":[[2021,12,10]]},"article-number":"bbab519"}}