Open AccessPyGTED: Python Application for Computing Graph Traversal Edit Distance
Author(s) -
Ali Ebrahimpour Boroojeny,
Akash Shrestha,
Ali Sharifi-Zarchi,
Suzanne Renick Gallagher,
S. Cenk Şahinalp,
Hamidreza Chitsaz
Publication year - 2020
Publication title -
journal of computational biology
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.585
H-Index - 95
eISSN - 1557-8666
pISSN - 1066-5277
DOI - 10.1089/cmb.2019.0510
Subject(s) - edit distance , graph traversal , eulerian path , computer science , python (programming language) , tree traversal , theoretical computer science , graph kernel , algorithm , artificial intelligence , mathematics , kernel method , polynomial kernel , programming language , lagrangian , support vector machine , mathematical physics
Graph Traversal Edit Distance (GTED) is a measure of distance (or dissimilarity) between two graphs introduced. This measure is based on the minimum edit distance between two strings formed by the edge labels of respective Eulerian traversals of the two graphs. GTED was motivated by and provides the first mathematical formalism for sequence coassembly and de novo variation detection in bioinformatics. Many problems in applied machine learning deal with graphs (also called networks), including social networks, security, web data mining, protein function prediction, and genome informatics. The kernel paradigm beautifully decouples the learning algorithm from the underlying geometric space, which renders graph kernels important for the aforementioned applications. In this article, we introduce a tool, PyGTED to compute GTED. It implements the algorithm based on the polynomial time algorithm devised for it by the authors. Informally, the GTED is the minimum edit distance between two strings formed by the edge labels of respective Eulerian traversals of the two graphs.