Splicing operation

A formal model of the recombinant behaviour of DNA sequences under the influence of restriction enzymes and ligases; it was introduced in [a2].

A splicing rule over an alphabet $ V $ is a string $ r = u _ {1} \# u _ {2} \dlr u _ {3} \# u _ {4} $, where $ u _ {1} ,u _ {2} ,u _ {3} ,u _ {4} \in V ^ {*} $ and $ \# $, $ \dlr $ are two symbols not in $ V $. With respect to such a rule, for three strings $ x,y,z \in V ^ {*} $ one writes $ ( x,y ) \vdash _ {r} z $ if $ x = x _ {1} u _ {1} u _ {2} x _ {2} $, $ y = y _ {1} u _ {3} u _ {4} y _ {2} $, $ z = x _ {1} u _ {1} u _ {4} y _ {2} $, for some $ x _ {1} ,x _ {2} ,y _ {1} ,y _ {2} \in V ^ {*} $.

The pair $ x,y $ is said to splice at the sites $ u _ {1} u _ {2} $, $ u _ {3} u _ {4} $, respectively.

A pair $ \sigma = ( V, R ) $, where $ V $ is an alphabet and $ R \subseteq V ^ {*} \# V ^ {*} \dlr V ^ {*} \# V ^ {*} $ is a set of splicing rules, is called an $ H $- scheme. For a language $ L \subseteq V ^ {*} $, one defines

$$ \sigma ( L ) = $$

$$ = \left \{ {z \in V ^ {*} } : {( x,y ) \vdash _ {r} z \textrm{ for some } x,y \in L, r \in R } \right \} . $$

The operation can be iterated:

$$ \sigma ^ {0} ( L ) = L, $$

$$ \sigma ^ {i + 1 } ( L ) = \sigma ^ {i} ( L ) \cup \sigma ( \sigma ^ {i} ( L ) ) , \quad i \geq 0, $$

$$ \sigma ^ {*} ( L ) = \cup _ {i \geq 0 } \sigma ^ {i} ( L ) . $$

On this basis, the notion of an extended $ H $- system has been introduced, [a6], as a construct

$$ \gamma = ( V,T,A,R ) , $$

where $ V $ is an alphabet, $ T \subseteq V $( terminal alphabet), $ A \subseteq V ^ {*} $( axioms), and $ R \subseteq V ^ {*} \# V ^ {*} \dlr V ^ {*} \# V ^ {*} $, where $ \# $, $ \dlr $ are special symbols not in $ V $; $ \sigma = ( V,R ) $ is the underlying $ H $- scheme of $ \gamma $.

The language generated by $ \gamma $ is defined by $ L ( \gamma ) = \sigma ^ {*} ( A ) \cap T ^ {*} $. For two families of languages, $ F _ {1} $, $ F _ {2} $, let $ { \mathop{\rm EH} } ( F _ {1} ,F _ {2} ) $ be the family of languages $ L ( \gamma ) $ generated by the extended $ H $- systems $ \gamma = ( V,T,A,R ) $ with $ A \in F _ {1} $, $ R \in F _ {2} $. Let FIN, REG and RE be the families of finite, regular, and recursively enumerable languages, respectively. Then:

1) $ { \mathop{\rm EH} } ( { \mathop{\rm REG} } , { \mathop{\rm FIN} } ) = { \mathop{\rm REG} } $([a1]);

2) $ { \mathop{\rm EH} } ( { \mathop{\rm FIN} } , { \mathop{\rm REG} } ) = { \mathop{\rm RE} } $([a5]).

The second result above was followed by many related characterizations of recursively enumerable languages by means of extended $ H $- systems with finite sets of axioms and splicing rules, with the splicing operation controlled in various ways. (This theoretically proves the possibility of constructing universal "DNA computers" based on splicing.) Details can be found in [a3], [a4], [a7].

See also Formal languages and automata.

References

[a1]	K. Culik II, T. Harju, "Splicing semigroups of dominoes and DNA" Discrete Appl. Math. , 31 (1991) pp. 261–277
[a2]	T. Head, "Formal language theory and DNA: an analysis of the generative capacity of specific recombinant behaviors" Bull. Math. Biology , 49 (1987) pp. 737–759
[a3]	T. Head, Gh. Păun, D. Pixton, "Language theory and molecular genetics. Generative mechanisms suggested by DNA recombination" G. Rozenberg (ed.) A. Salomaa (ed.) , Handbook of Formal Languages , Springer (1997)
[a4]	Gh. Păun, "Splicing. A challenge to formal language theorists" Bulletin of EATCS , 57 (1995) pp. 183–194
[a5]	Gh. Păun, "Regular extended H systems are computationally universal" J. Automata, Languages, Combinatorics , 1 : 1 (1996) pp. 27–36
[a6]	Gh. Păun, G. Rozenberg, A. Salomaa, "Computing by splicing" Theor. Comput. Sci. , 161 (1996) pp. 321–336
[a7]	Gh. Păun, A. Salomaa, "DNA computing based on the splicing operation" Math. Japon. , 43 : 3 (1996) pp. 607–632