DNA Computing | springerprofessional.de

Springer Professional

nach oben

1998 | Buch

Kapitel lesen Erstes Kapitel lesen

DNA Computing

New Computing Paradigms

verfasst von: Prof. Dr. Gheorghe Păun, Prof. Dr. Grzegorz Rozenberg, Prof. Dr. Arto Salomaa

Verlag: Springer Berlin Heidelberg

Buchreihe : Texts in Theoretical Computer Science An EATCS Series

Enthalten in: Professional Book Archive

Einloggen, um Zugang zu erhalten

Anzeige

Inhaltsverzeichnis

Frontmatter

Introduction: DNA Computing in a Nutshell

Introduction: DNA Computing in a Nutshell

Abstract

From silicon to carbon. From microchips to DNA molecules. This is the basic idea in DNA computing. Information-processing capabilities of organic molecules can be used in computers to replace digital switching primitives.

Gheorghe Păun, Grzegorz Rozenberg, Arto Salomaa

Background and Motivation

Frontmatter

Chapter 1. DNA: Its Structure and Processing

Abstract

The term “genetic engineering” is a very broad generic term used to cover all kinds of manipulations of genetic material. For the purpose of this book this term describes the in vitro (hence outside living cell) manipulation of DNA and related molecules. These manipulations may be used to perform various kinds of computations.

Gheorghe Păun, Grzegorz Rozenberg, Arto Salomaa

Chapter 2. Beginnings of Molecular Computing

Abstract

“We can see only a short distance ahead, but we can see plenty there that needs to be done.” These words of Turing [213] can be taken as an underlying principle of any program for scientific development. Such an underlying principle is very characteristic for research programs in computer science. Advances in computer science are often shown by and remembered from some unexpected demonstration, rather than from a dramatic experiment as in physical sciences. As pointed out by Hartmanis [83], it is the role of such a demo to show the possibility or feasibility of doing what was previously thought to be impossible or not feasible. Often, the ideas and concepts brought about and tested in such demos determine or at least influence the research agenda in computer science. Adleman’s experiment [1] constituted such a demo. This book is about the short distance we can see ahead, and about the theoretical work already done concerning various aspects of molecular computing. The ultimate impact of DNA computing cannot yet be seen; this matter will be further discussed in Sect. 2.4.

Gheorghe Păun, Grzegorz Rozenberg, Arto Salomaa

Mathematical Theory

Frontmatter

Chapter 3. Introduction to Formal Language Theory

Abstract

The mathematical theory of DNA computing presented in Part II of this book is developed in the framework of formal language theory. As we have seen in Chap. 1, DNA molecules have a natural representation through “double” strings satisfying certain assumptions (Watson-Crick complementarity and opposite directionality). Also, various enzymatic operations on DNA molecules can be naturally represented as operations on (double) strings. Consequently, using DNA molecules and their manipulation for the purpose of DNA computing can be conveniently and naturally expressed in the framework of (double) strings and operations on them. This leads to formal language theory as a natural framework for formalizing and investigating DNA computing.

Gheorghe Păun, Grzegorz Rozenberg, Arto Salomaa

Chapter 4. Sticker Systems

Abstract

Data structures basic in language theory are words,that is, strings of elements, letters. Here the idea of a “string” entails a linear order among the elements. The double helix of DNA, when presented in two dimensions as we have already done, constitutes a data structure of a new kind: a double strand. While both strands still are linear strings of elements, the double strand possesses an important additional property. The paired elements in the strands are complementary with respect to a given symmetric relation. We have already discussed the interconnection between this Watson—Crick complementarity and the twin-shuffle language The computational capacity of the latter has also been pointed out. In the next two chapters intensive use will be made of these two facts, the interconnection and computational capacity, for DNA computing. Our previous characterizations of recursively enumerable languages, based on equality sets and twin-shuffle languages, find here very natural applications.

Gheorghe Păun, Grzegorz Rozenberg, Arto Salomaa

Chapter 5. Watson—Crick Automata

Abstract

