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

Fukagawa D, Tamura T, Takasu A, Tomita E, Akutsu T - BMC Bioinformatics (2011)

Bottom Line: The result suggests that our proposed method can efficiently compute the edit distance for moderate size unordered trees.The proposed method is simple but useful for computation of the edit distance between unordered trees.The object code is available upon request.

View Article: PubMed Central - HTML - PubMed

Affiliation: Faculty of Culture and Information Science, Doshisha University, Kyoto 610-0394, Japan. dfukagaw@mail.doshisha.ac.jp

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.

Show MeSH

Related in: MedlinePlus

Example of tree edit operations and edit distance mapping under the unit cost model. T2 is obtained from T1 by deletion of node (labeled with) e, insertion of node k and substitution of node f. The corresponding mapping M is shown by broken curves.
© Copyright Policy - open-access
Related In: Results  -  Collection

License
getmorefigures.php?uid=PMC3044267&req=5

Figure 1: Example of tree edit operations and edit distance mapping under the unit cost model. T2 is obtained from T1 by deletion of node (labeled with) e, insertion of node k and substitution of node f. The corresponding mapping M is shown by broken curves.

Mentions: Here, we briefly review tree edit distance and edit distance mapping (see also Figure 1) for rooted, labelled and unordered trees [12,15,16].


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

Fukagawa D, Tamura T, Takasu A, Tomita E, Akutsu T - BMC Bioinformatics (2011)

Example of tree edit operations and edit distance mapping under the unit cost model. T2 is obtained from T1 by deletion of node (labeled with) e, insertion of node k and substitution of node f. The corresponding mapping M is shown by broken curves.
© Copyright Policy - open-access
Related In: Results  -  Collection

License
Show All Figures
getmorefigures.php?uid=PMC3044267&req=5

Figure 1: Example of tree edit operations and edit distance mapping under the unit cost model. T2 is obtained from T1 by deletion of node (labeled with) e, insertion of node k and substitution of node f. The corresponding mapping M is shown by broken curves.
Mentions: Here, we briefly review tree edit distance and edit distance mapping (see also Figure 1) for rooted, labelled and unordered trees [12,15,16].

Bottom Line: The result suggests that our proposed method can efficiently compute the edit distance for moderate size unordered trees.The proposed method is simple but useful for computation of the edit distance between unordered trees.The object code is available upon request.

View Article: PubMed Central - HTML - PubMed

Affiliation: Faculty of Culture and Information Science, Doshisha University, Kyoto 610-0394, Japan. dfukagaw@mail.doshisha.ac.jp

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.

Show MeSH
Related in: MedlinePlus