Integer programming-based method for grammar-based tree compression and its application to pattern extraction of glycan tree structures

摘要：

Background: A bisection-type algorithm for the grammar-based compression of tree-structured data has been proposed recently. In this framework, an elementary ordered-tree grammar (EOTG) and an elementary unorderedtree grammar (EUTG) were defined, and an approximation algorithm was proposed. Results: In this paper, we propose an integer programming-based method that finds the minimum context-free grammar (CFG ) for a given string under the condition that at most two symbols appear on the right-hand side of each production rule. Next, we extend this method to find the minimum EOTG and EUTG grammars for given ordered and unordered trees, respectively. Then, we conduct computational experiments for the ordered and unordered artificial trees. Finally, we apply our methods to pattern extraction of glycan tree structures. Conclusions: We propose integer programming-based methods that find the minimum CFG, EOTG, and EUTG for given strings, ordered and unordered trees. Our proposed methods for trees are useful for extracting patterns of glycan tree structures.

作者: Yang Zhao Morihiro Hayashida Tatsuya Akutsu

作者单位: Bioinformatics Center, Institute for Chemical Research, Kyoto University,Gokasho, Uji, Kyoto, 611-00 Bioinformatics Center, Institute for Chemical Research, Kyoto University, Gokasho, Uji, Kyoto, 611-0

会议类型: 国际会议

会议名称: 第二十一届国际基因组信息学大会

会议地点: 上海

会议语种:英文

页码: 108-118

在线出版日期: 2010-12-06（万方平台首次上网日期，不代表论文的发表时间）