Integer Programming Methods for Tree Compression and Glycan Pattern Extraction
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)
Want to read the original?
Access the complete publication on the publisher's website