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

A clique-based method for the edit distance between unordered trees and its application to analysis of glycan structures,10.1186/1471-2105-12-S1-S13,B

A clique-based method for the edit distance between unordered trees and its application to analysis of glycan structures   (Citations: 1)
BibTex | RIS | RefWorks Download
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.
Journal: BMC Bioinformatics , vol. 12, no. Suppl 1, pp. S13-9, 2011
Cumulative Annual
View Publication
The following links allow you to view full publications. These links are maintained by other sources not affiliated with Microsoft Academic Search.
    • ...We recently proposed a practical method for computing the tree edit distance between unordered trees [10] using algorithms for computing the maximum clique [11], [12]...
    • ...The method was applied to comparison and search of similar glycan structures and shown to be efficient for moderate size tree structures [10]...
    • ...Different from our previous method [10], the improved method is basically a dynamic programming algorithm that repeatedly solves instances of the maximum vertex weighted clique problem as sub-problems...
    • ...Before presenting our improved clique-based method, we briefly review our previous clique-based method [10] (see also Fig. 2), which is referred as CliqueEdit in this paper...
    • ...[2], it seems that CliqueEdit has similar efficiency [10] to the �� ∗ -algorithm for unordered tree edit distance [2]...
    • ...In this paper, we focus only on the computational efficiency and do not conduct computational experiments for evaluating the performance (i.e., accuracy of comparison) of CliqueEdit and DpCliqueEdit because these two methods compute the same distances and the performance of CliqueEdit was already evaluated in our previous work [10]...
    • ...As in our previous work [10], we randomly selected 100 pairs of glycan structures with a specified range of the total number of nodes (i.e., the sum of the numbers of nodes in �� 1 and �� 2) and measured the average CPU time (user time) per pair...

    Tatsuya Akutsuet al. An Improved Clique-Based Method for Computing Edit Distance between Un...

Sort by: