Graph Traversal Edit Distance and Extensions.

Area of Science:

• Machine learning
• Graph theory
• Bioinformatics

Background:

• Machine learning frequently encounters graph-structured data across diverse fields.
• Graph kernels are crucial for learning algorithms operating on these geometric spaces.
• Existing methods lack efficient solutions for certain graph comparison problems.

Purpose of the Study:

• To introduce a new graph kernel, the Graph Traversal Edit Distance (GTED).
• To develop the first polynomial-time algorithm for GTED.
• To provide a mathematical framework for sequence co-assembly and variation detection in bioinformatics.

Main Methods:

• Developed a polynomial-time algorithm for GTED using linear programming in the graph product space.
• Introduced a linear programming relaxation for GTED lower bounds.
• Evaluated GTED as a graph kernel with Support Vector Machine (SVM) classifiers.

Main Results:

• The GTED algorithm guarantees an integer solution.
• GTED demonstrated superior performance compared to common graph kernels on benchmark datasets.
• Successfully clustered viral genomes using GTED on assembly graphs from next-generation sequencing data.

Conclusions:

• GTED is a novel and effective graph kernel with broad applicability.
• The developed algorithm provides an efficient solution for GTED.
• GTED shows significant promise in bioinformatics, particularly for genome analysis and clustering.