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

Integer Programming Methods for Tree Compression and Glycan Pattern Extraction

publication Evidence: moderate

Author Information

Author(s): Zhao Yang, Hayashida Morihiro, Akutsu Tatsuya

Primary Institution: Bioinformatics Center, Institute for Chemical Research, Kyoto University

Hypothesis

Can integer programming methods effectively find minimum grammars for tree-structured data?

Conclusion

The proposed integer programming methods are effective for finding minimum grammars for strings, ordered trees, and unordered trees, and are useful for extracting patterns from glycan tree structures.

Supporting Evidence

  • The methods were tested on artificial data and glycan tree-structure data.
  • The proposed methods showed better compression ratios compared to existing methods.
  • Computational experiments confirmed the correctness and efficiency of the proposed methods.

Takeaway

This study created new methods to compress tree data and find patterns in glycan structures, which are important for understanding biological processes.

Methodology

The study used integer programming to find minimum context-free grammars for strings and tree structures, and applied these methods to glycan data.

Limitations

The methods may require improvements for unordered trees and do not address cycles in structured data.

Digital Object Identifier (DOI)

10.1186/1471-2105-11-S11-S4

Want to read the original?

Access the complete publication on the publisher's website

View Original Publication