{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,2,26]],"date-time":"2026-02-26T20:34:32Z","timestamp":1772138072299,"version":"3.50.1"},"reference-count":37,"publisher":"Oxford University Press (OUP)","issue":"1","license":[{"start":{"date-parts":[[2025,1,3]],"date-time":"2025-01-03T00:00:00Z","timestamp":1735862400000},"content-version":"vor","delay-in-days":8,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2024,12,26]]},"abstract":"<jats:title>Abstract<\/jats:title>\n                  <jats:sec>\n                    <jats:title>Motivation<\/jats:title>\n                    <jats:p>Partial order alignment is a widely used method for computing multiple sequence alignments, with applications in genome assembly and pangenomics, among many others. Current algorithms to compute the optimal, gap-affine partial order alignment do not scale well to larger graphs and sequences. While heuristic approaches exist, they do not guarantee optimal alignment and sacrifice alignment accuracy.<\/jats:p>\n                  <\/jats:sec>\n                  <jats:sec>\n                    <jats:title>Results<\/jats:title>\n                    <jats:p>We present POASTA, a new optimal algorithm for partial order alignment that exploits long stretches of matching sequence between the graph and a query. We benchmarked POASTA against the state-of-the-art on several diverse bacterial gene datasets and demonstrated an average speed-up of 4.1\u00d7 and up to 9.8\u00d7, using less memory. POASTA\u2019s memory scaling characteristics enabled the construction of much larger POA graphs than previously possible, as demonstrated by megabase-length alignments of 342 Mycobacterium tuberculosis sequences.<\/jats:p>\n                  <\/jats:sec>\n                  <jats:sec>\n                    <jats:title>Availability and implementation<\/jats:title>\n                    <jats:p>POASTA is available on Github at https:\/\/github.com\/broadinstitute\/poasta.<\/jats:p>\n                  <\/jats:sec>","DOI":"10.1093\/bioinformatics\/btae757","type":"journal-article","created":{"date-parts":[[2025,1,2]],"date-time":"2025-01-02T15:19:20Z","timestamp":1735831160000},"source":"Crossref","is-referenced-by-count":3,"title":["Fast and exact gap-affine partial order alignment with POASTA"],"prefix":"10.1093","volume":"41","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-7565-5859","authenticated-orcid":false,"given":"Lucas R","family":"van Dijk","sequence":"first","affiliation":[{"name":"Infectious Disease and Microbiome Program, Broad Institute of MIT and Harvard , Cambridge, MA 02142,","place":["United States"]},{"name":"Delft Bioinformatics Lab, TU Delft , 2628 XE Delft,","place":["The Netherlands"]}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-3800-0714","authenticated-orcid":false,"given":"Abigail L","family":"Manson","sequence":"additional","affiliation":[{"name":"Infectious Disease and Microbiome Program, Broad Institute of MIT and Harvard , Cambridge, MA 02142,","place":["United States"]}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-7857-9145","authenticated-orcid":false,"given":"Ashlee M","family":"Earl","sequence":"additional","affiliation":[{"name":"Infectious Disease and Microbiome Program, Broad Institute of MIT and Harvard , Cambridge, MA 02142,","place":["United States"]}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-6212-5736","authenticated-orcid":false,"given":"Kiran V","family":"Garimella","sequence":"additional","affiliation":[{"name":"Data Sciences Platform, Broad Institute of MIT and Harvard , Cambridge, MA 02142,","place":["United States"]}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-7205-7431","authenticated-orcid":false,"given":"Thomas","family":"Abeel","sequence":"additional","affiliation":[{"name":"Infectious Disease and Microbiome Program, Broad Institute of MIT and Harvard , Cambridge, MA 02142,","place":["United States"]},{"name":"Delft Bioinformatics Lab, TU Delft , 2628 XE Delft,","place":["The Netherlands"]}]}],"member":"286","published-online":{"date-parts":[[2025,1,3]]},"reference":[{"key":"2025012310374412500_btae757-B1","doi-asserted-by":"publisher","first-page":"1784","DOI":"10.1038\/s41467-018-08148-z","article-title":"Multi-platform discovery of haplotype-resolved structural variation in human genomes","volume":"10","author":"Chaisson","year":"2019","journal-title":"Nat Commun"},{"key":"2025012310374412500_btae757-B2","doi-asserted-by":"publisher","first-page":"563","DOI":"10.1038\/nmeth.2474","article-title":"Nonhybrid, finished microbial genome assemblies from long-read SMRT sequencing data","volume":"10","author":"Chin","year":"2013","journal-title":"Nat Methods"},{"key":"2025012310374412500_btae757-B3","doi-asserted-by":"publisher","first-page":"22","DOI":"10.1145\/322358.322360","article-title":"Bidirectional heuristic search again","volume":"30","author":"de Champeaux","year":"1983","journal-title":"J ACM"},{"key":"2025012310374412500_btae757-B4","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9780511790492","volume-title":"Biological Sequence Analysis: Probabilistic Models of Proteins and Nucleic Acids","author":"Durbin","year":"1998","edition":"1st edn"},{"key":"2025012310374412500_btae757-B5","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":"2025012310374412500_btae757-B6","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":"2025012310374412500_btae757-B7","doi-asserted-by":"publisher","first-page":"2008","DOI":"10.1038\/s41592-024-02430-3","volume-title":"Nat Methods","author":"Garrison"},{"key":"2025012310374412500_btae757-B8","doi-asserted-by":"publisher","first-page":"1","author":"Groot Koerkamp","DOI":"10.4230\/LIPIcs.WABI.2024.17"},{"key":"2025012310374412500_btae757-B9","doi-asserted-by":"publisher","first-page":"16","DOI":"10.1186\/s13015-018-0134-3","article-title":"Superbubbles revisited","volume":"13","author":"G\u00e4rtner","year":"2018","journal-title":"Algorithms Mol Biol"},{"key":"2025012310374412500_btae757-B10","first-page":"645","volume-title":"Proceedings of the 1st International Conference on Industrial and Engineering Applications of Artificial Intelligence and Expert Systems\u2014Volume 2, IEA\/AIE\u201988, New York, NY, USA, June 1988","author":"Hadlock","year":"1988"},{"key":"2025012310374412500_btae757-B11","doi-asserted-by":"publisher","first-page":"100","DOI":"10.1109\/TSSC.1968.300136","article-title":"A formal basis for the heuristic determination of minimum cost paths","volume":"4","author":"Hart","year":"1968","journal-title":"IEEE Trans Syst Sci Cyber"},{"key":"2025012310374412500_btae757-B12","doi-asserted-by":"publisher","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":"2025012310374412500_btae757-B13","doi-asserted-by":"publisher","author":"Holt","DOI":"10.1093\/bioinformatics\/btae042"},{"key":"2025012310374412500_btae757-B14","doi-asserted-by":"publisher","first-page":"104","DOI":"10.1007\/978-3-030-45257-5_7","volume-title":"Research in Computational Molecular Biology, Lecture Notes in Computer Science","author":"Ivanov","year":"2020"},{"key":"2025012310374412500_btae757-B15","doi-asserted-by":"publisher","first-page":"306","DOI":"10.1007\/978-3-031-04749-7_22","volume-title":"Research in Computational Molecular Biology, Lecture Notes in Computer Science","author":"Ivanov","year":"2022"},{"key":"2025012310374412500_btae757-B16","doi-asserted-by":"publisher","first-page":"451","DOI":"10.1109\/IPDPS.2019.00055","volume-title":"2019 IEEE International Parallel and Distributed Processing Symposium (IPDPS), Rio de Janeiro, Brazil, May 2019","author":"Jain","year":"2019"},{"key":"2025012310374412500_btae757-B17","doi-asserted-by":"publisher","first-page":"640","DOI":"10.1089\/cmb.2019.0066","article-title":"On the complexity of sequence-to-graph alignment","volume":"27","author":"Jain","year":"2020","journal-title":"J Comput Biol"},{"key":"2025012310374412500_btae757-B18","doi-asserted-by":"publisher","first-page":"2157","DOI":"10.1128\/jcm.00691-14","article-title":"Profiling of rpoB mutations and MICs for rifampin and rifabutin in Mycobacterium tuberculosis","volume":"52","author":"Jamieson","year":"2014","journal-title":"J Clin Microbiol"},{"key":"2025012310374412500_btae757-B19","doi-asserted-by":"publisher","first-page":"772","DOI":"10.1093\/molbev\/mst010","article-title":"MAFFT multiple sequence alignment software version 7: improvements in performance and usability","volume":"30","author":"Katoh","year":"2013","journal-title":"Mol Biol Evol"},{"key":"2025012310374412500_btae757-B20","doi-asserted-by":"publisher","first-page":"999","DOI":"10.1093\/bioinformatics\/btg109","article-title":"Generating consensus sequences from partial order multiple sequence alignment graphs","volume":"19","author":"Lee","year":"2003","journal-title":"Bioinformatics"},{"key":"2025012310374412500_btae757-B21","doi-asserted-by":"publisher","first-page":"452","DOI":"10.1093\/bioinformatics\/18.3452","article-title":"Multiple sequence alignment using partial order graphs","volume":"18","author":"Lee","year":"2002","journal-title":"Bioinformatics"},{"key":"2025012310374412500_btae757-B22","doi-asserted-by":"publisher","first-page":"733","DOI":"10.1038\/nmeth.3444","article-title":"A complete bacterial genome assembled de novo using only nanopore sequencing data","volume":"12","author":"Loman","year":"2015","journal-title":"Nat Methods"},{"key":"2025012310374412500_btae757-B23","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":"2025012310374412500_btae757-B24","doi-asserted-by":"publisher","first-page":"10283","DOI":"10.1038\/s41598-019-46756-x","article-title":"Identification and characterization of genetic determinants of isoniazid and rifampicin resistance in Mycobacterium tuberculosis in Southern India","volume":"9","author":"Munir","year":"2019","journal-title":"Sci Rep"},{"key":"2025012310374412500_btae757-B25","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":"2025012310374412500_btae757-B26","doi-asserted-by":"publisher","first-page":"132","DOI":"10.1186\/s13059-016-0997-x","article-title":"Mash: fast genome and metagenome distance estimation using MinHash","volume":"17","author":"Ondov","year":"2016","journal-title":"Genome Biol"},{"key":"2025012310374412500_btae757-B27","doi-asserted-by":"publisher","first-page":"338","DOI":"10.1007\/978-3-642-40453-5_26","volume-title":"Algorithms in Bioinformatics: 13th International Workshop","author":"Onodera","year":"2013"},{"key":"2025012310374412500_btae757-B28","author":"Rautiainen","year":"2017"},{"key":"2025012310374412500_btae757-B29","doi-asserted-by":"publisher","first-page":"253","DOI":"10.1186\/s13059-020-02157-2","article-title":"GraphAligner: rapid and versatile sequence-to-graph alignment","volume":"21","author":"Rautiainen","year":"2020","journal-title":"Genome Biol"},{"key":"2025012310374412500_btae757-B30","doi-asserted-by":"publisher","first-page":"461","DOI":"10.1038\/s41592-018-0001-7","article-title":"Accurate detection of complex structural variations using single-molecule sequencing","volume":"15","author":"Sedlazeck","year":"2018","journal-title":"Nat Methods"},{"key":"2025012310374412500_btae757-B31","author":"Suzuki","year":"2017"},{"key":"2025012310374412500_btae757-B32","doi-asserted-by":"publisher","first-page":"132","DOI":"10.1016\/0196-6774(85)90023-9","article-title":"Finding approximate patterns in strings","volume":"6","author":"Ukkonen","year":"1985","journal-title":"J Algorithms"},{"key":"2025012310374412500_btae757-B33","doi-asserted-by":"publisher","first-page":"737","DOI":"10.1101\/gr.214270.116","article-title":"Fast and accurate de novo genome assembly from long uncorrected reads","volume":"27","author":"Vaser","year":"2017","journal-title":"Genome Res"},{"key":"2025012310374412500_btae757-B34","doi-asserted-by":"publisher","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":"2025012310374412500_btae757-B35","doi-asserted-by":"publisher","first-page":"R151","DOI":"10.1186\/gb-2008-9-10-r151","article-title":"A simple, fast, and accurate method of phylogenomic inference","volume":"9","author":"Wu","year":"2008","journal-title":"Genome Biol"},{"key":"2025012310374412500_btae757-B36","author":"Zhang","year":"2022"},{"key":"2025012310374412500_btae757-B37","author":"Zhou","year":"2015"}],"container-title":["Bioinformatics"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/academic.oup.com\/bioinformatics\/advance-article-pdf\/doi\/10.1093\/bioinformatics\/btae757\/61327927\/btae757.pdf","content-type":"application\/pdf","content-version":"am","intended-application":"syndication"},{"URL":"https:\/\/academic.oup.com\/bioinformatics\/article-pdf\/41\/1\/btae757\/61327927\/btae757.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"syndication"},{"URL":"https:\/\/academic.oup.com\/bioinformatics\/article-pdf\/41\/1\/btae757\/61327927\/btae757.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,1,23]],"date-time":"2025-01-23T05:38:00Z","timestamp":1737610680000},"score":1,"resource":{"primary":{"URL":"https:\/\/academic.oup.com\/bioinformatics\/article\/doi\/10.1093\/bioinformatics\/btae757\/7942505"}},"subtitle":[],"editor":[{"given":"Peter","family":"Robinson","sequence":"additional","affiliation":[]}],"short-title":[],"issued":{"date-parts":[[2024,12,26]]},"references-count":37,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2024,12,26]]}},"URL":"https:\/\/doi.org\/10.1093\/bioinformatics\/btae757","relation":{"has-preprint":[{"id-type":"doi","id":"10.1101\/2024.05.23.595521","asserted-by":"object"}]},"ISSN":["1367-4811"],"issn-type":[{"value":"1367-4811","type":"electronic"}],"subject":[],"published-other":{"date-parts":[[2025,1]]},"published":{"date-parts":[[2024,12,26]]},"article-number":"btae757"}}