The Construction of Minimal DNA Expressions

We describe a formal language/notation for DNA molecules that may contain nicks and gaps. The elements of the language, DNA expressions, denote formal DNA molecules. Different DNA expressions may denote the same formal DNA molecule. We analyse the shortest DNA expressions denoting a given formal DNA molecule. We determine lower bounds on their lengths and explain how we construct these minimal DNA expressions.     

Embedding linear orders in grids

A grid (or a mesh) is a two-dimensional permutation: an m× n-grid of size mn is an m× n-matrix where the entries run through the elements {1,2, …, mn}. We prove that if δ₁ and δ₂ are any two linear orders on {1,2, …, N}, then they can be simultaneously embedded (in a well defined sense) into a unique grid having the smallest size.     

A characterization of context-free string languages by directed node-label controlled graph grammars

Summary Directed node-label controlled graph grammars (DNLC grammars) are sequential graph rewriting systems. In a direct derivation step of a DNLC grammar a single node is rewritten. Both the rewriting of a node and the embedding of a daughter graph in a host graph are controlled by the labels of nodes only. We study the use of those grammars to define string languages. In particular we provide a characterization of the class of context-free string languages in terms of DNLC grammars.     

Application of Mismatch Detection Methods in DNA Computing

In many implementations of DNA computing, reliable detection of hybridization is of prime importance. We have applied several well-established DNA mutation scanning methods to this problem. Since they have been developed for speed and accuracy, these technologies are very promising for DNA computing. We have benchmarked a heteroduplex migration assay and enzymatic detection of mismatches on a 4 variable instance of 3SAT, using a previously described blocking algorithm. The first method is promising, but yielded ambiguous results. On the other hand, we were able to distinguish all perfect from imperfect duplexes by means of a CEL I mismatch endonuclease assay.     

Extension of tabled 0L-systems and languages

This paper introduces a new family of languages which originated from a study of some mathematical models for the development of biological organisms. Various properties of this family are established and in particular it is proved that it forms a full abstract family of languages. It is compared with some other families of languages which have already been studied and which either originated from the study of models for biological development or belong to the now standard Chomsky hierarchy. A characterization theorem for context-free languages is also established.This research has been supported by NSF Grant GJ 998.