Annals of Computer Science and Information Systems, Volume 11

DOI: http://dx.doi.org/10.15439/2017F73

Citation: Proceedings of the 2017 Federated Conference on Computer Science and Information Systems, M. Ganzha, L. Maciaszek, M. Paprzycki (eds). ACSIS, Vol. 11, pages 433–440 (2017)

Full text

Abstract. In this paper, we formulate an anchored alignment distance between rooted labeled unordered trees as the minimum cost of the anchored alignment whose anchoring is constructed from the minimum cost isolated-subtree mapping by adding the pairs of non-mapped leaves, and design the algorithm to compute it. Whereas this algorithm runs in exponential time with respect to the number of leaves in theoretical, we give experimental results to compute the anchored alignment distance efficiently in experimental and to compare the anchored alignment distance, with the alignment distance and the isolated-subtree distance.

References

1. P. Ferraro, C. Godin: Optimal mappings with minimum number of connected components in tree-to-tree comparison problems, J. Algo. 48, 385–406, 2003. http://dx.doi.org/10.1016/S0196-6774(03)00079-8.
2. K. Hirata, Y. Yamamoto, T. Kuboyama: Improved MAX SNP-hard results for finding an edit distance between unordered trees, Proc. CPM 2011, LNCS 6661, 402–415, 2011. http://dx.doi.org/10.1007/978-3-642-21458-5 34.
3. Y. Ishizaka, T. Yoshino, K. Hirata: Anchored alignment problem for rooted labeled trees, New Frontiers in Artificial Intelligence, LNAI 9067, 296–309, 2015. DOI 10.1007/978-3-662-48119-6 22.
4. T. Jiang, L. Wang, K. Zhang: Alignment of trees – an alternative to tree edit, Theoret. Comput. Sci. 143, 137–148, 1995. http://dx.doi.org/10.1016/0304-3975(95)80029-9.
5. KEGG: Kyoto Encyclopedia of Genes and Genomes, http://www.kegg.jp/.
6. T. Kuboyama: Matching and learning in trees, Ph.D thesis, University of Tokyo, 2007.
7. C. L. Lu, Z.-Y. Su, C. Y. Yang: A new measure of edit distance between labeled trees, Proc. COCOON’01, LNCS 2108, 338–348, 2001. http://dx.doi.org/10.1007/3-540-44679-6 37.
8. S. Luke, L. Panait: A survey and comparison of tree generation algorithms, Proc. GECCO’01, 81–88, 2001.
9. T. Mori, T. Tamura, D. Fukagawa, A. Takasu, E. Tomita, T. Akutsu: A clique-based method using dynamic programming for computing edit distance between unordered trees, J. Comput. Bio. 19, 1089–1104, 2012. http://dx.doi.org/10.1089/cmb.2012.0133.
10. S. Schiermer, R. Giegerich: Forest alignment with affine gaps and anchors, applied in RNA structure comparison, Theoret. Comput. Sci. 483, 51–67, 2013. http://dx.doi.org/10.1016/j.tcs.2012.07.040.
11. K.-C. Tai: The tree-to-tree correction problem, J. ACM 26, 422–433, 1979. http://dx.doi.org/10.1145/322139.322143.
12. J. T. L. Wang, K. Zhang: Finding similar consensus between trees: An algorithm and a distance hierarchy, Pattern Recog. 34, 127–137, 2001. http://dx.doi.org/10.1016/S0031-3203(99)00199-5.
13. Y. Yamamoto, K, Hirata, T. Kuboyama: Tractable and intractable variations of unordered tree edit distance, Internat. J. Found. Comput. Sci. 25, 307–329, 2014. http://dx.doi.org/10.1142/S0129054114500154.
14. T. Yoshino, S. Higuchi, K. Hirata: A dynamic programming A∗ algorithm for computing unordered tree edit distance, Proc. IIAI AAI ’13, 135–140, 2013. http://dx.doi.org/10.1109/IIAI-AAI.2013.71.
15. T. Yoshino, K. Hirata: Tai mapping hierarchy for rooted labeled trees through common subforest, Theory of Comput. Sys. 60, 759–783, 2017. http://dx.doi.org/10.1007/s00224-016-9705-1.
16. K. Zhang: Algorithms for the constrained editing distance between ordered labeled trees and related problems, Pattern Recog. 28, 463–474, 1995. http://dx.doi.org/10.1016/0031-3203(94)00109-Y.
17. K. Zhang: A constrained edit distance between unordered labeled trees, Algorithmica 15, 205-222, 1996. http://dx.doi.org/10.1007/BF01975866.
18. K. Zhang, T. Jiang: Some MAX SNP-hard results concerning unordered labeled trees, Inform. Process. Lett. 49, 249–254, 1994. http://dx.doi.org/10.1016/0020-0190(94)90062-0.