License: 
Creative Commons Attribution 4.0 International license (CC BY 4.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.WABI.2023.11
URN: urn:nbn:de:0030-drops-186374
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2023/18637/
Qiu, Yutong ;
Shen, Yihang ;
Kingsford, Carl
Revisiting the Complexity of and Algorithms for the Graph Traversal Edit Distance and Its Variants
Abstract
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 will always yield optimal integer solutions. The claim that GTED is polynomially solvable is contradictory to the complexity 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 that estimate GTED efficiently.
BibTeX - Entry
@InProceedings{qiu_et_al:LIPIcs.WABI.2023.11,
author = {Qiu, Yutong and Shen, Yihang and Kingsford, Carl},
title = {{Revisiting the Complexity of and Algorithms for the Graph Traversal Edit Distance and Its Variants}},
booktitle = {23rd International Workshop on Algorithms in Bioinformatics (WABI 2023)},
pages = {11:1--11:22},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-294-5},
ISSN = {1868-8969},
year = {2023},
volume = {273},
editor = {Belazzougui, Djamal and Ouangraoua, A\"{i}da},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/opus/volltexte/2023/18637},
URN = {urn:nbn:de:0030-drops-186374},
doi = {10.4230/LIPIcs.WABI.2023.11},
annote = {Keywords: Integer Linear Programming, Genome Graphs, Flow Network, Graph Comparison}
}
