Tree structures are suitable for representing biological objects such as RNA secondary structures so that it is important in computational biology to compare tree structures. Though there are various metrics proposed for computing similarity between tree structured data, tree edit distance is one of the most widely used. However, it is known that the tree edit distance problem is NP-hard for unordered trees. Fukagawa et al. have recently proposed a clique-based method for computing the tree edit distance between unordered trees in which each instance of the tree edit distance problem is tra...