{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,1,31]],"date-time":"2026-01-31T07:47:06Z","timestamp":1769845626780,"version":"3.49.0"},"reference-count":37,"publisher":"Oxford University Press (OUP)","issue":"3","license":[{"start":{"date-parts":[[2025,3,18]],"date-time":"2025-03-18T00:00:00Z","timestamp":1742256000000},"content-version":"vor","delay-in-days":17,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"funder":[{"DOI":"10.13039\/501100001659","name":"Deutsche Forschungsgemeinschaft","doi-asserted-by":"publisher","id":[{"id":"10.13039\/501100001659","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2025,3,4]]},"abstract":"<jats:title>Abstract<\/jats:title>\n               <jats:sec>\n                  <jats:title>Motivation<\/jats:title>\n                  <jats:p>Since novel long read sequencing technologies allow for de novo assembly of many individuals of a species, high-quality assemblies are becoming widely available. For example, the recently published draft human pangenome reference was based on assemblies composed of contigs. There is an urgent need for a software-tool that is able to generate a multiple alignment of genomes of the same species because current multiple sequence alignment programs cannot deal with such a volume of data.<\/jats:p>\n               <\/jats:sec>\n               <jats:sec>\n                  <jats:title>Results<\/jats:title>\n                  <jats:p>We show that the combination of a well-known anchor-based method with the technique of prefix-free parsing yields an approach that is able to generate multiple alignments on a pangenomic scale, provided that large-scale structural variants are rare. Furthermore, experiments with real world data show that our software tool PANgenomic Anchor-based Multiple Alignment significantly outperforms current state-of-the art programs.<\/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:\/\/gitlab.com\/qwerzuiop\/panama, archived at swh:1:dir:e90c9f664995acca9063245cabdd97549cf39694.<\/jats:p>\n               <\/jats:sec>","DOI":"10.1093\/bioinformatics\/btaf104","type":"journal-article","created":{"date-parts":[[2025,3,18]],"date-time":"2025-03-18T02:14:06Z","timestamp":1742264046000},"source":"Crossref","is-referenced-by-count":3,"title":["Generating multiple alignments on a pangenomic scale"],"prefix":"10.1093","volume":"41","author":[{"ORCID":"https:\/\/orcid.org\/0000-0003-3291-7342","authenticated-orcid":false,"given":"Jannik","family":"Olbrich","sequence":"first","affiliation":[{"name":"Institute of Theoretical Computer Science, Ulm University , Ulm, 89069,","place":["Germany"]}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-9273-5439","authenticated-orcid":false,"given":"Thomas","family":"B\u00fcchler","sequence":"additional","affiliation":[{"name":"Institute of Theoretical Computer Science, Ulm University , Ulm, 89069,","place":["Germany"]}]},{"given":"Enno","family":"Ohlebusch","sequence":"additional","affiliation":[{"name":"Institute of Theoretical Computer Science, Ulm University , Ulm, 89069,","place":["Germany"]}]}],"member":"286","published-online":{"date-parts":[[2025,3,17]]},"reference":[{"key":"2025032208012553200_btaf104-B1","doi-asserted-by":"crossref","first-page":"53","DOI":"10.1016\/S1570-8667(03)00065-0","article-title":"Replacing suffix trees with enhanced suffix arrays","volume":"2","author":"Abouelhoda","year":"2004","journal-title":"J Discret Algorithms"},{"key":"2025032208012553200_btaf104-B2","doi-asserted-by":"crossref","first-page":"246","DOI":"10.1038\/s41586-020-2871-y","article-title":"Progressive cactus is a multiple-genome aligner for the thousand-genome era","volume":"587","author":"Armstrong","year":"2020","journal-title":"Nature"},{"key":"2025032208012553200_btaf104-B3","doi-asserted-by":"crossref","first-page":"68","DOI":"10.1038\/nature15393","article-title":"A global reference for human genetic variation","volume":"526","author":"Auton","year":"2015","journal-title":"Nature"},{"key":"2025032208012553200_btaf104-B4","doi-asserted-by":"crossref","first-page":"81","DOI":"10.1007\/s11047-022-09882-6","article-title":"Computational graph pangenomics: a tutorial on data structures and their applications","volume":"21","author":"Baaijens","year":"2022","journal-title":"Nat Comput"},{"key":"2025032208012553200_btaf104-B5","doi-asserted-by":"crossref","DOI":"10.1186\/s13015-019-0148-5","article-title":"Prefix-free parsing for building big BWTs","volume":"14","author":"Boucher","year":"2019","journal-title":"Algorithms Mol Biol"},{"key":"2025032208012553200_btaf104-B6","first-page":"193","author":"Boucher","year":"2021"},{"key":"2025032208012553200_btaf104-B7","doi-asserted-by":"crossref","first-page":"btad320","DOI":"10.1093\/bioinformatics\/btad320","article-title":"Efficient short read mapping to a pangenome that is represented by a graph of ED strings","volume":"39","author":"B\u00fcchler","year":"2023","journal-title":"Bioinformatics"},{"key":"2025032208012553200_btaf104-B8","author":"Burrows","year":"1994"},{"key":"2025032208012553200_btaf104-B9","doi-asserted-by":"crossref","first-page":"105","DOI":"10.1093\/bib\/4.2.105","article-title":"An applications-focused review of comparative genomics tools: capabilities, limitations and future challenges","volume":"4","author":"Chain","year":"2003","journal-title":"Brief Bioinform"},{"key":"2025032208012553200_btaf104-B10","volume-title":"Introduction to Algorithms","author":"Cormen","year":"1990"},{"key":"2025032208012553200_btaf104-B11","doi-asserted-by":"crossref","first-page":"139","DOI":"10.1146\/annurev-genom-120219-080406","article-title":"Pangenome graphs","volume":"21","author":"Eizenga","year":"2020","journal-title":"Annu Rev Genomics Hum Genet"},{"key":"2025032208012553200_btaf104-B12","doi-asserted-by":"crossref","first-page":"875","DOI":"10.1038\/nbt.4227","article-title":"Variation graph toolkit improves read mapping by representing genetic variation in the reference","volume":"36","author":"Garrison","year":"2018","journal-title":"Nat Biotechnol"},{"key":"2025032208012553200_btaf104-B13","doi-asserted-by":"crossref","first-page":"2008","DOI":"10.1038\/s41592-024-02430-3","article-title":"Building pangenome graphs","volume":"21","author":"Garrison","year":"2024","journal-title":"Nat Methods"},{"key":"2025032208012553200_btaf104-B14","first-page":"326","author":"Gog","year":"2014"},{"key":"2025032208012553200_btaf104-B15","doi-asserted-by":"crossref","first-page":"663","DOI":"10.1038\/s41587-023-01793-w","article-title":"Pangenome graph construction from genome alignments with Minigraph-Cactus","volume":"42","author":"Hickey","year":"2024","journal-title":"Nat Biotechnol"},{"key":"2025032208012553200_btaf104-B16","doi-asserted-by":"crossref","first-page":"S312","DOI":"10.1093\/bioinformatics\/18.suppl_1.S312","article-title":"Efficient multiple genome alignment","volume":"18","author":"H\u00f6hl","year":"2002","journal-title":"Bioinformatics"},{"key":"2025032208012553200_btaf104-B17","doi-asserted-by":"crossref","first-page":"52","DOI":"10.1007\/3-540-56024-6_5","volume-title":"Combinatorial Pattern Matching","author":"Jacobson","year":"1992"},{"key":"2025032208012553200_btaf104-B18","doi-asserted-by":"crossref","first-page":"181","DOI":"10.1007\/3-540-48194-X_17","volume-title":"Combinatorial Pattern Matching","author":"Kasai","year":"2001"},{"key":"2025032208012553200_btaf104-B19","first-page":"17:1","author":"Koerkamp","year":"2024"},{"key":"2025032208012553200_btaf104-B20","first-page":"707","article-title":"Binary codes capable of correcting deletions, insertions, and reversals","volume":"10","author":"Levenshtein","year":"1966","journal-title":"Soviet Physics-Doklady"},{"key":"2025032208012553200_btaf104-B21","doi-asserted-by":"crossref","first-page":"4572","DOI":"10.1093\/bioinformatics\/btab705","article-title":"New strategies to improve minimap2 alignment accuracy","volume":"37","author":"Li","year":"2021","journal-title":"Bioinformatics"},{"key":"2025032208012553200_btaf104-B22","doi-asserted-by":"crossref","first-page":"265","DOI":"10.1186\/s13059-020-02168-z","article-title":"The design and construction of reference pangenome graphs with minigraph","volume":"21","author":"Li","year":"2020","journal-title":"Genome Biol"},{"key":"2025032208012553200_btaf104-B23","doi-asserted-by":"crossref","first-page":"312","DOI":"10.1038\/s41586-023-05896-x","article-title":"A draft human pangenome reference","volume":"617","author":"Liao","year":"2023","journal-title":"Nature"},{"key":"2025032208012553200_btaf104-B24","doi-asserted-by":"crossref","first-page":"136","DOI":"10.1038\/s41586-024-07278-3","article-title":"The variation and evolution of complete human centromeres","volume":"629","author":"Logsdon","year":"2024","journal-title":"Nature"},{"key":"2025032208012553200_btaf104-B25","doi-asserted-by":"crossref","first-page":"22","DOI":"10.1016\/j.tcs.2017.03.039","article-title":"Inducing enhanced suffix arrays for string collections","volume":"678","author":"Louza","year":"2017","journal-title":"Theor Comput Sci"},{"key":"2025032208012553200_btaf104-B26","doi-asserted-by":"crossref","first-page":"708","DOI":"10.1007\/s00248-010-9717-3","article-title":"Comparison of 61 sequenced Escherichia coli genomes","volume":"60","author":"Lukjancenko","year":"2010","journal-title":"Microb Ecol"},{"key":"2025032208012553200_btaf104-B27","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":"2025032208012553200_btaf104-B28","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"},{"key":"2025032208012553200_btaf104-B29","doi-asserted-by":"crossref","first-page":"3242","DOI":"10.1093\/bioinformatics\/btaa115","article-title":"MUM&Co: accurate detection of all SV types through whole-genome alignment","volume":"36","author":"O'Donnell","year":"2020","journal-title":"Bioinformatics"},{"key":"2025032208012553200_btaf104-B30","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1145\/3641854","article-title":"Generic non-recursive suffix array construction","volume":"20","author":"Olbrich","year":"2024","journal-title":"ACM Trans Algorithms"},{"key":"2025032208012553200_btaf104-B31","first-page":"459","author":"Olbrich","year":"2025"},{"key":"2025032208012553200_btaf104-B32","doi-asserted-by":"crossref","first-page":"302","DOI":"10.1038\/s41587-020-0719-5","article-title":"Fully phased human genome assembly without parental data using single-cell strand sequencing and long reads","volume":"39","author":"Porubsky","year":"2021","journal-title":"Nat Biotechnol"},{"key":"2025032208012553200_btaf104-B33","doi-asserted-by":"crossref","first-page":"4","DOI":"10.1145\/1242471.1242472","article-title":"A taxonomy of suffix array construction algorithms","volume":"39","author":"Puglisi","year":"2007","journal-title":"ACM Comput Surv"},{"key":"2025032208012553200_btaf104-B34","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"},{"key":"2025032208012553200_btaf104-B35","doi-asserted-by":"crossref","first-page":"13950","DOI":"10.1073\/pnas.0506758102","article-title":"Genome analysis of multiple pathogenic isolates of streptococcus agalactiae: implications for the microbial pan-genome","volume":"102","author":"Tettelin","year":"2005","journal-title":"Proc Natl Acad Sci USA"},{"key":"2025032208012553200_btaf104-B36","doi-asserted-by":"crossref","first-page":"524","DOI":"10.1186\/s13059-014-0524-x","article-title":"The harvest suite for rapid core-genome alignment and visualization of thousands of intraspecific microbial genomes","volume":"15","author":"Treangen","year":"2014","journal-title":"Genome Biol"},{"key":"2025032208012553200_btaf104-B37","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"}],"container-title":["Bioinformatics"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/academic.oup.com\/bioinformatics\/advance-article-pdf\/doi\/10.1093\/bioinformatics\/btaf104\/62432069\/btaf104.pdf","content-type":"application\/pdf","content-version":"am","intended-application":"syndication"},{"URL":"https:\/\/academic.oup.com\/bioinformatics\/article-pdf\/41\/3\/btaf104\/62432069\/btaf104.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"syndication"},{"URL":"https:\/\/academic.oup.com\/bioinformatics\/article-pdf\/41\/3\/btaf104\/62432069\/btaf104.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,3,23]],"date-time":"2025-03-23T11:20:05Z","timestamp":1742728805000},"score":1,"resource":{"primary":{"URL":"https:\/\/academic.oup.com\/bioinformatics\/article\/doi\/10.1093\/bioinformatics\/btaf104\/8082102"}},"subtitle":[],"editor":[{"given":"Yann","family":"Ponty","sequence":"additional","affiliation":[]}],"short-title":[],"issued":{"date-parts":[[2025,3]]},"references-count":37,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2025,3,4]]}},"URL":"https:\/\/doi.org\/10.1093\/bioinformatics\/btaf104","relation":{},"ISSN":["1367-4811"],"issn-type":[{"value":"1367-4811","type":"electronic"}],"subject":[],"published-other":{"date-parts":[[2025,3]]},"published":{"date-parts":[[2025,3]]},"article-number":"btaf104"}}