{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,12,2]],"date-time":"2025-12-02T15:20:04Z","timestamp":1764688804466},"reference-count":27,"publisher":"Springer Science and Business Media LLC","issue":"S1","content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["BMC Bioinformatics"],"published-print":{"date-parts":[[2011,12]]},"abstract":"<jats:title>Abstract<\/jats:title>\n          <jats:sec>\n            <jats:title>Background<\/jats:title>\n            <jats:p>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.<\/jats:p>\n          <\/jats:sec>\n          <jats:sec>\n            <jats:title>Results<\/jats:title>\n            <jats:p>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.<\/jats:p>\n          <\/jats:sec>\n          <jats:sec>\n            <jats:title>Conclusions<\/jats:title>\n            <jats:p>The proposed method is simple but useful for computation of the edit distance between unordered trees. The object code is available upon request.<\/jats:p>\n          <\/jats:sec>","DOI":"10.1186\/1471-2105-12-s1-s13","type":"journal-article","created":{"date-parts":[[2011,2,18]],"date-time":"2011-02-18T20:12:44Z","timestamp":1298059964000},"update-policy":"http:\/\/dx.doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":16,"title":["A clique-based method for the edit distance between unordered trees and its application to analysis of glycan structures"],"prefix":"10.1186","volume":"12","author":[{"given":"Daiji","family":"Fukagawa","sequence":"first","affiliation":[]},{"given":"Takeyuki","family":"Tamura","sequence":"additional","affiliation":[]},{"given":"Atsuhiro","family":"Takasu","sequence":"additional","affiliation":[]},{"given":"Etsuji","family":"Tomita","sequence":"additional","affiliation":[]},{"given":"Tatsuya","family":"Akutsu","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2011,2,15]]},"reference":[{"key":"4371_CR1","doi-asserted-by":"publisher","first-page":"371","DOI":"10.1089\/10665270252935511","volume":"9","author":"T Jiang","year":"2002","unstructured":"Jiang T, Lin G, Ma B, Zhang K: A general edit distance between RNA structures. J Comput Biol 2002, 9: 371\u2013388. 10.1089\/10665270252935511","journal-title":"J Comput Biol"},{"key":"4371_CR2","doi-asserted-by":"publisher","first-page":"111","DOI":"10.1016\/S0304-3975(01)00192-X","volume":"276","author":"B Ma","year":"2002","unstructured":"Ma B, Wang L, Zhang K: Computing similarity between RNA structures. Theoret Comp Sci 2002, 276: 111\u2013132. 10.1016\/S0304-3975(01)00192-X","journal-title":"Theoret Comp Sci"},{"key":"4371_CR3","doi-asserted-by":"publisher","first-page":"1165","DOI":"10.1089\/cmb.2006.13.1165","volume":"13","author":"T Horesh","year":"2006","unstructured":"Horesh T, Mehr R, Unger R: Designing an A* algorithm for calculating edit distance between rooted-unordered trees. J Comput Biol 2006, 13: 1165\u20131176. 10.1089\/cmb.2006.13.1165","journal-title":"J Comput Biol"},{"key":"4371_CR4","doi-asserted-by":"publisher","first-page":"293","DOI":"10.1007\/s00453-004-1147-5","volume":"43","author":"J Jansson","year":"2005","unstructured":"Jansson J, Ng JHK, Sadakane K, Sung WK: Rooted maximum agreement supertrees. Algorithmica 2005, 43: 293\u2013307. 10.1007\/s00453-004-1147-5","journal-title":"Algorithmica"},{"key":"4371_CR5","doi-asserted-by":"publisher","first-page":"55","DOI":"10.1109\/MC.2002.1016902","volume":"35","author":"BME Moret","year":"2002","unstructured":"Moret BME, Li-San Wang LS, Warnow T: Toward new software for computational phylogenetics. IEEE Computer 2002, 35: 55\u201364.","journal-title":"IEEE Computer"},{"key":"4371_CR6","doi-asserted-by":"publisher","first-page":"W267","DOI":"10.1093\/nar\/gkh473","volume":"32","author":"KF Aoki","year":"2004","unstructured":"Aoki KF, Yamaguchi A, Ueda N, Akutsu T, Mamitsuka H, Goto S, Kanehisa M: KCaM (KEGG Carbohydrate Matcher): a software tool for analyzing the structures of carbohydrate sugar chains. Nucleic Acids Res 2004, 32: W267-W272. 10.1093\/nar\/gkh473","journal-title":"Nucleic Acids Res"},{"key":"4371_CR7","doi-asserted-by":"publisher","first-page":"6","DOI":"10.1145\/1342320.1342326","volume":"2","author":"K Hashimoto","year":"2008","unstructured":"Hashimoto K, Aoki-Kinoshita KF, Ueda N, Kanehisa M, Mamitsuka H: A new efficient probabilistic model for mining labeled ordered trees applied to glycobiology. ACM Trans Knowledge Discovery from Data 2008, 2: 6.","journal-title":"ACM Trans Knowledge Discovery from Data"},{"key":"4371_CR8","first-page":"184","volume-title":"Proceedings of the 12th Pacific-Asia Conference on Know ledge Discovery and Data Mining (Lecture Notes in Computer Science, Vol. 5012)","author":"T Kuboyama","year":"2008","unstructured":"Kuboyama T, Hirata K, Aoki-Kinoshita KF: An efficient unordered tree kernel and its application to glycan classification. In Proceedings of the 12th Pacific-Asia Conference on Know ledge Discovery and Data Mining (Lecture Notes in Computer Science, Vol. 5012). Edited by: T W, E S, M TK, A I. Springer; 2008:184\u2013195."},{"key":"4371_CR9","doi-asserted-by":"publisher","first-page":"1211","DOI":"10.1093\/bioinformatics\/btm090","volume":"23","author":"Y Yamanishi","year":"2007","unstructured":"Yamanishi Y, Bach F, Vert JP: Glycan classification with tree kernels. Bioinformatics 2007, 23: 1211\u20131216. 10.1093\/bioinformatics\/btm090","journal-title":"Bioinformatics"},{"key":"4371_CR10","doi-asserted-by":"publisher","first-page":"469","DOI":"10.1016\/S0895-6111(03)00039-9","volume":"27","author":"Z Chen","year":"2003","unstructured":"Chen Z, Molloi S: Automatic 3D vascular tree construction in CT angiography. Comp Med Imaging and Graphics 2003, 27: 469\u2013479. 10.1016\/S0895-6111(03)00039-9","journal-title":"Comp Med Imaging and Graphics"},{"key":"4371_CR11","doi-asserted-by":"publisher","first-page":"1802","DOI":"10.1016\/j.compbiomed.2007.06.005","volume":"37","author":"KC Yu","year":"2007","unstructured":"Yu KC, Ritman EL, Higgns E: System for the analysis and visualization of large 3D anatomical trees. Comput in Biol and Med 2007, 37: 1802\u20131830. 10.1016\/j.compbiomed.2007.06.005","journal-title":"Comput in Biol and Med"},{"key":"4371_CR12","doi-asserted-by":"publisher","first-page":"217","DOI":"10.1016\/j.tcs.2004.12.030","volume":"337","author":"P Bille","year":"2005","unstructured":"Bille P: A survey on tree edit distance and related problem. Theoret Comput Sci 2005, 337: 217\u2013239. 10.1016\/j.tcs.2004.12.030","journal-title":"Theoret Comput Sci"},{"key":"4371_CR13","doi-asserted-by":"publisher","first-page":"422","DOI":"10.1145\/322139.322143","volume":"26","author":"KC Tai","year":"1979","unstructured":"Tai KC: The tree-to-tree correction problem. J ACM 1979, 26: 422\u2013433. 10.1145\/322139.322143","journal-title":"J ACM"},{"key":"4371_CR14","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1145\/1644015.1644017","volume":"6","author":"ED Demaine","year":"2009","unstructured":"Demaine ED, Mozes S, Rossman B, Weimann O: An optimal decomposition algorithm for tree edit distance. ACM Trans Alg 2009, 6: 1. 10.1145\/1644015.1644017","journal-title":"ACM Trans Alg"},{"key":"4371_CR15","doi-asserted-by":"publisher","first-page":"133","DOI":"10.1016\/0020-0190(92)90136-J","volume":"42","author":"K Zhang","year":"1992","unstructured":"Zhang K, Statman R, Shasha D: On the editing distance between unordered labeled trees. Inf Proc Lett 1992, 42: 133\u2013139. 10.1016\/0020-0190(92)90136-J","journal-title":"Inf Proc Lett"},{"key":"4371_CR16","doi-asserted-by":"publisher","first-page":"249","DOI":"10.1016\/0020-0190(94)90062-0","volume":"49","author":"K Zhang","year":"1994","unstructured":"Zhang K, Jiang T: Some MAX SNP-hard results concerning unordered labeled trees. Inf Proc Lett 1994, 49: 249\u2013254. 10.1016\/0020-0190(94)90062-0","journal-title":"Inf Proc Lett"},{"key":"4371_CR17","unstructured":"Akutsu T, Fukagawa D, Takasu A, Tamura T: Exact algorithms for computing tree edit distance between unordered trees. Theoret Comput Sci, in press."},{"key":"4371_CR18","doi-asserted-by":"publisher","first-page":"137","DOI":"10.1016\/0304-3975(95)80029-9","volume":"143","author":"T Jiang","year":"1995","unstructured":"Jiang T, Wang L, Zhang K: Alignment of trees - an alternative to tree edit. Theoret Comp Sci 1995, 143: 137\u2013148. 10.1016\/0304-3975(95)80015-8","journal-title":"Theoret Comp Sci"},{"key":"4371_CR19","doi-asserted-by":"publisher","first-page":"205","DOI":"10.1007\/BF01975866","volume":"15","author":"K Zhang","year":"1996","unstructured":"Zhang K: A constrained edit distance between unordered labeled trees. Algorithmica 1996, 15: 205\u2013222. 10.1007\/BF01975866","journal-title":"Algorithmica"},{"key":"4371_CR20","volume-title":"Technical Report of the University of Electro-Communications (in Japanese)","author":"T Nakamura","year":"2005","unstructured":"Nakamura T, Tomita E: Efficient algorithms for finding a maximum clique with maximum vertex weight. In Technical Report of the University of Electro-Communications (in Japanese). Tokyo; 2005."},{"key":"4371_CR21","doi-asserted-by":"publisher","first-page":"278","DOI":"10.1007\/3-540-45066-1_22","volume-title":"Proceedings of the 4th International Conference on Discrete Mathematics and Theoretical Computer Science (Lecture Notes in Computer Science, Vol. 2731)","author":"E Tomita","year":"2003","unstructured":"Tomita E, Seki T: An efficient branch-and-bound algorithm for finding a maximum clique. In Proceedings of the 4th International Conference on Discrete Mathematics and Theoretical Computer Science (Lecture Notes in Computer Science, Vol. 2731). Edited by: Calude C, Dinneen MJ, Vajnovszki V. Springer; 2003:278\u2013289."},{"key":"4371_CR22","first-page":"191","volume-title":"Proceedings of the 4th International Workshop on Algorithms and Computation (Lecture Notes in Computer Science, Vol. 5942)","author":"E Tomita","year":"2010","unstructured":"Tomita E, Sutani Y, Higashi T, Takahashi S, Wakatsuki M: A simple and faster branch-and-bound algorithm for finding a maximum clique. In Proceedings of the 4th International Workshop on Algorithms and Computation (Lecture Notes in Computer Science, Vol. 5942). Edited by: Rahman MS, Fujita S. Springer; 2010:191\u2013203."},{"key":"4371_CR23","unstructured":"Tomita E, Akutsu T, Matsunaga T: Efficient algorithms for finding maximum and maximal cliques - Effective tools for bioinformatics -. In Biomedical Engineering, Trends, Researches and Technologies. Vienna: INTECH.; in press."},{"key":"4371_CR24","doi-asserted-by":"publisher","first-page":"1105","DOI":"10.1109\/34.809105","volume":"21","author":"M Pelillo","year":"1999","unstructured":"Pelillo M, Siddiqi K, Zucker SW: Matching hierarchical structures using association graphs. IEEE Trans Patt Match Mach Intell 1999, 21: 1105\u20131119. 10.1109\/34.809105","journal-title":"IEEE Trans Patt Match Mach Intell"},{"key":"4371_CR25","doi-asserted-by":"publisher","first-page":"1089","DOI":"10.1016\/S0167-8655(02)00255-6","volume":"24","author":"A Torsello","year":"2003","unstructured":"Torsello A, Hancock ER: Computing approximate tree edit distance using relaxation labeling. Patt Recog Lett 2003, 24: 1089\u20131097. 10.1016\/S0167-8655(02)00255-6","journal-title":"Patt Recog Lett"},{"key":"4371_CR26","doi-asserted-by":"publisher","first-page":"D355","DOI":"10.1093\/nar\/gkp896","volume":"38","author":"M Kanehisa","year":"2010","unstructured":"Kanehisa M, Goto S, Furumichi M, Tanabe M, Hirakawa M: KEGG for representation and analysis of molecular networks involving diseases and drugs. Nucleic Acids Res 2010, 38: D355-D360. 10.1093\/nar\/gkp896","journal-title":"Nucleic Acids Res"},{"key":"4371_CR27","doi-asserted-by":"publisher","first-page":"25","DOI":"10.1016\/S0097-8485(96)80004-0","volume":"20","author":"M Gribskov","year":"1996","unstructured":"Gribskov M, Robinson NL: Use of receiver operating characteristic (ROC) analysis to evaluate sequence matching. Comput Chem 1996, 20: 25\u201333. 10.1016\/S0097-8485(96)80004-0","journal-title":"Comput Chem"}],"container-title":["BMC Bioinformatics"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1186\/1471-2105-12-S1-S13.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,9,1]],"date-time":"2021-09-01T14:00:39Z","timestamp":1630504839000},"score":1,"resource":{"primary":{"URL":"https:\/\/bmcbioinformatics.biomedcentral.com\/articles\/10.1186\/1471-2105-12-S1-S13"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2011,2,15]]},"references-count":27,"journal-issue":{"issue":"S1","published-print":{"date-parts":[[2011,12]]}},"alternative-id":["4371"],"URL":"https:\/\/doi.org\/10.1186\/1471-2105-12-s1-s13","relation":{},"ISSN":["1471-2105"],"issn-type":[{"value":"1471-2105","type":"electronic"}],"subject":[],"published":{"date-parts":[[2011,2,15]]},"assertion":[{"value":"15 February 2011","order":1,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}],"article-number":"S13"}}