title: Grammar-based compression approach to extraction of common rules among multiple trees of glycans and RNAs.
abstract: BACKGROUND
  Many tree structures are found in nature and organisms. Such trees are believed to be constructed on the basis of certain rules. We have previously developed grammar-based compression methods for ordered and unordered single trees, based on bisection-type tree grammars. Here, these methods find construction rules for one single tree. On the other hand, specified construction rules can be utilized to generate multiple similar trees.
  
  
  RESULTS
  Therefore, in this paper, we develop novel methods to discover common rules for the construction of multiple distinct trees, by improving and extending the previous methods using integer programming. We apply our proposed methods to several sets of glycans and RNA secondary structures, which play important roles in cellular systems, and can be regarded as tree structures. The results suggest that our method can be successfully applied to determining the minimum grammar and several common rules among glycans and RNAs.
  
  
  CONCLUSIONS
  We propose integer programming-based methods MinSEOTGMul and MinSEUTGMul for the determination of the minimum grammars constructing multiple ordered and unordered trees, respectively. The proposed methods can provide clues for the determination of hierarchical structures contained in tree-structured biological data, beyond the extraction of frequent patterns.
authors.affiliation: Bioinformatics Center, Institute for Chemical Research, Kyoto University, Gokasho, Uji, Japan. tyoyo@kuicr.kyoto-u.ac.jp.
authors.forename: Yang
authors.initials: Y
authors.lastname: Zhao
authors.affiliation: Bioinformatics Center, Institute for Chemical Research, Kyoto University, Gokasho, Uji, Japan. morihiro@kuicr.kyoto-u.ac.jp.
authors.forename: Morihiro
authors.initials: M
authors.lastname: Hayashida
authors.affiliation: Bioinformatics Center, Institute for Chemical Research, Kyoto University, Gokasho, Uji, Japan. caoyue@kuicr.kyoto-u.ac.jp.
authors.forename: Yue
authors.initials: Y
authors.lastname: Cao
authors.affiliation: Bioinformatics Center, Institute for Chemical Research, Kyoto University, Gokasho, Uji, Japan. hwangjw@kuicr.kyoto-u.ac.jp.
authors.forename: Jaewook
authors.initials: J
authors.lastname: Hwang
authors.affiliation: Bioinformatics Center, Institute for Chemical Research, Kyoto University, Gokasho, Uji, Japan. takutsu@kuicr.kyoto-u.ac.jp.
authors.forename: Tatsuya
authors.initials: T
authors.lastname: Akutsu
mesh_terms: D000465:Algorithms; D019295:Computational Biology / Q000379:methods; D044962:Data Compression / Q000379:methods*; D006801:Humans; D011134:Polysaccharides / Q000737:chemistry*; D012313:RNA / Q000737:chemistry*
chemical_list: D011134:Polysaccharides; D012313:RNA