检索结果-内蒙古大学图书馆

grammar-based compression approach to extraction of common rules among multiple trees of glycans and RNAs

BMC BIOINFORMATICS 2015年第1期16卷 1-13页

作者： Zhao, Yang Hayashida, Morihiro Cao, Yue Hwang, Jaewook Akutsu, Tatsuya Kyoto Univ Inst Chem Res Bioinformat Ctr Uji Kyoto Japan

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.

关键词： grammar-based compression Bisection-type tree grammar Glycan RNA secondary structure

来源：评论

学校读者我要写书评

暂无评论

Approximation of grammar-based compression via recompression

引用

THEORETICAL COMPUTER SCIENCE 2015年 592卷 115-134页

作者： Jez, Artur Univ Wroclaw Inst Comp Sci PL-50383 Wroclaw Poland

In this paper we present a simple linear-time algorithm constructing a context-free grammar of size O(glog(N/g)) for the input string, where N is the size of the input string and g the size of the optimal grammar generating this string. The algorithm works for arbitrary size alphabets, but the running time is linear assuming that the alphabet Sigma of the input string can be identified with numbers from (1,..., N-C) for some constant c. Otherwise, additional cost of O(N log vertical bar Sigma vertical bar) is needed. Algorithms with such an approximation guarantee and running time are known, the novelty of this paper is a particular simplicity of the algorithm as well as the analysis of the algorithm, which uses a general technique of recompression recently introduced by the author. Furthermore, contrary to the previous results, this work does not use the LZ representation of the input string in the construction, nor in the analysis. (C) 2015 Elsevier B.V. All rights reserved.

关键词： grammar-based compression Construction of the smallest grammar SLP compression

来源：评论

学校读者我要写书评

暂无评论

Scalable Detection of Frequent Substrings by grammar-based compression

引用

IEICE TRANSACTIONS ON INFORMATION AND SYSTEMS 2013年第3期E96D卷 457-464页

作者： Nakahara, Masaya Maruyama, Shirou Kuboyama, Tetsuji Sakamoto, Hiroshi Kyushu Inst Technol Iizuka Fukuoka 8208502 Japan Kyushu Univ Fukuoka 8190395 Japan Gakushuin Univ Tokyo 1718588 Japan JST PRESTO Kawaguchi Saitama 3320012 Japan

A scalable pattern discovery by compression is proposed. A string is representable by a context-free grammar deriving the string deterministically. In this framework of grammar-based compression, the aim of the algorithm is to output as small a grammar as possible. Beyond that, the optimization problem is approximately solvable. In such approximation algorithms, the compressor based on edit-sensitive parsing (ESP) is especially suitable for detecting maximal common substrings as well as long frequent substrings. based on ESP, we design a linear time algorithm to find all frequent patterns in a string approximately and prove several lower bounds to guarantee the length of extracted patterns. We also examine the performance of our algorithm by experiments in biological sequences and other compressible real world texts. Compared to other practical algorithms, our algorithm is faster and more scalable with large and repetitive strings.

关键词： pattern discovery grammar-based compression edit-sensitive parsing

来源：评论

学校读者我要写书评

暂无评论

A Space-Saving Approximation Algorithm for grammar-based compression

引用

IEICE TRANSACTIONS ON INFORMATION AND SYSTEMS 2009年第2期E92D卷 158-165页

作者： Sakamoto, Hiroshi Maruyama, Shirou Kida, Takuya Shimozono, Shinichi Kyushu Inst Technol Fac Comp Sci & Syst Engn Iizuka Fukuoka 8208502 Japan Kyushu Univ Dept Informat Fukuoka 8190395 Japan Hokkaido Univ Grad Sch Informat Sci & Technol Sapporo Hokkaido 0600814 Japan

