{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,21]],"date-time":"2026-03-21T05:12:03Z","timestamp":1774069923905,"version":"3.50.1"},"reference-count":23,"publisher":"Oxford University Press (OUP)","issue":"6","license":[{"start":{"date-parts":[[2025,5,9]],"date-time":"2025-05-09T00:00:00Z","timestamp":1746748800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"funder":[{"DOI":"10.13039\/501100001665","name":"French National Research Agency","doi-asserted-by":"publisher","award":["ANR-22-PEAE-0005"],"award-info":[{"award-number":["ANR-22-PEAE-0005"]}],"id":[{"id":"10.13039\/501100001665","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2025,6,2]]},"abstract":"<jats:title>Abstract<\/jats:title>\n                  <jats:sec>\n                    <jats:title>Motivation<\/jats:title>\n                    <jats:p>Pangenome variation graphs are an increasingly used tool to perform genome analysis, aiming to replace a linear reference in a wide variety of genomic analyses. The construction of a variation graph from a collection of chromosome-size genome sequences is a difficult task that is generally addressed using a number of heuristics. The question that arises is to what extent the construction method influences the resulting graph, and the characterization of variability.<\/jats:p>\n                  <\/jats:sec>\n                  <jats:sec>\n                    <jats:title>Results<\/jats:title>\n                    <jats:p>We aim to characterize the differences between variation graphs derived from the same set of genomes with a metric which expresses and pinpoint differences. We designed a pairwise variation graph comparison algorithm, which establishes an edit distance between variation graphs, threading the genomes through both graphs. We applied our method to pangenome graphs built from yeast and human chromosome collections, and demonstrate that our method effectively characterizes discordances between pangenome graph construction methods and scales to real datasets.<\/jats:p>\n                  <\/jats:sec>\n                  <jats:sec>\n                    <jats:title>Availability and implementation<\/jats:title>\n                    <jats:p>pancat compare is published as free Rust software under the AGPL3.0 open source license. Source code and documentation are available at https:\/\/github.com\/dubssieg\/rs-pancat-compare. Snapshot available on Software Heritage at swh:1:dir:61acda8ba3dac1709ed60530147d3871831be629.<\/jats:p>\n                  <\/jats:sec>","DOI":"10.1093\/bioinformatics\/btaf291","type":"journal-article","created":{"date-parts":[[2025,5,8]],"date-time":"2025-05-08T07:33:24Z","timestamp":1746689604000},"source":"Crossref","is-referenced-by-count":2,"title":["Pairwise graph edit distance characterizes the impact of the construction method on pangenome graphs"],"prefix":"10.1093","volume":"41","author":[{"ORCID":"https:\/\/orcid.org\/0009-0001-9800-0644","authenticated-orcid":false,"given":"Siegfried","family":"Dubois","sequence":"first","affiliation":[{"name":"Univ Rennes, CNRS, Inria, IRISA-UMR 6074 , Rennes F-35000,","place":["France"]},{"name":"GenPhySE, Universit\u00e9 de Toulouse, INRAE, ENVT , Castanet-Tolosan 31320,","place":["France"]}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-4895-8731","authenticated-orcid":false,"given":"Matthias","family":"Zytnicki","sequence":"additional","affiliation":[{"name":"MIAT, INRAE , Castanet-Tolosan 31320,","place":["France"]}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-8675-170X","authenticated-orcid":false,"given":"Claire","family":"Lemaitre","sequence":"additional","affiliation":[{"name":"Univ Rennes, CNRS, Inria, IRISA-UMR 6074 , Rennes F-35000,","place":["France"]}]},{"given":"Thomas","family":"Faraut","sequence":"additional","affiliation":[{"name":"GenPhySE, Universit\u00e9 de Toulouse, INRAE, ENVT , Castanet-Tolosan 31320,","place":["France"]}]}],"member":"286","published-online":{"date-parts":[[2025,5,9]]},"reference":[{"key":"2025070408281709000_btaf291-B1","doi-asserted-by":"crossref","first-page":"83","DOI":"10.1038\/s41586-020-2371-0","article-title":"Mapping and characterization of structural variation in 17,795 human genomes","volume":"583","author":"Abel","year":"2020","journal-title":"Nature"},{"key":"2025070408281709000_btaf291-B2","doi-asserted-by":"crossref","first-page":"eabl4178","DOI":"10.1126\/science.abl4178","article-title":"Complete genomic and epigenetic maps of human centromeres","volume":"376","author":"Altemose","year":"2022","journal-title":"Science"},{"key":"2025070408281709000_btaf291-B3","doi-asserted-by":"crossref","first-page":"274","DOI":"10.1186\/s13059-023-03098-2","article-title":"Comparing methods for constructing and representing human pangenome graphs","volume":"24","author":"Andreace","year":"2023","journal-title":"Genome Biol"},{"key":"2025070408281709000_btaf291-B4","doi-asserted-by":"crossref","first-page":"7","DOI":"10.1101\/gr.278203.123","article-title":"Small polymorphisms are a source of ancestral bias in structural variant breakpoint placement","volume":"34","author":"Audano","year":"2024","journal-title":"Genome Res"},{"key":"2025070408281709000_btaf291-B5","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":"2025070408281709000_btaf291-B6","doi-asserted-by":"crossref","first-page":"573","DOI":"10.1093\/nar\/27.2.573","article-title":"Tandem repeats finder: a program to analyze DNA sequences","volume":"27","author":"Benson","year":"1999","journal-title":"Nucleic Acids Res"},{"key":"2025070408281709000_btaf291-B7","doi-asserted-by":"crossref","first-page":"114","DOI":"10.1007\/978-3-031-43980-3_10","volume-title":"String Processing and Information Retrieval","author":"Cicherski","year":"2023"},{"key":"2025070408281709000_btaf291-B8","doi-asserted-by":"crossref","first-page":"btac743","DOI":"10.1093\/bioinformatics\/btac743","article-title":"Unbiased pangenome graphs","volume":"39","author":"Garrison","year":"2023","journal-title":"Bioinformatics"},{"key":"2025070408281709000_btaf291-B9","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":"2025070408281709000_btaf291-B10","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":"2025070408281709000_btaf291-B11","first-page":"663","article-title":"Pangenome Graph Construction from Genome Alignment with Minigraph-Cactus","author":"Hickey","year":"2023"},{"key":"2025070408281709000_btaf291-B12","doi-asserted-by":"crossref","first-page":"4","DOI":"10.1186\/s13015-022-00210-2","article-title":"Fast characterization of segmental duplication structure in multiple genome assemblies","volume":"17","author":"I\u0161eri\u0107","year":"2022","journal-title":"Algorithms Mol Biol"},{"key":"2025070408281709000_btaf291-B13","doi-asserted-by":"crossref","first-page":"gkae1294","DOI":"10.1093\/nar\/gkae1294","article-title":"Highly accurate Korean draft genomes reveal structural variation highlighting human telomere evolution","volume":"53","author":"Kim","year":"2025","journal-title":"Nucleic Acids Res"},{"key":"2025070408281709000_btaf291-B14","author":"Leonard"},{"key":"2025070408281709000_btaf291-B15","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":"2025070408281709000_btaf291-B16","doi-asserted-by":"crossref","first-page":"53","DOI":"10.1007\/3-540-45748-8_5","volume-title":"Peer-to-Peer Systems","author":"Maymounkov","year":"2002"},{"key":"2025070408281709000_btaf291-B17","doi-asserted-by":"crossref","first-page":"1390","DOI":"10.1038\/s41588-023-01459-y","article-title":"Telomere-to-telomere assemblies of 142 strains characterize the genome structural landscape in Saccharomyces cerevisiae","volume":"55","author":"O'Donnell","year":"2023","journal-title":"Nat Genet"},{"key":"2025070408281709000_btaf291-B18","doi-asserted-by":"crossref","first-page":"665","DOI":"10.1101\/gr.214155.116","article-title":"Genome graphs and the evolution of genome inference","volume":"27","author":"Paten","year":"2017","journal-title":"Genome Res"},{"key":"2025070408281709000_btaf291-B19","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":"2025070408281709000_btaf291-B20","doi-asserted-by":"crossref","first-page":"eabj6965","DOI":"10.1126\/science.abj6965","article-title":"Segmental duplications and their variation in a complete human genome","volume":"376","author":"Vollger","year":"2022","journal-title":"Science"},{"key":"2025070408281709000_btaf291-B21","doi-asserted-by":"crossref","first-page":"e0228728","DOI":"10.1371\/journal.pone.0228728","article-title":"Metrics for graph comparison: a practitioner\u2019s guide","volume":"15","author":"Wills","year":"2020","journal-title":"PLoS One"},{"key":"2025070408281709000_btaf291-B22","doi-asserted-by":"crossref","first-page":"913","DOI":"10.1038\/ng.3847","article-title":"Contrasting evolutionary genome dynamics between domesticated and wild yeasts","volume":"49","author":"Yue","year":"2017","journal-title":"Nat Genet"},{"key":"2025070408281709000_btaf291-B23","doi-asserted-by":"crossref","first-page":"1397036","DOI":"10.3389\/fbinf.2024.1397036","article-title":"Pangenome comparison via ED strings","volume":"4","author":"Zuba","year":"2024","journal-title":"Front Bioinform"}],"container-title":["Bioinformatics"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/academic.oup.com\/bioinformatics\/advance-article-pdf\/doi\/10.1093\/bioinformatics\/btaf291\/63136787\/btaf291.pdf","content-type":"application\/pdf","content-version":"am","intended-application":"syndication"},{"URL":"https:\/\/academic.oup.com\/bioinformatics\/article-pdf\/41\/6\/btaf291\/63136787\/btaf291.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"syndication"},{"URL":"https:\/\/academic.oup.com\/bioinformatics\/article-pdf\/41\/6\/btaf291\/63136787\/btaf291.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,7,4]],"date-time":"2025-07-04T08:28:26Z","timestamp":1751617706000},"score":1,"resource":{"primary":{"URL":"https:\/\/academic.oup.com\/bioinformatics\/article\/doi\/10.1093\/bioinformatics\/btaf291\/8127914"}},"subtitle":[],"editor":[{"given":"Pier Luigi","family":"Martelli","sequence":"additional","affiliation":[]}],"short-title":[],"issued":{"date-parts":[[2025,5,9]]},"references-count":23,"journal-issue":{"issue":"6","published-print":{"date-parts":[[2025,6,2]]}},"URL":"https:\/\/doi.org\/10.1093\/bioinformatics\/btaf291","relation":{"has-preprint":[{"id-type":"doi","id":"10.1101\/2024.12.06.627166","asserted-by":"object"}]},"ISSN":["1367-4811"],"issn-type":[{"value":"1367-4811","type":"electronic"}],"subject":[],"published-other":{"date-parts":[[2025,6]]},"published":{"date-parts":[[2025,5,9]]},"article-number":"btaf291"}}