{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,2,1]],"date-time":"2026-02-01T12:04:17Z","timestamp":1769947457361,"version":"3.49.0"},"reference-count":26,"publisher":"Springer Science and Business Media LLC","issue":"1","license":[{"start":{"date-parts":[[2024,4,29]],"date-time":"2024-04-29T00:00:00Z","timestamp":1714348800000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2024,4,29]],"date-time":"2024-04-29T00:00:00Z","timestamp":1714348800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"funder":[{"name":"National Science Foundation","award":["DBI-1937540"],"award-info":[{"award-number":["DBI-1937540"]}]},{"name":"National Science Foundation","award":["III-2232121"],"award-info":[{"award-number":["III-2232121"]}]},{"DOI":"10.13039\/100000002","name":"National Institutes of Health","doi-asserted-by":"publisher","award":["R01HG012470"],"award-info":[{"award-number":["R01HG012470"]}],"id":[{"id":"10.13039\/100000002","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Algorithms Mol Biol"],"abstract":"<jats:title>Abstract<\/jats:title><jats:p>The graph traversal edit distance (GTED), introduced by Ebrahimpour Boroojeny et al. (2018), is an elegant distance measure defined as the minimum edit distance between strings reconstructed from Eulerian trails in two edge-labeled graphs. GTED can be used to infer evolutionary relationships between species by comparing de Bruijn graphs directly without the computationally costly and error-prone process of genome assembly. Ebrahimpour Boroojeny et al. (2018) propose two ILP formulations for GTED and claim that GTED is polynomially solvable because the linear programming relaxation of one of the ILPs always yields optimal integer solutions. The claim that GTED is polynomially solvable is contradictory to the complexity results of existing string-to-graph matching problems. We resolve this conflict in complexity results by proving that GTED is NP-complete and showing that the ILPs proposed by Ebrahimpour Boroojeny et al. do not solve GTED but instead solve for a lower bound of GTED and are not solvable in polynomial time. In addition, we provide the first two, correct ILP formulations of GTED and evaluate their empirical efficiency. These results provide solid algorithmic foundations for comparing genome graphs and point to the direction of heuristics. The source code to reproduce experimental results is available at <jats:ext-link xmlns:xlink=\"http:\/\/www.w3.org\/1999\/xlink\" ext-link-type=\"uri\" xlink:href=\"https:\/\/github.com\/Kingsford-Group\/gtednewilp\/\">https:\/\/github.com\/Kingsford-Group\/gtednewilp\/<\/jats:ext-link>.<\/jats:p>","DOI":"10.1186\/s13015-024-00262-6","type":"journal-article","created":{"date-parts":[[2024,4,29]],"date-time":"2024-04-29T03:09:58Z","timestamp":1714360198000},"update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":1,"title":["Revisiting the complexity of and algorithms for the graph traversal edit distance and its variants"],"prefix":"10.1186","volume":"19","author":[{"given":"Yutong","family":"Qiu","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Yihang","family":"Shen","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Carl","family":"Kingsford","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2024,4,29]]},"reference":[{"issue":"3","key":"262_CR1","doi-asserted-by":"publisher","first-page":"317","DOI":"10.1089\/cmb.2019.0511","volume":"27","author":"A Ebrahimpour Boroojeny","year":"2020","unstructured":"Ebrahimpour Boroojeny A, Shrestha A, Sharifi-Zarchi A, Gallagher SR, Sahinalp SC, Chitsaz H. Graph traversal edit distance and extensions. J Comput Biol. 2020;27(3):317\u201329.","journal-title":"J Comput Biol"},{"issue":"17","key":"262_CR2","doi-asserted-by":"publisher","first-page":"9748","DOI":"10.1073\/pnas.171285098","volume":"98","author":"PA Pevzner","year":"2001","unstructured":"Pevzner PA, Tang H, Waterman MS. An Eulerian path approach to DNA fragment assembly. Proc Natl Acad Sci USA. 2001;98(17):9748\u201353.","journal-title":"Proc Natl Acad Sci USA"},{"key":"262_CR3","doi-asserted-by":"publisher","unstructured":"Polevikov E, Kolmogorov M. Synteny Paths for Assembly Graphs Comparison. In: Huber, K.T., Gusfield, D. (eds.) 19th International Workshop on Algorithms in Bioinformatics (WABI 2019). Leibniz International Proceedings in Informatics (LIPIcs), vol. 143, pp. 24\u201312414. Schloss Dagstuhl\u2013Leibniz-Zentrum fuer Informatik, Dagstuhl, Germany (2019). https:\/\/doi.org\/10.4230\/LIPIcs.WABI.2019.24 . http:\/\/drops.dagstuhl.de\/opus\/volltexte\/2019\/11054","DOI":"10.4230\/LIPIcs.WABI.2019.24"},{"issue":"6","key":"262_CR4","doi-asserted-by":"publisher","DOI":"10.1016\/j.isci.2020.101224","volume":"23","author":"I Minkin","year":"2020","unstructured":"Minkin I, Medvedev P. Scalable pairwise whole-genome homology mapping of long genomes with Bubbz. IScience. 2020;23(6): 101224.","journal-title":"IScience"},{"key":"262_CR5","doi-asserted-by":"crossref","unstructured":"Mangul S, Koslicki D. Reference-free comparison of microbial communities via de Bruijn graphs. In: Proceedings of the 7th ACM International Conference on Bioinformatics, Computational Biology, and Health Informatics, 2016;68\u201377","DOI":"10.1145\/2975167.2975174"},{"key":"262_CR6","unstructured":"Huntsman S, Rezaee A. De Bruijn entropy and string similarity. arXiv preprint arXiv:1509.02975 (2015)"},{"key":"262_CR7","series-title":"Leibniz International Proceedings in Informatics (LIPIcs)","first-page":"62","volume-title":"41st International Symposium on Mathematical Foundations of Computer Science (MFCS 2016)","author":"O Kupferman","year":"2016","unstructured":"Kupferman O, Vardi G. Eulerian paths with regular constraints. In: Faliszewski P, Muscholl A, Niedermeier R, editors. 41st International Symposium on Mathematical Foundations of Computer Science (MFCS 2016), vol. 58. Leibniz International Proceedings in Informatics (LIPIcs). Dagstuhl, Germany: Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik; 2016. p. 62\u201316215."},{"issue":"4","key":"262_CR8","doi-asserted-by":"publisher","first-page":"640","DOI":"10.1089\/cmb.2019.0066","volume":"27","author":"C Jain","year":"2020","unstructured":"Jain C, Zhang H, Gao Y, Aluru S. On the complexity of sequence-to-graph alignment. J Comput Biol. 2020;27(4):640\u201354.","journal-title":"J Comput Biol"},{"issue":"3","key":"262_CR9","doi-asserted-by":"publisher","first-page":"443","DOI":"10.1016\/0022-2836(70)90057-4","volume":"48","author":"SB Needleman","year":"1970","unstructured":"Needleman SB, Wunsch CD. A general method applicable to the search for similarities in the amino acid sequence of two proteins. J Mol Biol. 1970;48(3):443\u201353.","journal-title":"J Mol Biol"},{"issue":"4","key":"262_CR10","first-page":"393","volume":"2","author":"G Dantzig","year":"1954","unstructured":"Dantzig G, Fulkerson R, Johnson S. Solution of a large-scale traveling-salesman problem. J Oper Res Soc Am. 1954;2(4):393\u2013410.","journal-title":"J Oper Res Soc Am"},{"key":"262_CR11","unstructured":"Dias FH, Williams L, Mumey B, Tomescu AI. Minimum flow decomposition in graphs with cycles using integer linear programming. arXiv preprint arXiv:2209.00042 (2022)"},{"issue":"4","key":"262_CR12","doi-asserted-by":"publisher","first-page":"326","DOI":"10.1145\/321043.321046","volume":"7","author":"CE Miller","year":"1960","unstructured":"Miller CE, Tucker AW, Zemlin RA. Integer programming formulation of traveling salesman problems. J ACM. 1960;7(4):326\u20139.","journal-title":"J ACM"},{"key":"262_CR13","doi-asserted-by":"publisher","first-page":"404","DOI":"10.1093\/bioinformatics\/btac264","volume":"38","author":"Y Qiu","year":"2022","unstructured":"Qiu Y, Kingsford C. The effect of genome graph expressiveness on the discrepancy between genome graph distance and string set distance. Bioinformatics. 2022;38:404\u201312.","journal-title":"Bioinformatics"},{"issue":"2","key":"262_CR14","doi-asserted-by":"publisher","first-page":"99","DOI":"10.1023\/A:1026543900054","volume":"40","author":"Y Rubner","year":"2000","unstructured":"Rubner Y, Tomasi C, Guibas LJ. The Earth Mover\u2019s distance as a metric for image retrieval. Int J Comput Vision. 2000;40(2):99\u2013121.","journal-title":"Int J Comput Vision"},{"key":"262_CR15","doi-asserted-by":"publisher","DOI":"10.1201\/9780429493911","volume-title":"Elements of algebraic topology","author":"JR Munkres","year":"2018","unstructured":"Munkres JR. Elements of algebraic topology. Boca Raton: CRC Press; 2018."},{"key":"262_CR16","unstructured":"Bradley SP, Hax AC, Magnanti TL. Applied mathematical programming (1977)"},{"key":"262_CR17","doi-asserted-by":"crossref","unstructured":"Pele O, Werman M. A linear time histogram metric for improved sift matching. In: Computer Vision\u2013ECCV 2008: 10th European Conference on Computer Vision, Marseille, France, October 12-18, 2008, Proceedings, Part III 10, pp. 495\u2013508 (2008). Springer","DOI":"10.1007\/978-3-540-88690-7_37"},{"issue":"4","key":"262_CR18","doi-asserted-by":"publisher","first-page":"507","DOI":"10.1101\/gr.1975204","volume":"14","author":"G Bourque","year":"2004","unstructured":"Bourque G, Pevzner PA, Tesler G. Reconstructing the genomic architecture of ancestral mammals: lessons from human, mouse, and rat genomes. Genome Res. 2004;14(4):507\u201316.","journal-title":"Genome Res"},{"issue":"6588","key":"262_CR19","doi-asserted-by":"publisher","first-page":"6965","DOI":"10.1126\/science.abj6965","volume":"376","author":"MR Vollger","year":"2022","unstructured":"Vollger MR, Guitart X, Dishuck PC, Mercuri L, Harvey WT, Gershman A, Diekhans M, Sulovari A, Munson KM, Lewis AP, et al. Segmental duplications and their variation in a complete human genome. Science. 2022;376(6588):6965.","journal-title":"Science"},{"key":"262_CR20","unstructured":"Gurobi Optimization, LLC: Gurobi Optimizer Reference Manual (2023). https:\/\/www.gurobi.com"},{"issue":"6","key":"262_CR21","doi-asserted-by":"publisher","first-page":"595","DOI":"10.1101\/pdb.top115","volume":"2011","author":"M-P Lefranc","year":"2011","unstructured":"Lefranc M-P. IMGT, the international ImMunoGeneTics information system. Cold Spring Harbor Protocols. 2011;2011(6):595\u2013603.","journal-title":"Cold Spring Harbor Protocols"},{"issue":"7793","key":"262_CR22","doi-asserted-by":"publisher","first-page":"112","DOI":"10.1038\/s41586-019-1913-9","volume":"578","author":"Y Li","year":"2020","unstructured":"Li Y, Roberts ND, Wala JA, Shapira O, Schumacher SE, Kumar K, Khurana E, Waszak S, Korbel JO, Haber JE, et al. Patterns of somatic structural variation in human cancer genomes. Nature. 2020;578(7793):112\u201321.","journal-title":"Nature"},{"issue":"3","key":"262_CR23","doi-asserted-by":"publisher","first-page":"370","DOI":"10.1101\/gr.7010208","volume":"18","author":"E Darai-Ramqvist","year":"2008","unstructured":"Darai-Ramqvist E, Sandlund A, M\u00fcller S, Klein G, Imreh S, Kost-Alimova M. Segmental duplications and evolutionary plasticity at tumor chromosome break-prone regions. Genome Res. 2008;18(3):370\u20139.","journal-title":"Genome Res"},{"key":"262_CR24","volume-title":"Network flows: theory, algorithms and applications","author":"RK Ahujia","year":"1993","unstructured":"Ahujia RK, Magnanti TL, Orlin JB. Network flows: theory, algorithms and applications. New Jersey: Prentice-Hall; 1993."},{"issue":"4","key":"262_CR25","doi-asserted-by":"publisher","first-page":"1026","DOI":"10.1137\/100800245","volume":"40","author":"TK Dey","year":"2011","unstructured":"Dey TK, Hirani AN, Krishnamoorthy B. Optimal homologous cycles, total unimodularity, and linear programming. SIAM J Comput. 2011;40(4):1026\u201344.","journal-title":"SIAM J Comput"},{"key":"262_CR26","volume-title":"Theory of linear and integer programming","author":"A Schrijver","year":"1998","unstructured":"Schrijver A. Theory of linear and integer programming. Hoboken: Wiley; 1998."}],"container-title":["Algorithms for Molecular Biology"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1186\/s13015-024-00262-6.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1186\/s13015-024-00262-6\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1186\/s13015-024-00262-6.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,4,29]],"date-time":"2024-04-29T03:10:59Z","timestamp":1714360259000},"score":1,"resource":{"primary":{"URL":"https:\/\/almob.biomedcentral.com\/articles\/10.1186\/s13015-024-00262-6"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2024,4,29]]},"references-count":26,"journal-issue":{"issue":"1","published-online":{"date-parts":[[2024,12]]}},"alternative-id":["262"],"URL":"https:\/\/doi.org\/10.1186\/s13015-024-00262-6","relation":{},"ISSN":["1748-7188"],"issn-type":[{"value":"1748-7188","type":"electronic"}],"subject":[],"published":{"date-parts":[[2024,4,29]]},"assertion":[{"value":"21 October 2023","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"21 March 2024","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"29 April 2024","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}},{"order":1,"name":"Ethics","group":{"name":"EthicsHeading","label":"Declarations"}},{"value":"Not applicable.","order":2,"name":"Ethics","group":{"name":"EthicsHeading","label":"Ethics approval and consent to participate"}},{"value":"Not applicable.","order":3,"name":"Ethics","group":{"name":"EthicsHeading","label":"Consent for publication"}},{"value":"C.K. is a co-founder of Ocean Genomics, Inc.","order":4,"name":"Ethics","group":{"name":"EthicsHeading","label":"Competing interests"}}],"article-number":"17"}}