A clique-based method for the edit distance between unordered trees and its application to analysis of glycan structures
2011

A method for comparing unordered trees in bioinformatics

publication Evidence: moderate

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)

10.1186/1471-2105-12-S1-S13

Want to read the original?

Access the complete publication on the publisher's website

View Original Publication