PyGTED: Python Application for Computing Graph Traversal Edit Distance.

Area of Science:

• Computational biology
• Machine learning
• Graph theory

Background:

• Graph-based data is prevalent in diverse fields like bioinformatics, social networks, and web data mining.
• Measuring graph dissimilarity is crucial for various machine learning applications, including graph kernels.
• Existing methods may not fully capture the nuances of graph structure for specific bioinformatics tasks.

Purpose of the Study:

• To introduce Graph Traversal Edit Distance (GTED) as a novel measure of dissimilarity between graphs.
• To provide the first mathematical formalism for sequence coassembly and de novo variation detection using graph distances.
• To present PyGTED, a computational tool for calculating GTED.

Main Methods:

• GTED is computed by finding the minimum edit distance between strings derived from Eulerian traversals of graphs.
• The implementation leverages a polynomial-time algorithm for efficient GTED computation.
• The PyGTED tool facilitates the practical application of the GTED algorithm.

Main Results:

• GTED provides a formal mathematical framework for comparing graphs based on their traversal paths.
• The PyGTED tool enables efficient and accurate calculation of GTED.
• The method is particularly relevant for sequence coassembly and variation detection in bioinformatics.

Conclusions:

• GTED offers a powerful new metric for graph comparison, with significant implications for bioinformatics and machine learning.
• The PyGTED tool democratizes the use of GTED for researchers.
• This work advances the application of graph kernels and related machine learning techniques.