ALGORITHMS FOR SPLICING SYSTEMS
In [Bull. Math. Biol., 49 (1987), pp. 737-759] T Head proposed a mathematical abstraction of the effect of restriction enzyme digestion and subsequent religation in the recombination of DNA molecules. In particular, he was concerned with the structure of the language of all DNA which could be produced by a splicing system consisting of a finite set of initial DNA and two finite sets of enzymes. He was able to show that, under appropriate conditions, the language produced is strictly locally testable and hence recursively decidable. In this paper, an algorithmic reduction on the set of patterns is given and additional conditions introduced. The main result is that for a particular class of splicing systems there is a universal algorithm which produces a finite automaton that accepts the splicing language. The relation between this class and that studied by Head is examined and the questions of membership, finiteness, and equivalence of languages are shown to be recursive. Algorithms are given which are implementable and may be of practical interest.
splicing system dna strictly locally testable finite automata