A space-efficient approximation algorithm for the grammar-based compression problem, which requests for a given string to find a smallest context-free grammar deriving the string, is presented. For the input length it and an optimum CFG size g, the algorithm consumes only O(g log g) space and O(n log*n) time to achieve O((log*n) log n) approximation ratio to the optimum compression, where log*n is the maximum number of logarithms satisfying log log...log n > 1. This ratio is thus regarded to almost O(log n), which is the currently best approximation ratio. While g depends on the string, it is known that g = Omega(log n) and g = O(n/log(k)n) for strings from k-letter alphabet [12].

关键词： grammar-based compression approximation algorithm minimum CFG problem

来源：评论

学校读者我要写书评

暂无评论

Self-Indexed grammar-based compression

引用

FUNDAMENTA INFORMATICAE 2011年第3期111卷 313-337页

作者： Claude, Francisco Navarro, Gonzalo Univ Waterloo David R Cheriton Sch Comp Sci Waterloo ON N2L 3G1 Canada Univ Chile Dept Comp Sci Santiago Chile

Self-indexes aim at representing text collections in a compressed format that allows extracting arbitrary portions and also offers indexed searching on the collection. Current self-indexes are unable of fully exploiting the redundancy of highly repetitive text collections that arise in several applications. grammar-based compression is well suited to exploit such repetitiveness. We introduce the first grammar-based self-index. It builds on Straight-Line Programs (SLPs), a rather general kind of context-free grammars. If an SLP of n rules represents a text T [1, u], then an SLP-compressed representation of T requires 2n log(2) n bits. For that same SLP, our self-index takes O(n log n) + n log(2) u bits. It extracts any text substring of length m in time O ((m + h) log n), and finds occ occurrences of a pattern string of length m in time O ((m (m + h) + h occ) log n), where h is the height of the parse tree of the SLP. No previous grammar representation had achieved o(n) search time. As byproducts we introduce (i) a representation of SLPs that takes 2n log(2) n (1 + o(1)) bits and efficiently supports more operations than a plain array of rules;(ii) a representation for binary relations with labels supporting various extended queries;(iii) a generalization of our self-index to grammar compressors that reduce T to a sequence of terminals and nonterminals, such as Re-Pair and LZ78.

关键词： grammar-based compression Straight-Line Programs Self-Indexes Compressed Text Databases Highly Repetitive Sequences Pattern Matching Data Structures

来源：评论

学校读者我要写书评

暂无评论

An Online Algorithm for Lightweight grammar-based compression

引用

ALGORITHMS 2012年第2期5卷 214-235页

作者： Maruyama, Shirou Sakamoto, Hiroshi Takeda, Masayuki Kyushu Univ Dept Informat Nishi Ku 744 Motooka Fukuoka Fukuoka Japan Kyushu Inst Technol 680-4 Kawazu Iizuka Fukuoka Japan

grammar-based compression is a well-studied technique to construct a context-free grammar (CFG) deriving a given text uniquely. In this work, we propose an online algorithm for grammar-based compression. Our algorithm guarantees O (log(2) n) approximation ratio for the minimum grammar size, where n is an input size, and it runs in input linear time and output linear space. In addition, we propose a practical encoding, which transforms a restricted CFG into a more compact representation. Experimental results by comparison with standard compressors demonstrate that our algorithm is especially effective for highly repetitive text.

关键词： lossless compression grammar-based compression online algorithm approximation algorithm

来源：评论

学校读者我要写书评

暂无评论

Universal Tree Source Coding Using grammar-based compression

引用

IEEE TRANSACTIONS ON INFORMATION THEORY 2019年第10期65卷 6399-6413页

作者： Ganardi, Moses Hucke, Danny Lohrey, Markus Benkner, Louisa Seelbach Univ Siegen Dept Elect Engn & Comp Sci D-57076 Siegen Germany

