Path: utzoo!utgpu!news-server.csri.toronto.edu!rpi!usc!sdd.hp.com!spool.mu.edu!news.cs.indiana.edu!msi.umn.edu!cs.umn.edu!talon.UCS.ORST.EDU!usenet!
From: holloway@bionette.cgrb.orst.edu (Jim Holloway - CS)
Newsgroups: bionet.general
Subject: Re: Representing DNA/RNA with formal grammars
Keywords: formal grammars, DNA/RNA representation
Message-ID: <1991Apr05.174621.13708@lynx.CS.ORST.EDU>
Date: 5 Apr 91 17:46:21 GMT
Sender: @lynx.CS.ORST.EDU
Organization: Oregon State University, Corvallis
Lines: 59
Nntp-Posting-Host: bionette.cgrb.orst.edu


Brian Butler asks:

> Recently, I came across some references to this.  However, they were 1988 and
>  1987 and I was wondering whether anyone knew of more recent references.
>
> bb26@andrew.cmu.edu

I assume that the 1987 and 1988 articles were by T. Head and D. B. Searls.
There have been a couple of references to the paper by Tom Head. One of them
is a paper in the International Journal of Computer Mathematics, volume 31,
page 63 (1989) that I have not seen yet -- It may be useful.

@string{bmb = "Bulletin of Mathematical Biology"}

@article{Denninghoff1,
author = "K. L. Denninghoff and R. W. Gatterdam",
title = "On the undecidability of splicing systems",
journal = "International Journal of Computer Mathematics",
volume = 27,
pages = "133--145",
year = 1989,
comment = "``In this paper the concept of a sequential splicing system is
introduced. A sequential splicing system differs from a splicing system in
that the latter allows arbitrarily many copies of any string in the initial
set whereas the sequential splicing system may restrict the initial number
of copies of some strings. The main result is that there exist sequential
splicing systems with recursively unsolvable membership problem. The
technique of the proof is to embed Truing machine computations in the
languages.''"}

@article{Head1,
author = "T. Head",
title = "Formal language theory and {DNA}: An analysis of the generative capacity of specific recombinant behaviors",
journal = bmb,
volume = 49,
pages = "737--759",
year = 1987,
comment = "DNA is represented as a language over a four symbol alphabet. The
actions of enzymes is represented as a set of operations on the strings over
the four symbol alphabet. The closure of the original set of strings under the
set of operations is analyzed using formal language theory. Two useful
results are enumerating the possible DNA molecules that can be formed under
specific conditions and secondly ``The relationships between or among the
transforming activities made possible by different enzymes or combinations
of enzymes may be made precise or at least conceptually clarified.''"}

@inproceedings{Searls1,
author = "D. B. Searls",
title = "Representing Genetic Information with Formal Grammars",
booktitle = "Proceedings of the AAAI 88",
pages = "386--391",
year = 1988,
comment = "``This paper will first introduce the notion of applying general
grammars to some simple DNA features, then discuss the linguistic power
required for DNA, and then further elaborate a biological example along with an
actual implementation and sample run.''"}

--Jim