title: A clique-based method for the edit distance between unordered trees and its application to analysis of glycan structures.
abstract: BACKGROUND
  Measuring similarities between tree structured data is important for analysis of RNA secondary structures, phylogenetic trees, glycan structures, and vascular trees. The edit distance is one of the most widely used measures for comparison of tree structured data. However, it is known that computation of the edit distance for rooted unordered trees is NP-hard. Furthermore, there is almost no available software tool that can compute the exact edit distance for unordered trees.
  
  
  RESULTS
  In this paper, we present a practical method for computing the edit distance between rooted unordered trees. In this method, the edit distance problem for unordered trees is transformed into the maximum clique problem and then efficient solvers for the maximum clique problem are applied. We applied the proposed method to similar structure search for glycan structures. The result suggests that our proposed method can efficiently compute the edit distance for moderate size unordered trees. It also suggests that the proposed method has the accuracy comparative to those by the edit distance for ordered trees and by an existing method for glycan search.
  
  
  CONCLUSIONS
  The proposed method is simple but useful for computation of the edit distance between unordered trees. The object code is available upon request.
authors.affiliation: Faculty of Culture and Information Science, Doshisha University, Kyoto 610-0394, Japan. dfukagaw@mail.doshisha.ac.jp
authors.forename: Daiji
authors.initials: D
authors.lastname: Fukagawa
authors.forename: Takeyuki
authors.initials: T
authors.lastname: Tamura
authors.forename: Atsuhiro
authors.initials: A
authors.lastname: Takasu
authors.forename: Etsuji
authors.initials: E
authors.lastname: Tomita
authors.forename: Tatsuya
authors.initials: T
authors.lastname: Akutsu
mesh_terms: D000465:Algorithms; D019295:Computational Biology / Q000379:methods*; D011134:Polysaccharides / Q000032:analysis*; D012984:Software
chemical_list: D011134:Polysaccharides