A method for comparing unordered trees in bioinformatics
Author Information
Author(s): Fukagawa Daiji, Tamura Takeyuki, Takasu Atsuhiro, Tomita Etsuji, Akutsu Tatsuya
Primary Institution: Doshisha University
Hypothesis
Can a practical method be developed to compute the edit distance between unordered trees using maximum clique algorithms?
Conclusion
The proposed method efficiently computes the edit distance for moderate size unordered trees and is comparable in accuracy to existing methods.
Supporting Evidence
- The proposed method can efficiently compute the edit distance for moderate size unordered trees.
- The accuracy of the proposed method is comparable to that of existing methods for glycan search.
- The method is the first practical approach for computing unordered tree edit distance with general editing cost functions.
Takeaway
This study created a new way to compare tree-like data, which helps scientists understand complex biological structures better.
Methodology
The method transforms the edit distance problem for unordered trees into a maximum clique problem and applies efficient solvers for the maximum clique.
Limitations
The method may not be useful for comparison of non-similar trees and relies on the identity of node labels.
Digital Object Identifier (DOI)
Want to read the original?
Access the complete publication on the publisher's website