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

BMC Bioinformatics

Research

Morihiro Hayashida¹  Tatsuya Akutsu¹  Yang Zhao¹ 

[1] Bioinformatics Center, Institute for Chemical Research, Kyoto University, 611-0011, Gokasho, Uji, Kyoto, Japan;

关键词: Integer Programming;    Production Rule;    Sibling Relationship;    Integer Programming Formulation;    Terminal Symbol;   

DOI  :  10.1186/1471-2105-11-S11-S4

来源: Springer

【 摘 要 】

BackgroundA 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 unordered-tree grammar (EUTG) were defined, and an approximation algorithm was proposed.ResultsIn 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.ConclusionsWe 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.

【 授权许可】

CC BY   
© Akutsu et al; licensee BioMed Central Ltd. 2010