Without loss of generality, we assume thati1 ikforch(i) = (i1, ,ik)

Without loss of generality, we assume thati1 ikforch(i) = (i1, ,ik).We suppose that the root ofT(V, E) is 1. EUTG for given strings, ordered and unordered trees. Our proposed methods for trees are useful for extracting patterns of glycan tree structures. == Background == Data compression is useful because it can help reduce the consumption of expensive resources such as hard disks. To date, many methods such as Huffman coding, arithmetic coding, etc. have been proposed to solve problems of data compression. Data compression is also useful for the analysis of biological data. Li et al. proposed the universal similarity metric (USM), and approximated the dissimilarity using compression sizes. They applied a compression algorithm to unaligned mitochondrial genomes, and obtained a phylogeny that was consistent with the generally accepted one [1]. Similarly, protein tertiary structures and metabolic networks were compressed, and their similarities were measured [2,3]. Grammar-based compression, which is a typical data-compression method, seeks a small grammar to generate a given string, as it is well known that it is NP-hard to find the smallest context-free grammar (CFG). However, in recent years, several polynomial time algorithms have been proposed to approximate the smallest grammar for the input data within a factor ofO(log(n/m)), wherenandmare the sizes of the BIIB021 input data and the smallest grammar [4-6], respectively. These algorithms can be used to compress biological data such as DNA, RNA, and amino acid sequences. However, there exist a large amount of tree-structured biological data (e.g., glycan, etc.). Therefore, it is necessary to develop methods to compress tree-structured data. Recent approaches show that it is feasible Rabbit Polyclonal to CSE1L to extend the grammar-based compression to the tree-structure data [7-9]. However, these methods neither output the minimum grammar, nor they accomplish a guaranteed approximation ratio. In this paper, we propose an integer programming (IP)-based method that finds the minimum 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 lengthen this method to find the minimum elementary ordered-tree grammar (EOTG) and elementary unordered-tree grammar (EUTG) for given ordered and unordered trees. To the best of our knowledge, these are the first methods that can find the minimum size grammars for strings, ordered trees, and unordered trees. It is possible to compress ordered trees by transforming them into Euler strings [10], and by applying existing grammar-based string-compression algorithms to the strings. Such an approach may accomplish better compression performances. However, there do not usually exist tree grammars corresponding to string grammars derived by the approach. Our objective is not only to compress trees but also to extract features and patterns from input BIIB021 trees. Therefore, we need to develop methods for obtaining minimum tree grammars. The organization of the paper is as follows. First, we give an IP-based method for sequence data compression using CFG. Second, we review anelementary ordered tree grammar(EOTG) [10] for ordered rooted tree compression, and lengthen this IP-based method to the tree compression problem. Then, we also review anelementary unordered tree grammar(EUTG) [10] for unordered rooted tree compression, and lengthen the above mentioned IP-based method for unordered trees. Furthermore, we conduct some computational experiments, apply the proposed methods to glycan tree-structure data, and extract tree patterns from generated production rules of simple EUTGs. Finally, we conclude with future BIIB021 work. == IP BIIB021 formulation for strings == == Minimum CFG problem == We use a simple context-free grammar (CFG) for string and text compression. CFG is usually defined as 4-tuple (, ,S, ), where is usually a set of terminal symbols (denoted by a lower-case letter), is usually a set of nonterminal symbols (denoted by an upper-case letter),Sis.