{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,8,5]],"date-time":"2026-08-05T18:10:48Z","timestamp":1785953448124,"version":"3.56.0"},"reference-count":45,"publisher":"Oxford University Press (OUP)","issue":"8","license":[{"start":{"date-parts":[[2023,7,26]],"date-time":"2023-07-26T00:00:00Z","timestamp":1690329600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"funder":[{"DOI":"10.13039\/100010663","name":"European Research Council","doi-asserted-by":"publisher","id":[{"id":"10.13039\/100010663","id-type":"DOI","asserted-by":"publisher"}]},{"name":"European Union\u2019s Horizon 2020 research and innovation program","award":["851093"],"award-info":[{"award-number":["851093"]}]},{"name":"European Union\u2019s Horizon 2020 research and innovation program","award":["322595"],"award-info":[{"award-number":["322595"]}]},{"name":"European Union\u2019s Horizon 2020 research and innovation program","award":["328877"],"award-info":[{"award-number":["328877"]}]},{"name":"European Union\u2019s Horizon 2020 research and innovation program","award":["308030"],"award-info":[{"award-number":["308030"]}]},{"name":"European Union\u2019s Horizon 2020 research and innovation program","award":["352821"],"award-info":[{"award-number":["352821"]}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2023,8,1]]},"abstract":"<jats:title>Abstract<\/jats:title>\n                  <jats:sec>\n                    <jats:title>Motivation<\/jats:title>\n                    <jats:p>Aligning reads to a variation graph is a standard task in pangenomics, with downstream applications such as improving variant calling. While the vg toolkit [Garrison et al. (Variation graph toolkit improves read mapping by representing genetic variation in the reference. Nat Biotechnol 2018;36:875\u20139)] is a popular aligner of short reads, GraphAligner [Rautiainen and Marschall (GraphAligner: rapid and versatile sequence-to-graph alignment. Genome Biol 2020;21:253\u201328)] is the state-of-the-art aligner of erroneous long reads. GraphAligner works by finding candidate read occurrences based on individually extending the best seeds of the read in the variation graph. However, a more principled approach recognized in the community is to co-linearly chain multiple seeds.<\/jats:p>\n                  <\/jats:sec>\n                  <jats:sec>\n                    <jats:title>Results<\/jats:title>\n                    <jats:p>We present a new algorithm to co-linearly chain a set of seeds in a string labeled acyclic graph, together with the first efficient implementation of such a co-linear chaining algorithm into a new aligner of erroneous long reads to acyclic variation graphs, GraphChainer. We run experiments aligning real and simulated PacBio CLR reads with average error rates 15% and 5%. Compared to GraphAligner, GraphChainer aligns 12\u201317% more reads, and 21\u201328% more total read length, on real PacBio CLR reads from human chromosomes 1, 22, and the whole human pangenome. On both simulated and real data, GraphChainer aligns between 95% and 99% of all reads, and of total read length. We also show that minigraph [Li et al. (The design and construction of reference pangenome graphs with minigraph. Genome Biol 2020;21:265\u201319.)] and minichain [Chandra and Jain (Sequence to graph alignment using gap-sensitive co-linear chaining. In: Proceedings of the 27th Annual International Conference on Research in Computational Molecular Biology (RECOMB 2023). Springer, 2023, 58\u201373.)] obtain an accuracy of &amp;lt;60% on this setting.<\/jats:p>\n                  <\/jats:sec>\n                  <jats:sec>\n                    <jats:title>Availability and implementation<\/jats:title>\n                    <jats:p>GraphChainer is freely available at https:\/\/github.com\/algbio\/GraphChainer. The datasets and evaluation pipeline can be reached from the previous address.<\/jats:p>\n                  <\/jats:sec>","DOI":"10.1093\/bioinformatics\/btad460","type":"journal-article","created":{"date-parts":[[2023,7,26]],"date-time":"2023-07-26T14:10:12Z","timestamp":1690380612000},"source":"Crossref","is-referenced-by-count":19,"title":["Chaining for accurate alignment of erroneous long reads to acyclic variation graphs"],"prefix":"10.1093","volume":"39","author":[{"given":"Jun","family":"Ma","sequence":"first","affiliation":[{"name":"Department of Computer Science, University of Helsinki , 00014 Helsinki, Finland"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-0235-6951","authenticated-orcid":false,"given":"Manuel","family":"C\u00e1ceres","sequence":"additional","affiliation":[{"name":"Department of Computer Science, University of Helsinki , 00014 Helsinki, Finland"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Leena","family":"Salmela","sequence":"additional","affiliation":[{"name":"Department of Computer Science, University of Helsinki , 00014 Helsinki, Finland"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-4454-1493","authenticated-orcid":false,"given":"Veli","family":"M\u00e4kinen","sequence":"additional","affiliation":[{"name":"Department of Computer Science, University of Helsinki , 00014 Helsinki, Finland"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-5747-8350","authenticated-orcid":false,"given":"Alexandru I","family":"Tomescu","sequence":"additional","affiliation":[{"name":"Department of Computer Science, University of Helsinki , 00014 Helsinki, Finland"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"286","published-online":{"date-parts":[[2023,7,26]]},"reference":[{"key":"2023081217040076100_btad460-B1","first-page":"1","volume-title":"International Symposium on String Processing and Information Retrieval","author":"Abouelhoda","year":"2007"},{"key":"2023081217040076100_btad460-B2","doi-asserted-by":"crossref","first-page":"82","DOI":"10.1006\/jagm.1999.1063","article-title":"Pattern matching in hypertext","volume":"35","author":"Amir","year":"2000","journal-title":"J Algorithms"},{"key":"2023081217040076100_btad460-B3","first-page":"51","author":"Backurs","year":"2015"},{"key":"2023081217040076100_btad460-B4","doi-asserted-by":"crossref","first-page":"359","DOI":"10.1137\/1.9781611977073.18","volume-title":"Proceedings of the 33rd Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2022)","author":"C\u00e1ceres","year":"2022"},{"key":"2023081217040076100_btad460-B5","first-page":"58","volume-title":"Proceedings of the 27th Annual International Conference on Research in Computational Molecular Biology (RECOMB 2023)","author":"Chandra","year":"2023"},{"key":"2023081217040076100_btad460-B6","doi-asserted-by":"crossref","first-page":"D854","DOI":"10.1093\/nar\/gkw829","article-title":"The international genome sample resource (IGSR): a worldwide collection of genome variation incorporating the 1000 genomes project data","volume":"45","author":"Clarke","year":"2017","journal-title":"Nucleic Acids Res"},{"key":"2023081217040076100_btad460-B7","first-page":"118","article-title":"Computational pan-genomics: status, promises and challenges","volume":"19","author":"Computational Pan-Genomics Consortium","year":"2018","journal-title":"Brief Bioinformatics"},{"key":"2023081217040076100_btad460-B8","doi-asserted-by":"crossref","first-page":"682","DOI":"10.1038\/ng.3257","article-title":"Improved genome inference in the MHC using a population reference graph","volume":"47","author":"Dilthey","year":"2015","journal-title":"Nat Genet"},{"key":"2023081217040076100_btad460-B9","first-page":"1277","article-title":"Algorithm for solution of a problem of maximum flow in networks with power estimation","volume":"11","author":"Dinic","year":"1970","journal-title":"Soviet Math Doklady"},{"key":"2023081217040076100_btad460-B10","doi-asserted-by":"crossref","first-page":"306","DOI":"10.1186\/s12859-020-03590-7","article-title":"SPAligner: alignment of long diverged molecular sequences to assembly graphs","volume":"21","author":"Dvorkina","year":"2020","journal-title":"BMC Bioinformatics"},{"key":"2023081217040076100_btad460-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":"2023081217040076100_btad460-B12","first-page":"55:1","volume-title":"46th International Colloquium on Automata, Languages, and Programming, ICALP 2019","author":"Equi","year":"2019"},{"key":"2023081217040076100_btad460-B13","first-page":"608","volume-title":"Proceedings of the 47th International Conference on Current Trends in Theory and Practice of Computer Science (SOFSEM 2021)","author":"Equi","year":"2021"},{"key":"2023081217040076100_btad460-B14","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":"2023081217040076100_btad460-B15","first-page":"232","volume-title":"4th Symposium on Simplicity in Algorithms, SOSA 2021, Virtual Conference","author":"Gibney","year":"2021"},{"key":"2023081217040076100_btad460-B16","first-page":"263","volume-title":"International Conference on Research in Computational Molecular Biology","author":"Gibney","year":"2022"},{"key":"2023081217040076100_btad460-B17","doi-asserted-by":"crossref","first-page":"35","DOI":"10.1186\/s13059-020-1941-7","article-title":"Genotyping structural variants in pangenome graphs using the vg toolkit","volume":"21","author":"Hickey","year":"2020","journal-title":"Genome Biol"},{"key":"2023081217040076100_btad460-B18","doi-asserted-by":"crossref","first-page":"21","DOI":"10.3390\/biology6010021","article-title":"SNP discovery using a pangenome: has the single reference approach become obsolete?","volume":"6","author":"Hurgobin","year":"2017","journal-title":"Biology"},{"key":"2023081217040076100_btad460-B19","first-page":"104","volume-title":"International Conference on Research in Computational Molecular Biology","author":"Ivanov","year":"2020"},{"key":"2023081217040076100_btad460-B20","first-page":"306","article-title":"Fast and optimal sequence-to-graph alignment guided by seeds","author":"Ivanov","year":"2021"},{"key":"2023081217040076100_btad460-B21","first-page":"451","author":"Jain","year":"2019"},{"key":"2023081217040076100_btad460-B22","doi-asserted-by":"crossref","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":"2023081217040076100_btad460-B23","doi-asserted-by":"crossref","first-page":"1237","DOI":"10.1089\/cmb.2022.0266","article-title":"Algorithms for colinear chaining with overlaps and gap costs","volume":"29","author":"Jain","year":"2022","journal-title":"J Comput Biol"},{"key":"2023081217040076100_btad460-B24","doi-asserted-by":"crossref","first-page":"7","DOI":"10.1007\/BF01188580","article-title":"Combinatorial algorithms for DNA sequence assembly","volume":"13","author":"Kececioglu","year":"1995","journal-title":"Algorithmica"},{"key":"2023081217040076100_btad460-B25","doi-asserted-by":"crossref","first-page":"105","DOI":"10.1007\/978-3-319-89929-9_7","volume-title":"Research in Computational Molecular Biology","author":"Kuosmanen","year":"2018"},{"key":"2023081217040076100_btad460-B26","doi-asserted-by":"crossref","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":"2023081217040076100_btad460-B27","author":"Li","year":"2013"},{"key":"2023081217040076100_btad460-B28","doi-asserted-by":"crossref","first-page":"2103","DOI":"10.1093\/bioinformatics\/btw152","article-title":"Minimap and miniasm: fast mapping and de novo assembly for noisy long sequences","volume":"32","author":"Li","year":"2016","journal-title":"Bioinformatics"},{"key":"2023081217040076100_btad460-B29","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"},{"key":"2023081217040076100_btad460-B30","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":"2023081217040076100_btad460-B31","first-page":"25:1","volume-title":"31st Annual Symposium on Combinatorial Pattern Matching (CPM 2020), Volume 161 of Leibniz International Proceedings in Informatics (LIPIcs)","author":"M\u00e4kinen","year":"2020"},{"key":"2023081217040076100_btad460-B32","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1145\/3301312","article-title":"Sparse dynamic programming on DAGs with small width","volume":"15","author":"M\u00e4kinen","year":"2019","journal-title":"ACM Trans Algorithms"},{"key":"2023081217040076100_btad460-B33","doi-asserted-by":"crossref","first-page":"81","DOI":"10.1146\/annurev-genom-120120-081921","article-title":"The need for a human pangenome reference sequence","volume":"22","author":"Miga","year":"2021","journal-title":"Annu Rev Genomics Hum Genet"},{"key":"2023081217040076100_btad460-B34","first-page":"38","author":"Myers","year":"1995"},{"key":"2023081217040076100_btad460-B35","doi-asserted-by":"crossref","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":"2023081217040076100_btad460-B36","doi-asserted-by":"crossref","first-page":"3599","DOI":"10.1093\/bioinformatics\/btz162","article-title":"Bit-parallel sequence-to-graph alignment","volume":"35","author":"Rautiainen","year":"2019","journal-title":"Bioinformatics"},{"key":"2023081217040076100_btad460-B37","doi-asserted-by":"crossref","first-page":"3363","DOI":"10.1093\/bioinformatics\/bth408","article-title":"Reducing storage requirements for biological sequence comparison","volume":"20","author":"Roberts","year":"2004","journal-title":"Bioinformatics"},{"key":"2023081217040076100_btad460-B38","doi-asserted-by":"crossref","first-page":"169","DOI":"10.1089\/cmb.2021.0290","article-title":"MONI: a pangenomic index for finding maximal exact matches","volume":"29","author":"Rossi","year":"2022","journal-title":"J Comput Biol"},{"key":"2023081217040076100_btad460-B39","doi-asserted-by":"crossref","first-page":"464","DOI":"10.1007\/BF01940876","article-title":"Randomized search trees","volume":"16","author":"Seidel","year":"1996","journal-title":"Algorithmica"},{"key":"2023081217040076100_btad460-B40","doi-asserted-by":"crossref","first-page":"462","DOI":"10.1007\/978-3-540-39763-2_33","volume-title":"International Workshop on Algorithms in Bioinformatics","author":"Shibuya","year":"2003"},{"key":"2023081217040076100_btad460-B41","doi-asserted-by":"crossref","first-page":"1054","DOI":"10.1038\/s41588-018-0145-5","article-title":"Accurate genotyping across variant classes and lengths using variant graphs","volume":"50","author":"Sibbesen","year":"2018","journal-title":"Nat Genet"},{"key":"2023081217040076100_btad460-B42","doi-asserted-by":"crossref","first-page":"abg8871","DOI":"10.1126\/science.abg8871","article-title":"Pangenomics enables genotyping of known structural variants in 5202 diverse genomes","volume":"374","author":"Sir\u00e9n","year":"2021","journal-title":"Science"},{"key":"2023081217040076100_btad460-B43","doi-asserted-by":"crossref","first-page":"1394","DOI":"10.1093\/bioinformatics\/btw753","article-title":"Edlib: a C\/C++ library for fast, exact sequence alignment using edit distance","volume":"33","author":"\u0160o\u0161i\u0107","year":"2017","journal-title":"Bioinformatics"},{"key":"2023081217040076100_btad460-B44","doi-asserted-by":"crossref","first-page":"87","DOI":"10.1186\/s12864-018-4465-8","article-title":"Towards pan-genome read alignment to improve variation calling","volume":"19","author":"Valenzuela","year":"2018","journal-title":"BMC Genomics"},{"key":"2023081217040076100_btad460-B45","doi-asserted-by":"crossref","first-page":"1316","DOI":"10.21105\/joss.01316","article-title":"Badread: simulation of error-prone long reads","volume":"4","author":"Wick","year":"2019","journal-title":"JOSS"}],"container-title":["Bioinformatics"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/academic.oup.com\/bioinformatics\/advance-article-pdf\/doi\/10.1093\/bioinformatics\/btad460\/50967888\/btad460.pdf","content-type":"application\/pdf","content-version":"am","intended-application":"syndication"},{"URL":"https:\/\/academic.oup.com\/bioinformatics\/article-pdf\/39\/8\/btad460\/51103223\/btad460.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"syndication"},{"URL":"https:\/\/academic.oup.com\/bioinformatics\/article-pdf\/39\/8\/btad460\/51103223\/btad460.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,8,12]],"date-time":"2023-08-12T13:05:05Z","timestamp":1691845505000},"score":1,"resource":{"primary":{"URL":"https:\/\/academic.oup.com\/bioinformatics\/article\/doi\/10.1093\/bioinformatics\/btad460\/7231478"}},"subtitle":[],"editor":[{"given":"Janet","family":"Kelso","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"editor"}]}],"short-title":[],"issued":{"date-parts":[[2023,7,26]]},"references-count":45,"journal-issue":{"issue":"8","published-print":{"date-parts":[[2023,8,1]]}},"URL":"https:\/\/doi.org\/10.1093\/bioinformatics\/btad460","relation":{"has-preprint":[{"id-type":"doi","id":"10.1101\/2022.01.07.475257","asserted-by":"object"}]},"ISSN":["1367-4811"],"issn-type":[{"value":"1367-4811","type":"electronic"}],"subject":[],"published-other":{"date-parts":[[2023,8,1]]},"published":{"date-parts":[[2023,7,26]]},"article-number":"btad460"}}