In this chapter we investigate the automata counterpart of the sticker systems studied in the previous chapter. We consider a new type of automata, working on tapes which are double stranded sequences of symbols related by a complementarity relation, similar to a DNA molecule (such a data structure is called a Watson-Crick tape). The automata scan separately each of the two strands, in a correlated manner. They can also have a finite number of states controlling the moves and/or they can have an auxiliary memory which is also a Watson—Crick tape, used in a FIFO-like manner Combining such possibilities we obtain several types of automata. In most cases, these automata augmented with squeezing mechanisms, such as weak codings and deterministic sequential transducers, characterize the recursively enumerable languages.

Gheorghe Păun, Grzegorz Rozenberg, Arto Salomaa

Chapter 6. Insertion-Deletion Systems

Abstract

In this chapter we consider computing models based on two operations which were already considered in formal language theory, mainly with motivation from linguistics. These operations — insertion and deletion, with context dependence — can also be encountered in the genetic area and they can be performed, at least theoretically, in the following ways.

Gheorghe Păun, Grzegorz Rozenberg, Arto Salomaa

Chapter 7. Splicing Systems

Abstract

Starting with this chapter we investigate computability models based on the splicing operation, a formal model of the recombinant behavior of DNA molecules under the influence of restriction enzymes and ligases. Informally speaking, splicing two strings means to cut them at points specified by given substrings (corresponding to the patterns recognized by restriction enzymes) and to concatenate the obtained fragments crosswise (this corresponds to a ligation reaction).

Gheorghe Păun, Grzegorz Rozenberg, Arto Salomaa

Chapter 8. Universality by Finite H Systems

Abstract

As we have seen in the previous chapter, extended H systems with finite sets of axioms and splicing rules are able to generate only regular languages. As we are looking for generative (computability) models having the power of Turing machines, we have to consider features that can increase the power of H systems. This has been successfully done for Chomsky grammars and other generative mechanisms in the regulated rewriting area and the grammar systems area. Following suggestions from these areas, as well as suggestions offered by the proof of the Basic Universality Lemma (Lemma 7.16), in this chapter we shall consider a series of controlled H systems with finite components which characterize the recursively enumerable languages, hence are computationally complete. From the proofs, we shall also obtain universal computing devices, hence models of “programmable DNA computers based on splicing”.

Gheorghe Păun, Grzegorz Rozenberg, Arto Salomaa

Chapter 9. Splicing Circular Strings

Abstract

In certain circumstances — in several bacteria, for instance — the DNA molecules are present in the form of a circular sequence. More generally, we can consider situations where both linear and circular DNA sequences are present. The restriction enzymes can cut both the linear and the circular double stranded sequences, hence recombination by ligation can also appear in such a case. Many variants are possible, because a recombination can have as input two circular strings, or one circular and one linear string, and can have as output one or two circular strings, one or two linear strings, or both a circular and a linear string.

Gheorghe Păun, Grzegorz Rozenberg, Arto Salomaa

Chapter 10. Distributed H Systems

Abstract

One of the important drawbacks of the models considered in the previous chapters is the fact that we need several splicing rules. Each rule corresponds to two restriction enzymes. However, each enzyme needs specific temperature, acidity, salinity, and other reaction conditions. This means that, in general, from using a splicing rule to using another one we have to change these reaction conditions. This operation dramatically decreases the efficiency of the computation (in terms of duration), hence should be avoided as much as possible.

Gheorghe Păun, Grzegorz Rozenberg, Arto Salomaa

Chapter 11. Splicing Revisited

Abstract

Besides the variants of the splicing operation discussed in the previous chapters (especially in Chap. 8) and of the generative mechanisms based on them, several others were already investigated in the literature, mainly from a mathematical point of view, without directing the research toward (universal) computability models. In this chapter we present some of these variants, as a challenge to the reader for building further computability models.

Gheorghe Păun, Grzegorz Rozenberg, Arto Salomaa

Backmatter

Titel: DNA Computing
verfasst von: Prof. Dr. Gheorghe Păun
Prof. Dr. Grzegorz Rozenberg
Prof. Dr. Arto Salomaa
Copyright-Jahr: 1998
Verlag: Springer Berlin Heidelberg
Electronic ISBN: 978-3-662-03563-4
Print ISBN: 978-3-642-08388-4
DOI: https://doi.org/10.1007/978-3-662-03563-4