An algorithm for identifying spliced languages (Q4364597)

Genetic splicing is an abstraction of the genetic engineering which involves restriction enzymes and DNA molecules represented by strings over an alphabet of four pairing symbols \(A/T\), \(C/G\), \(G/C\) and \(T/A\). The effect of a restriction enzyme is to cleave a DNA molecule into two pieces at a specific pattern which is defined by the enzyme. Two cleaved DNA strings can be recombined and form a new string if they have matching cleaved ends. To abstract this process, let each of the pairing symbols be represented by a single symbol in an alphabet \(A\). An enzyme \(s\in A^+\) can be viewed as consisting of three substrings, i.e., \(s=ux v\), \(u,x,v\in A^*\), such that a DNA string \(w\) is cut at its substring \(x\), so called crossing, if it has a matching substring \(uxv\). If there are two DNA strings \(w_0uxvz_0\) and \(w_1u'xv' z_1\), and two enzymes \(uxv\) and \(u'xv'\) which have identical crossing \(x\), the two DNA strings are cleaved and recombined (i.e., spliced) at \(x\) producing new strings \(w_0uxv'z_1\) and \(w_1u'xv \). We can abstract this process in terms of a language generating system of two sets of strings, one for DNA strings and the other for enzymes. The paper presents an algorithm for the problem of deciding whether or not a language \(L\), given in terms of the state transition graph of the reduced finite state automaton whose language is \(L\), can be generated by a splicing system with a finite initial set of strings using a given enzyme set \(X\). The algorithm is based on the properties of cycles of the state transition graph that should be satisfied if the language can be spliced with a finite initial set of strings. For the entire collection see [Zbl 0869.00027].