{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,11,5]],"date-time":"2025-11-05T07:00:02Z","timestamp":1762326002819,"version":"3.41.2"},"reference-count":53,"publisher":"Frontiers Media SA","license":[{"start":{"date-parts":[[2024,9,26]],"date-time":"2024-09-26T00:00:00Z","timestamp":1727308800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"funder":[{"DOI":"10.13039\/501100007601","name":"Horizon 2020","doi-asserted-by":"publisher","award":["872539 956229 101034253"],"award-info":[{"award-number":["872539 956229 101034253"]}],"id":[{"id":"10.13039\/501100007601","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100024370","name":"Ministero dell'Istruzione e del Merito","doi-asserted-by":"publisher","award":["YRB97K"],"award-info":[{"award-number":["YRB97K"]}],"id":[{"id":"10.13039\/501100024370","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["frontiersin.org"],"crossmark-restriction":true},"short-container-title":["Front. Bioinform."],"abstract":"<jats:sec><jats:title>Introduction<\/jats:title><jats:p>An elastic-degenerate (ED) string is a sequence of sets of strings. It can also be seen as a directed acyclic graph whose edges are labeled by strings. The notion of ED strings was introduced as a simple alternative to variation and sequence graphs for representing a pangenome, that is, a collection of genomic sequences to be analyzed jointly or to be used as a reference.<\/jats:p><\/jats:sec><jats:sec><jats:title>Methods<\/jats:title><jats:p>In this study, we define notions of <jats:italic>matching statistics<\/jats:italic> of two ED strings as similarity measures between pangenomes and, consequently infer a corresponding distance measure. We then show that both measures can be computed efficiently, in both theory and practice, by employing the <jats:italic>intersection graph<\/jats:italic> of two ED strings.<\/jats:p><\/jats:sec><jats:sec><jats:title>Results<\/jats:title><jats:p>We also implemented our methods as a software tool for pangenome comparison and evaluated their efficiency and effectiveness using both synthetic and real datasets.<\/jats:p><\/jats:sec><jats:sec><jats:title>Discussion<\/jats:title><jats:p>As for efficiency, we compare the runtime of the intersection graph method against the classic product automaton construction showing that the intersection graph is faster by up to one order of magnitude. For showing effectiveness, we used real SARS-CoV-2 datasets and our matching statistics similarity measure to reproduce a well-established clade classification of SARS-CoV-2, thus demonstrating that the classification obtained by our method is in accordance with the existing one.<\/jats:p><\/jats:sec>","DOI":"10.3389\/fbinf.2024.1397036","type":"journal-article","created":{"date-parts":[[2024,9,26]],"date-time":"2024-09-26T05:10:38Z","timestamp":1727327438000},"update-policy":"https:\/\/doi.org\/10.3389\/crossmark-policy","source":"Crossref","is-referenced-by-count":4,"title":["Pangenome comparison via ED strings"],"prefix":"10.3389","volume":"4","author":[{"given":"Esteban","family":"Gabory","sequence":"first","affiliation":[]},{"given":"Moses Njagi","family":"Mwaniki","sequence":"additional","affiliation":[]},{"given":"Nadia","family":"Pisanti","sequence":"additional","affiliation":[]},{"given":"Solon P.","family":"Pissis","sequence":"additional","affiliation":[]},{"given":"Jakub","family":"Radoszewski","sequence":"additional","affiliation":[]},{"given":"Michelle","family":"Sweering","sequence":"additional","affiliation":[]},{"given":"Wiktor","family":"Zuba","sequence":"additional","affiliation":[]}],"member":"1965","published-online":{"date-parts":[[2024,9,26]]},"reference":[{"key":"B1","first-page":"1","article-title":"Degenerate string comparison and applications","volume-title":"18th international workshop on algorithms in bioinformatics, WABI 2018, August 20-22, 2018, Helsinki, Finland","author":"Alzamel","year":"2018"},{"key":"B2","doi-asserted-by":"publisher","first-page":"41","DOI":"10.3233\/FI-2020-1947","article-title":"Comparing degenerate strings","volume":"175","author":"Alzamel","year":"2020","journal-title":"Fundam. Inf."},{"key":"B3","first-page":"1","article-title":"Faster online elastic degenerate string matching","volume-title":"Annual symposium on combinatorial pattern matching, CPM 2018, july 2-4, 2018 - qingdao, China","author":"Aoyama","year":"2018"},{"key":"B4","doi-asserted-by":"publisher","first-page":"76","DOI":"10.1016\/J.TCS.2016.01.023","article-title":"Sequence similarity measures based on bounded hamming distance","volume":"638","author":"Apostolico","year":"2016","journal-title":"Theor. Comput. Sci."},{"key":"B5","first-page":"183","article-title":"Alignment free sequence similarity with bounded hamming distance","volume-title":"Data compression conference, DCC 2014, snowbird, UT, USA, 26-28 march, 2014","author":"Apostolico","year":"2014"},{"key":"B6","doi-asserted-by":"publisher","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":"B7","doi-asserted-by":"publisher","first-page":"1897","DOI":"10.1093\/bioinformatics\/btq301","article-title":"Cassis: detection of genomic rearrangement breakpoints","volume":"26","author":"Baudet","year":"2010","journal-title":"Bioinform"},{"key":"B8","first-page":"1","article-title":"Even faster elastic-degenerate string matching via fast matrix multiplication","volume-title":"46th international colloquium on automata, languages, and programming, ICALP 2019, july 9-12, 2019, patras, Greece","author":"Bernardini","year":"2019"},{"key":"B9","doi-asserted-by":"publisher","first-page":"549","DOI":"10.1137\/20M1368033","article-title":"Elastic-degenerate string matching via fast matrix multiplication","volume":"51","author":"Bernardini","year":"2022","journal-title":"SIAM J. Comput."},{"key":"B10","doi-asserted-by":"crossref","first-page":"74","DOI":"10.1007\/978-3-319-67428-5_7","article-title":"Pattern matching on elastic-degenerate text with errors","volume-title":"24th international symposium on string processing and information retrieval (SPIRE)","author":"Bernardini","year":"2017"},{"key":"B11","doi-asserted-by":"publisher","first-page":"109","DOI":"10.1016\/j.tcs.2019.08.012","article-title":"Approximate pattern matching on elastic-degenerate text","volume":"812","author":"Bernardini","year":"2020","journal-title":"Theor. Comput. Sci."},{"key":"B12","doi-asserted-by":"publisher","first-page":"718","DOI":"10.1089\/cmb.2015.0220","article-title":"On the minimum error correction problem for haplotype assembly in diploid and polyploid genomes","volume":"23","author":"Bonizzoni","year":"2016","journal-title":"J. Comput. Biol."},{"key":"B14","doi-asserted-by":"publisher","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":"B15","first-page":"237","article-title":"Graph-based representations for supporting genome data analysis and visualization: opportunities and challenges","volume-title":"Graph-based representations in pattern recognition - 12th IAPR-TC-15 international workshop, GbRPR 2019, tours, France, june 19-21, 2019, proceedings","author":"Carletti","year":"2019"},{"key":"B16","doi-asserted-by":"publisher","first-page":"4290","DOI":"10.1093\/bioinformatics\/bty506","article-title":"SOPanG: online text searching over a pan-genome","volume":"34","author":"Cis\u0142ak","year":"2018","journal-title":"Bioinformatics"},{"key":"B17","doi-asserted-by":"publisher","first-page":"832","DOI":"10.3389\/fimmu.2017.00832","article-title":"Human leukocyte antigen (HLA) and immune regulation: how do classical and non-classical HLA alleles modulate immune response to human immunodeficiency virus and hepatitis C virus infections?","volume":"8","author":"Crux","year":"2017","journal-title":"Front. Immunol."},{"key":"B18","doi-asserted-by":"publisher","first-page":"5139","DOI":"10.1093\/bioinformatics\/btaa640","article-title":"Efficient dynamic variation graphs","volume":"36","author":"Eizenga","year":"2021","journal-title":"Bioinform"},{"key":"B19","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1145\/3588334","article-title":"On the complexity of string matching for graphs","volume":"19","author":"Equi","year":"2023","journal-title":"ACM Trans. Algorithms"},{"key":"B20","doi-asserted-by":"publisher","first-page":"4391","DOI":"10.1016\/J.TCS.2009.07.020","article-title":"Suffix tree characterization of maximal motifs in biological sequences","volume":"410","author":"Federico","year":"2009","journal-title":"Theor. Comput. Sci."},{"key":"B21","first-page":"1","article-title":"Comparing elastic-degenerate strings: algorithms, lower bounds, and applications","volume-title":"34th annual symposium on combinatorial pattern matching, CPM 2023, june 26-28, 2023, marne-la-vall\u00e9e, France","author":"Gabory","year":"2023"},{"key":"B22","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":"2020","journal-title":"Bioinformatics"},{"key":"B23","doi-asserted-by":"publisher","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":"","journal-title":"Nat. Biotechnol."},{"key":"B24","doi-asserted-by":"publisher","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":"","journal-title":"Nat. Biotechnol."},{"key":"B25","doi-asserted-by":"publisher","first-page":"1377","DOI":"10.1089\/cmb.2022.0411","article-title":"On the hardness of sequence alignment on de bruijn graphs","volume":"29","author":"Gibney","year":"2022","journal-title":"J. Comput. Biol."},{"key":"B26","first-page":"1","article-title":"On-line pattern matching on similar texts","volume-title":"28th annual symposium on combinatorial pattern matching, CPM 2017, july 4-6, 2017, Warsaw, Poland","author":"Grossi","year":"2017"},{"key":"B27","doi-asserted-by":"crossref","first-page":"362","DOI":"10.1007\/978-3-642-04241-6_30","article-title":"MADMX: a novel strategy for maximal dense motif extraction","volume-title":"Algorithms in bioinformatics, 9th international workshop, WABI 2009, Philadelphia, PA, USA, september 12-13, 2009. Proceedings","author":"Grossi","year":"2009"},{"key":"B28","doi-asserted-by":"publisher","first-page":"535","DOI":"10.1089\/CMB.2010.0177","article-title":"MADMX: a strategy for maximal dense motif extraction","volume":"18","author":"Grossi","year":"2011","journal-title":"J. Comput. Biol."},{"key":"B29","doi-asserted-by":"crossref","DOI":"10.1017\/CBO9780511574931","volume-title":"Algorithms on strings, trees, and sequences - computer science and computational biology","author":"Gusfield","year":"1997"},{"key":"B30","doi-asserted-by":"publisher","first-page":"4121","DOI":"10.1093\/bioinformatics\/bty407","article-title":"Nextstrain: real-time tracking of pathogen evolution","volume":"34","author":"Hadfield","year":"2018","journal-title":"Bioinform"},{"key":"B31","doi-asserted-by":"crossref","first-page":"11","DOI":"10.25080\/TCWV9851","article-title":"Exploring network structure, dynamics, and function using networkx","volume-title":"Proceedings of the 7th Python in science conference","author":"Hagberg","year":"2008"},{"volume-title":"Introduction to automata theory, languages, and computation - international edition","year":"2003","author":"Hopcroft","key":"B32"},{"key":"B33","doi-asserted-by":"publisher","first-page":"104616","DOI":"10.1016\/j.ic.2020.104616","article-title":"Efficient pattern matching in elastic-degenerate strings","volume":"279","author":"Iliopoulos","year":"2021","journal-title":"Inf. Comput."},{"key":"B34","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."},{"volume-title":"Finite automata","year":"2004","author":"Lawson","key":"B35"},{"key":"B36","doi-asserted-by":"publisher","first-page":"2000","DOI":"10.1093\/bioinformatics\/btu331","article-title":"kmacs: the k-mismatch average common substring approach to alignment-free sequence comparison","volume":"30","author":"Leimeister","year":"2014","journal-title":"Bioinform"},{"key":"B37","doi-asserted-by":"publisher","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":"B38","doi-asserted-by":"publisher","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":"B39","first-page":"70","article-title":"Fast exact string to D-texts alignments","volume-title":"Proceedings of the 16th international joint conference on biomedical engineering systems and Technologies, BIOSTEC 2023, volume 3: BIOINFORMATICS, Lisbon, Portugal, february 16-18, 2023","author":"Mwaniki","year":"2023"},{"key":"B40","first-page":"204","article-title":"Optimal sequence alignment to ED-strings","volume-title":"Bioinformatics research and applications - 18th international symposium, ISBRA 2022, haifa, Israel, november 14-17, 2022, proceedings","author":"Mwaniki","year":"2022"},{"key":"B44","doi-asserted-by":"publisher","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":"B45","doi-asserted-by":"publisher","first-page":"497","DOI":"10.1016\/J.JDA.2007.03.003","article-title":"Lossless filter for multiple repetitions with hamming distance","volume":"6","author":"Peterlongo","year":"2008","journal-title":"J. Discrete Algorithms"},{"key":"B46","doi-asserted-by":"crossref","first-page":"179","DOI":"10.1007\/11575832_20","article-title":"Lossless filter for finding long multiple approximate repetitions using a new data structure, the bi-factor array","volume-title":"String processing and information retrieval, 12th international conference, SPIRE 2005, Buenos Aires, Argentina, november 2-4, 2005, proceedings","author":"Peterlongo","year":"2005"},{"key":"B47","doi-asserted-by":"publisher","first-page":"3","DOI":"10.1186\/1748-7188-4-3","article-title":"Lossless filter for multiple repeats with bounded edit distance","volume":"4","author":"Peterlongo","year":"2009","journal-title":"Algorithms Mol. Biol."},{"key":"B48","first-page":"1","article-title":"Dictionary matching in elastic-degenerate texts with applications in searching VCF files on-line","volume-title":"17th international symposium on experimental algorithms, SEA 2018, june 27-29, 2018, L\u2019aquila, Italy","author":"Pissis","year":"2018"},{"key":"B49","doi-asserted-by":"publisher","first-page":"6","DOI":"10.1186\/S13015-016-0072-X","article-title":"Missmax: alignment-free sequence comparison with mismatches through filtering and heuristics","volume":"11","author":"Pizzi","year":"2016","journal-title":"Algorithms Mol. Biol."},{"key":"B50","doi-asserted-by":"publisher","first-page":"354","DOI":"10.1038\/s41588-018-0316-4","article-title":"Fast and accurate genomic analyses using genome graphs","volume":"51","author":"Rakocevic","year":"2019","journal-title":"Nat. Genet."},{"key":"B51","doi-asserted-by":"publisher","first-page":"3599","DOI":"10.1093\/bioinformatics\/btz162","article-title":"Bit-parallel sequence-to-graph alignment","volume":"35","author":"Rautiainen","year":"2019","journal-title":"Bioinform"},{"key":"B52","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":"B53","doi-asserted-by":"publisher","first-page":"S148","DOI":"10.1097\/rhu.0000000000001671","article-title":"HLA-B allele, genotype, and haplotype frequencies in a group of healthy individuals in Colombia","volume":"27","author":"Romero-S\u00e1nchez","year":"2021","journal-title":"J. Clin. Rheumatol."},{"key":"B54","doi-asserted-by":"publisher","first-page":"555","DOI":"10.1089\/cmb.1998.5.555","article-title":"Multiple genome rearrangement and breakpoint phylogeny","volume":"5","author":"Sankoff","year":"1998","journal-title":"J. Comput. Biol."},{"key":"B55","doi-asserted-by":"publisher","first-page":"238","DOI":"10.1186\/s12859-017-1658-0","article-title":"A greedy alignment-free distance estimator for phylogenetic inference","volume":"18","author":"Thankachan","year":"2017","journal-title":"BMC Bioinform"},{"key":"B56","doi-asserted-by":"publisher","first-page":"118","DOI":"10.1093\/bib\/bbw089","article-title":"Computational pan-genomics: status, promises and challenges","volume":"19","year":"2018","journal-title":"Briefings Bioinforma."},{"key":"B59","doi-asserted-by":"publisher","first-page":"336","DOI":"10.1089\/cmb.2006.13.336","article-title":"The average common substring approach to phylogenomic reconstruction","volume":"13","author":"Ulitsky","year":"2006","journal-title":"J. Comput. Biol."}],"container-title":["Frontiers in Bioinformatics"],"original-title":[],"link":[{"URL":"https:\/\/www.frontiersin.org\/articles\/10.3389\/fbinf.2024.1397036\/full","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,9,26]],"date-time":"2024-09-26T05:10:45Z","timestamp":1727327445000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.frontiersin.org\/articles\/10.3389\/fbinf.2024.1397036\/full"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2024,9,26]]},"references-count":53,"alternative-id":["10.3389\/fbinf.2024.1397036"],"URL":"https:\/\/doi.org\/10.3389\/fbinf.2024.1397036","relation":{},"ISSN":["2673-7647"],"issn-type":[{"type":"electronic","value":"2673-7647"}],"subject":[],"published":{"date-parts":[[2024,9,26]]},"article-number":"1397036"}}