The problem of universal source coding for binary trees is considered. Zhang, Yang, and Kieffer derived upper bounds on the average-case redundancy of codes based on directed acyclic graph (DAG) compression for binary tree sources with certain properties. In this paper, a natural class of binary tree sources is presented such that the demanded properties are fulfilled. Moreover, for both subclasses considered in the paper of Zhang, Yang, and Kieffer, their result is improved by deriving bounds on the maximal pointwise redundancy (or worst-case redundancy) instead of the average-case redundancy. Finally, using context-free tree grammars instead of DAGs, upper bounds on the maximal pointwise redundancy for certain binary tree sources are derived. This yields universal codes for new classes of binary tree sources.

关键词： grammar-based compression minimal DAG representation binary trees universal source coding lossless compression

来源：评论

学校读者我要写书评

暂无评论

Approximation of grammar-based compression via Recompression

Approximation of Grammar-Based Compression via Recompression

引用

24th Annual Symposium on Combinatorial Pattern Matching (CPM)

作者： Jez, Artur Max Planck Inst Informat DE-66123 Saarbrucken Germany

ISBN: (纸本)9783642389054;9783642389047

We present a simple linear-time algorithm constructing a context-free grammar of size O(g log(N/g)) for the input string of size N, where g the size of the optimal grammar generating this string. The algorithm works for arbitrary size alphabets, but the running time is linear assuming that the alphabet S of the input string is a subset of {1, ... , N-c} for some constant c. Algorithms with such an approximation guarantees and running time are known, the novelty of this paper is the particular simplicity of the algorithm as well as the analysis of the algorithm, which uses a general technique of recompression recently introduced by the author. Furthermore, contrary to the previous results, this work does not use the LZ representation of the input string in the construction, nor in the analysis.

关键词： grammar-based compression Construction of the smallest grammar SLP

来源：评论

学校读者我要写书评

暂无评论

Universal Tree Source Coding Using grammar-based compression

Universal Tree Source Coding Using Grammar-Based Compression

引用

IEEE International Symposium on Information Theory (ISIT)

作者： Ganardi, Moses Hucke, Danny Lohrey, Markus Benkner, Louisa Seelbach Univ Siegen Dept Elect Engn & Comp Sci D-57076 Siegen Germany

关键词： grammar-based compression minimal DAG representation binary trees universal source coding lossless compression

来源：评论

学校读者我要写书评

暂无评论

Measuring the Similarity of Proteomes using grammar-based compression via Domain Combinations 11

Measuring the Similarity of Proteomes using Grammar-based Co...

引用

13th International Joint Conference on Biomedical Engineering Systems and Technologies

作者： Hayashida, Morihiro Koyano, Hitoshi Nacher, Jose C. Matsue Coll Natl Inst Technol Dept Elect Engn & Comp Sci Matsue Shimane Japan Tokyo Inst Technol Sch Life Sci & Technol Meguro Ku Tokyo Japan Toho Univ Fac Sci Dept Informat Sci Funabashi Chiba Japan

ISBN: (纸本)9789897583988

Revealing evolution of organisms is one of important biological research topics, and is also useful for understanding the origin of organisms. Hence, genomic sequences have been compared and aligned for finding conserved and functional regions. A protein can contain several domains, which are known as structural and functional units. In the previous work, a proteome, whole kinds of proteins in an organism, was regarded as a set of sequences of protein domains, and a grammar-based compression algorithm was developed for a proteome, where production rules in the grammar represented evolutionary processes, mutation and duplication. In this paper, we propose a similarity measure based on the grammar-based compression, and apply it to hierarchical clustering of seven organisms, Homo sapiens. Mus musculus, Drosophila melanogaster, Caenorhabditis elegans. Sacchammyces cerevisiae. Arabidopsis thaliana. and Escherichia coli. The results suggest that our similarity measure could classify the organisms very well.

关键词： grammar-based compression Kolmogorov Complexity Protein Domain Combination

来源：评论

学校读者我要写书评

暂无评论

建议与咨询留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

建议与咨询 留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案： 新增检索档案 确定 取消

请选择收藏分类： 新增自定义分类 确定 取消

通借通还

建议与咨询留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

请选择保存的检索档案：

请选择收藏分类：