{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,7,9]],"date-time":"2026-07-09T22:22:35Z","timestamp":1783635755774,"version":"3.55.0"},"reference-count":23,"publisher":"Springer Science and Business Media LLC","issue":"1","license":[{"start":{"date-parts":[[2015,4,24]],"date-time":"2015-04-24T00:00:00Z","timestamp":1429833600000},"content-version":"unspecified","delay-in-days":0,"URL":"http:\/\/creativecommons.org\/licenses\/by\/4.0"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["BMC Bioinformatics"],"published-print":{"date-parts":[[2015,12]]},"DOI":"10.1186\/s12859-015-0558-4","type":"journal-article","created":{"date-parts":[[2015,4,23]],"date-time":"2015-04-23T19:27:54Z","timestamp":1429817274000},"update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":3,"title":["Grammar-based compression approach to extraction of common rules among multiple trees of glycans and RNAs"],"prefix":"10.1186","volume":"16","author":[{"given":"Yang","family":"Zhao","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Morihiro","family":"Hayashida","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Yue","family":"Cao","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Jaewook","family":"Hwang","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Tatsuya","family":"Akutsu","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"297","published-online":{"date-parts":[[2015,4,24]]},"reference":[{"key":"558_CR1","doi-asserted-by":"publisher","first-page":"929","DOI":"10.1042\/bj3260929u","volume":"326","author":"JA Campbell","year":"1997","unstructured":"Campbell JA, Davies GJ, Bulone V, Henrissat B. A classification of nucleotide-diphospho-sugar glycosyltransferases based on amino acid sequence similarities. Biochem J. 1997; 326:929\u201342.","journal-title":"Biochem J."},{"key":"558_CR2","doi-asserted-by":"publisher","first-page":"2270","DOI":"10.1016\/j.carres.2005.07.012","volume":"340","author":"Y Hizukuri","year":"2005","unstructured":"Hizukuri Y, Yamanishi Y, Nakamura O, Yagi F, Goto S, Kanehisa M. Extraction of leukemia specific glycan motifs in humans by computational glycomics. Carbohydr Res. 2005; 340:2270\u201378.","journal-title":"Carbohydr Res."},{"key":"558_CR3","doi-asserted-by":"publisher","first-page":"25","DOI":"10.1093\/bioinformatics\/btl244","volume":"22","author":"KF Aoki-Kinoshita","year":"2006","unstructured":"Aoki-Kinoshita KF, Ueda N, Mamitsuka H, Kanehisa M. ProfilePSTMM: capturing tree-structure motifs in carbohydrate sugar chains. Bioinformatics. 2006; 22:25\u201334.","journal-title":"Bioinformatics"},{"key":"558_CR4","doi-asserted-by":"publisher","first-page":"167","DOI":"10.1093\/bioinformatics\/btn293","volume":"24","author":"K Hashimoto","year":"2008","unstructured":"Hashimoto K, Takigawa I, Shiga M, Kanehisa M, Mamitsuka H. Mining significant tree patterns in carbohydrate sugar chains. Bioinformatics. 2008; 24:167\u201373.","journal-title":"Bioinformatics"},{"issue":"Suppl 1","key":"558_CR5","doi-asserted-by":"publisher","first-page":"S33","DOI":"10.1186\/1471-2105-11-S1-S33","volume":"11","author":"L Li","year":"2010","unstructured":"Li L, Ching W-K, Yamaguchi T, Aoki-Kinoshita KF. A weighted q-gram method for glycan structure classification. BMC Bioinformatics. 2010; 11(Suppl 1):S33.","journal-title":"BMC Bioinformatics"},{"issue":"Suppl 1","key":"558_CR6","doi-asserted-by":"publisher","first-page":"S13","DOI":"10.1186\/1471-2105-12-S1-S13","volume":"12","author":"D Fukagawa","year":"2011","unstructured":"Fukagawa D, Tamura T, Takasu A, Tomita E, Akutsu T. A clique-based method for the edit distance between unordered trees and its application to analysis of glycan structures. BMC Bioinformatics. 2011; 12(Suppl 1):S13.","journal-title":"BMC Bioinformatics"},{"key":"558_CR7","doi-asserted-by":"publisher","first-page":"13","DOI":"10.1186\/1748-7188-8-13","volume":"8","author":"N Milo","year":"2013","unstructured":"Milo N, Zakov S, Katzenelson E, Bachmat E, Dinitz Y, Ziv-Ukelson M. Unrooted unordered homeomorphic subtree alignment of rna trees. Algorithms Mol Biol. 2013; 8:13.","journal-title":"Algorithms Mol Biol."},{"key":"558_CR8","doi-asserted-by":"publisher","first-page":"778","DOI":"10.1007\/s10878-012-9552-1","volume":"27","author":"S Chen","year":"2014","unstructured":"Chen S, Zhang K. An improved algorithm for tree edit distance with applications for rna secondary structure comparison. J Comb Optimization. 2014; 27:778\u201397.","journal-title":"J Comb Optimization."},{"key":"558_CR9","doi-asserted-by":"publisher","first-page":"314","DOI":"10.1111\/j.1365-313X.2011.04688.x","volume":"68","author":"A Farid","year":"2011","unstructured":"Farid A, Pabst M, Schoberer J, Altmann F, Gl\u00f6ssl J, Strasser R. Arabidopsis thaliana alpha1,2-glucosyltransferase (ALG10) is required for efficient N-glycosylation and leaf growth. Plant J. 2011; 68:314\u201325.","journal-title":"Plant J."},{"key":"558_CR10","doi-asserted-by":"publisher","first-page":"2554","DOI":"10.1109\/TIT.2005.850116","volume":"51","author":"M Charikar","year":"2005","unstructured":"Charikar M, Lehman E, Liu D, Panigrahy R, Prabhakaran M, Sahai A, et al.The smallest grammar problem. IEEE Trans Inf Theory. 2005; 51:2554\u201376.","journal-title":"IEEE Trans Inf Theory"},{"key":"558_CR11","doi-asserted-by":"publisher","first-page":"211","DOI":"10.1016\/S0304-3975(02)00777-6","volume":"302","author":"W Rytter","year":"2003","unstructured":"Rytter W. Application of lempel-ziv factorization to the approximation of grammar-based compression. Theor Comput Sci. 2003; 302:211\u201322.","journal-title":"Theor Comput Sci."},{"key":"558_CR12","doi-asserted-by":"publisher","first-page":"158","DOI":"10.1587\/transinf.E92.D.158","volume":"92-D","author":"H Sakamoto","year":"2009","unstructured":"Sakamoto H, Maruyama S, Kida T, Shimozono S. A space-saving approximation algorithm for grammar-based compression. IEICE Trans Inf Syst. 2009; 92-D:158\u201365.","journal-title":"IEICE Trans Inf Syst."},{"key":"558_CR13","volume-title":"12th International Conference on Grammatical Inference","author":"J Scicluna","year":"2014","unstructured":"Scicluna J, de la Higuera C. Grammatical inference of some probabilistic context-free grammars from positive data using minimum satisfiability. In: 12th International Conference on Grammatical Inference. Brookline, MA: Microtome Publishing: 2014. p. 139\u201352."},{"key":"558_CR14","doi-asserted-by":"publisher","first-page":"456","DOI":"10.1016\/j.is.2008.01.004","volume":"33","author":"G Busatto","year":"2008","unstructured":"Busatto G, Lohrey M, Maneth S. Efficient memory representation of xml document trees. Inf Syst. 2008; 33:456\u201374.","journal-title":"Inf Syst."},{"key":"558_CR15","volume-title":"Proc. 11th Int. Conf. Discovery Science","author":"S Murakami","year":"2008","unstructured":"Murakami S, Doi K, Yamamoto A. Finding frequent patterns from compressed tree-structure data. In: Proc. 11th Int. Conf. Discovery Science. Berlin Heidelberg: Springer: 2008. p. 284\u201395."},{"key":"558_CR16","volume-title":"Proc. 13th Int. Inductive Logic Programming","author":"K Yamagata","year":"2003","unstructured":"Yamagata K, Uchida T, Shoudai T, Nakamura Y. An effective grammar-based compression algorithm for tree structured data. In: Proc. 13th Int. Inductive Logic Programming. Berlin Heidelberg: Springer: 2003. p. 383\u2013400."},{"key":"558_CR17","doi-asserted-by":"publisher","first-page":"815","DOI":"10.1016\/j.ipl.2010.07.004","volume":"110","author":"T Akutsu","year":"2010","unstructured":"Akutsu T. A bisection algorithm for grammar-based compression of ordered trees. Inf Process Lett. 2010; 110:815\u201320.","journal-title":"Inf Process Lett."},{"issue":"Suppl 11","key":"558_CR18","doi-asserted-by":"publisher","first-page":"4","DOI":"10.1186\/1471-2105-11-S11-S4","volume":"11","author":"Y Zhao","year":"2010","unstructured":"Zhao Y, Hayashida M, Akutsu T. Integer programming-based method for grammar-based tree compression and its application to pattern extraction of glycan tree structures. BMC Bioinformatics. 2010; 11(Suppl 11):4.","journal-title":"BMC Bioinformatics"},{"key":"558_CR19","volume-title":"Chapter 5: Context-Free Grammars and Languages. Introduction to Automata Theory, languages, and Computation 2nd edn","author":"JE Hopcroft","year":"2001","unstructured":"Hopcroft JE, Motwani R, Ullman JD. Chapter 5: Context-Free Grammars and Languages. Introduction to Automata Theory, languages, and Computation 2nd edn. Boston: Addison-Wesley; 2001, pp. 169\u2013218."},{"issue":"5","key":"558_CR20","doi-asserted-by":"publisher","first-page":"63","DOI":"10.1093\/glycob\/cwj010","volume":"16","author":"K Hashimoto","year":"2006","unstructured":"Hashimoto K, Goto S, Kawano S, Aoki-Kinoshita F, Ueda N, Hamajima M et al.Kegg as a glycome informatics resource. Glycobiology. 2006; 16(5):63\u201370.","journal-title":"Glycobiology"},{"key":"558_CR21","doi-asserted-by":"crossref","unstructured":"Burge SW, Daub J, Eberhardt R, Tate J, Barquist L, Nawrocki EP, et al.Rfam 11.0: 10 years of RNA families. 2012. doi:10.1093\/nar\/gks1005.","DOI":"10.1093\/nar\/gks1005"},{"key":"558_CR22","first-page":"387","volume":"4","author":"BA Shapiro","year":"1988","unstructured":"Shapiro BA. An algorithm for comparing multiple rna secondary structures. Comput Appl Biosci. 1988; 4:387\u201393.","journal-title":"Comput Appl Biosci."},{"key":"558_CR23","doi-asserted-by":"publisher","first-page":"53","DOI":"10.1109\/TCBB.2004.11","volume":"1","author":"M H\u00f6chsmann","year":"2004","unstructured":"H\u00f6chsmann M, Voss B, Giegerich R. Pure multiple rna secondary structure alignments: a progressive profile approach. IEEE\/ACM Trans Comput Biol Bioinformatics. 2004; 1:53\u201362.","journal-title":"IEEE\/ACM Trans Comput Biol Bioinformatics"}],"container-title":["BMC Bioinformatics"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/article\/10.1186\/s12859-015-0558-4\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1186\/s12859-015-0558-4.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1186\/s12859-015-0558-4","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1186\/s12859-015-0558-4.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,9,2]],"date-time":"2021-09-02T11:56:41Z","timestamp":1630583801000},"score":1,"resource":{"primary":{"URL":"https:\/\/bmcbioinformatics.biomedcentral.com\/articles\/10.1186\/s12859-015-0558-4"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2015,4,24]]},"references-count":23,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2015,12]]}},"alternative-id":["558"],"URL":"https:\/\/doi.org\/10.1186\/s12859-015-0558-4","relation":{},"ISSN":["1471-2105"],"issn-type":[{"value":"1471-2105","type":"electronic"}],"subject":[],"published":{"date-parts":[[2015,4,24]]},"assertion":[{"value":"26 December 2014","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"30 March 2015","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"24 April 2015","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}],"article-number":"128"}}