Searching for Compact Hierarchical Structures in DNA by means of the Smallest Grammar Problem
Matthias Gallé · HAL (Le Centre pour la Communication Scientifique Directe) · 2011
Motivated by the goal of discovering hierarchical structures inside DNA sequences, we address the Smallest Grammar Problem, the problem of finding a smallest context-free grammar that generates exactly one sequence. This NP-Hard problem has been widely studied for applications like Data Compression, Structure Discovery and Algorithmic Information Theory. We give a new formalisation of this problem in form of a complete and correct search space. This search space is based on the decomposition of the problem into two complementary optimisation problems. The first one consists in choosing which substrings of the sequence will become the constituents of the final grammar. The second problem is concerned with how to combine these substrings in an optimal way. We called this the "Minimal Grammar Parsing" problem and give a polynomial solution for it. Thanks to this decomposition, we are able to define new algorithms that outperform the state-of-the-art one by 10% regarding the final grammar size. We are particularly interested in the feasibility of these algorithms. For this, we analyse the impact of using different maximality classes of repeats and the tradeoff between efficiency and final grammar size. We also present algorithmic improvements for existing off-line algorithms, which include a careful in-place update of an enhanced suffix array. Regarding the applications, we consider the impact of the non-uniqueness of smallest grammars on Structure Discovery. We prove that the number of smallest grammars can be exponential in the size of the sequence and then analyse the stability of the discovered structures between minimal grammars for real-life examples. With respect to Data Compression, we divide a grammar-based compressor into three different steps and consider each of them separately. We then define a new algorithm that optimises the size of the final bitstream instead of the size of the grammar. Applying it on DNA sequences show that this algorithm outperforms any other DNA specific grammar-based compressor. We improve over this result by using inexact repeats, namely rigid patterns and achieve compression rate up to 25% better compared to the previous best DNA grammar-based coder. Besides obtaining better compression rate, this approach also permits to envisages interesting continuations of this work to generalise the resulting grammars.