Searching for smallest grammars on large sequences and application to DNA

DOI10.1016/j.jda.2011.04.006zbMath1237.68265OpenAlexW2060610818MaRDI QIDQ414452

Gabriel Infante-Lopez, Rafael Carrascosa, Matthias Gallé, François Coste

Publication date: 11 May 2012

Published in: Journal of Discrete Algorithms (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.jda.2011.04.006

zbMATH Keywords

linguistics of DNAmaximal repeatssmallest grammar problemstructural inference

Mathematics Subject Classification ID

Protein sequences, DNA sequences (92D20) Grammars and rewriting systems (68Q42) Algorithms on strings (68W32)

Related Items (3)

Learning the Language of Biological Sequences ⋮ \(xkcd\)-repeats: a new taxonomy of repeats defined by their context diversity ⋮ On the complexity of the smallest grammar problem over fixed alphabets

Cites Work

• Unnamed Item
• Unnamed Item
• Replacing suffix trees with enhanced suffix arrays
• A new challenge for compression algorithms: Genetic sequences
• Application of Lempel-Ziv factorization to the approximation of grammar-based compression.
• Linear-time text compression by longest-first substitution
• Data structures and algorithms for the string statistics problem
• The Smallest Grammar Problem
• Choosing Word Occurrences for the Smallest Grammar Problem
• IN-PLACE UPDATE OF SUFFIX ARRAY WHILE RECODING WORDS
• Algorithms on Strings, Trees and Sequences
• Grammar-based codes: a new class of universal lossless source codes

This page was built for publication: Searching for smallest grammars on large sequences and application to DNA