Abstract
We introduce a grammatical model for the evolution of genomes on the basis of gene mutations and chromosome mutations and present some properties of such grammars. Few problems which might be biologically relevant are discussed from the computational point of view. On the other hand, the paper suggests a new direction in formal language theory motivated by the common operations of genome evolution.
Research supported by the Alexander von Humboldt Foundation
This is a preview of subscription content, log in via an institution to check access.
Preview
Unable to display preview. Download preview PDF.
Literature
V. Brendel and H. G. Busse, Genome structure described by formal languages, Nucleic Acids Res., 12 (1984), 2561–2568.
J. Collado-vides, The search for grammatical theory of gene regulations is formally justified by showing the inadequacy of context-free grammars, CABIOS, 7 (1991),321–326.
J. Dassow, Grammars with valuations — a discrete model for selforganization of biopolymers. Discrete Applied Math. 4 (1982) 161–174.
S. Karlin, E.S. Mocarski and G.A. Schachtel, Molecular evolution of herpesviruses: genomic and protein comparisons. J. of Virology 68 (1994) 1886–1902.
J.E. HOPCROFT and J.D. ULLMAN, Introduction to Automata Theory, Languages, and Computation. Addison-Wesley, 1979.
D.J. McGeoch, Molecular evolution of large DNA viruses of eukaryotes. Seminars in Virology 3 (1992) 399–408.
H. A. Maurer, A. Salomaa, D. Wood, Pure grammars, Information and Control, 44 (1980) 47–72.
G. ROZENBERG and A. SALOMAA, The Mathematical Theory of L Systems. Academic Press, 1980.
D. Sankoff et al., Gene order comparisons for phylogenetic inference: Evolution of the mitochondrial genome. Proc. Nall. Acad. Sci. USA 89 (1992) 6575–6579.
D. B. SEARLS, The computational linguistics of biological sequences. In Artificial Intelligence and Molecular Biology (L. HUNTER ed.), AAAI Press, The MIT Press, 1993, 47–120.
B. Shanon, The genetic code and human language, Synthese, 39 (1978), 401–415.
Author information
Authors and Affiliations
Editor information
Rights and permissions
Copyright information
© 1997 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Dassow, J., Mitrana, V. (1997). Evolutionary grammars: A grammatical model for genome evolution. In: Hofestädt, R., Lengauer, T., Löffler, M., Schomburg, D. (eds) Bioinformatics. GCB 1996. Lecture Notes in Computer Science, vol 1278. Springer, Berlin, Heidelberg. https://doi.org/10.1007/BFb0033218
Download citation
DOI: https://doi.org/10.1007/BFb0033218
Published:
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-63370-9
Online ISBN: 978-3-540-69524-0
eBook Packages: Springer Book Archive