Abstract
Given a finite set K of lethal genes, a starting genome x and a desired target genome y, is there a sequence of base insertions, deletions, and substitutions, which from x produces the desired genome y, and such that no intermediate genome contains a lethal gene. The main result of this paper is that, appropriately formulated, this problem is undecidable, even when the underlying alphabet has only 2 symbols (e.g. two of the bases A,C,G,T). We prove that asexual evolutionary systems form a universal computation engine, in the sense that for any reversible Turing machine M and input x, there is a finite set K of lethal genes, which can guide the computation, so that all intermediate genomes are prefixes of (encodings of) configurations in the computation of M. Since reversible Turing machines retain the history of their entire computation, and axe essentially encoded by evolutionary systems, this suggests a encoding mechanism by which phylogeny recapitulates ontogeny.
Research supported by NSF CCR-9408090 and US-Czech Science and Technology Grant 93-205.
This is a preview of subscription content, log in via an institution to check access.
Preview
Unable to display preview. Download preview PDF.
References
L. Adleman. Molecular computation of solutions to combinatorial problems. Science, 266:1021–1024, 1994.
S. Arora, Y. Rabani, and U. Vazirani. Simulating quadratic dynamical systems is PSPACE-complete (preliminary version). In Proceedings of the 26th Annual ACM Symposium on Theory of Computing, pages 459–467, 1994.
C.H. Bennett. Time/space trade-offs for reversible computation. SIAM Journal on Computing, 18:766–776, 1989.
V. Chvátal and D. Sankoff. Longest common subsequences of two random sequences. Journal of Applied Probability, 12:306–315, 1975.
J. Dassow and V. Mitrana. Evolutionary grammars: a grammatical model for genome evolution. In Computer Science and Biology, pages pp. 87–92, 1996. Proceedings of the German Conference on Bioinformatics (GCB'96).
L. Ilie and V. Mitrana. Crossing-over on languages: A formal representation of the recombination of genes in a chromosome. Technical Report 16, Turku Centre for Computer Science, June 1996.
Lila Kari and Gabriel Thierrin. Contextual insertion/deletions and computability. Information and Computation, 131(1):47–61, 1996.
L.Kari, G.Paun, G.Thierrin, and S.Yu. At the crossroads of DNA computing and formal languages: Characterizing recursively enumerable languages by insertion-deletion systems. In Proceedings of the 3 rd DIMACS Workshop on DNA-based Computers, pages 318–333, Philadelphia, June 1997.
S. Yu. Maslov. The mutation calculi. Journal of Soviet Mathematics, 10:495–517, 1978.
S. Yu. Maslov. Absorption relation on regular sets. Journal of Soviet Mathematics, 14:1468–1475, 1980.
S. Yu. Maslov. Theory of Deductive Systems and its Applications. MIT Press (Cambridge), 1987.
G. Paun and A. Salomaa. From DNA recombination to DNA computing, via formal languages. In Computer Science and Biology, pages pp. 93–98, 1996. Proceedings of the German Conference on Bioinformatics (GCB'96).
P. Pudlák. Complexity theory and genetics. In Proceedings of 9th Annual IEEE Conference on Structure in Complexity Theory, 1994.
M. S. Waterman. Introduction to Computational Biology — Maps, sequences and genomes. Chapman and Hall, 1995.
Author information
Authors and Affiliations
Editor information
Rights and permissions
Copyright information
© 1998 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Backofen, R., Clote, P. (1998). Evolution as a computational engine. In: Nielsen, M., Thomas, W. (eds) Computer Science Logic. CSL 1997. Lecture Notes in Computer Science, vol 1414. Springer, Berlin, Heidelberg. https://doi.org/10.1007/BFb0028006
Download citation
DOI: https://doi.org/10.1007/BFb0028006
Published:
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-64570-2
Online ISBN: 978-3-540-69353-6
eBook Packages: Springer Book Archive