Grammar-based Compression for Multiple Trees Using Integer Programming

• ZHAO YANG

  Bioinformatics Center, Institute for Chemical Research, Kyoto University

• HAYASHIDA MORIHIRO

  Bioinformatics Center, Institute for Chemical Research, Kyoto University

• CAO YUE

  Bioinformatics Center, Institute for Chemical Research, Kyoto University

• HWANG JAEWOOK

  Bioinformatics Center, Institute for Chemical Research, Kyoto University

• AKUTSU TATSUYA

  Bioinformatics Center, Institute for Chemical Research, Kyoto University

抄録

Many tree structures can be found in nature and organisms. It is considered that such trees are constructed by some rules. In our previous study, bisection-type grammar-based compression methods for ordered and unordered single trees have been developed. Here, these methods find construction rules for one tree. On the other hand, specified construction rules can be contributed to generate several similar trees. In this technical report, hence, we develop a method to find common rules generating multiple kinds of trees based on the previous method using integer programming. We apply our proposed method to several glycans that are one of important molecules in celluar systems and are regarded as tree structures. As a result, our method successfully found the minimum grammar and several common rules among these glycans.

収録刊行物

• 電子情報通信学会技術研究報告. IBISML, 情報論的学習理論と機械学習

  電子情報通信学会技術研究報告. IBISML, 情報論的学習理論と機械学習 114 (105), 163-164, 2014-06-18

  一般社団法人電子情報通信学会

詳細情報

• CRID: 1570291227930163200
• NII論文ID: 110009925777
• NII書誌ID: AA12482480
• 本文言語コード: en
• データソース種別:
  • CiNii Articles