In DNA splicing system, the potential effect of sets of restriction enzymes and
a ligase that allow DNA molecules to be cleaved and re-associated to produce further
molecules is modelled mathematically. This modelling is done in the framework of formal
language theory, in which the nitrogen bases, nucleotides and restriction sites are modelled
as alphabets, strings and rules respectively. The molecules resulting from a splicing system
is depicted as the splicing language. In this research, the splicing language resulting from
DNA splicing systems with one palindromic restriction enzyme for one and two (nonoverlapping)
cutting sites are generalised as regular expressions.
The modelling of splicing systems is simulated by the process of cleaving and recombining DNA molecules with the presence of a ligase and restriction enzymes which are biologically called as endodeoxyribonucleases. The molecules resulting from DNA splicing systems are known as splicing languages. Palindrome is a sequence of strings that reads the same forward and backward. In this research, the splicing languages resulting from DNA splicing systems with one non-palindromic restriction enzyme are determined using the notation from Head splicing system. The generalisations of splicing languages for DNA splicing systems involving a cutting site and two non-overlapping cutting sites of one non-palindromic restriction enzyme are presented in the first and second theorems, respectively, which are proved using direct and induction methods. The result from the first theorem shows a trivial string which is the initial DNA molecule; while the second theorem determines a splicing language consisting of a set of resulting DNA molecules from the respective DNA splicing system.
Abstract In DNA splicing system, DNA molecules are cut and recombined with the presence of restriction enzymes and a ligase. The splicing system is analyzed via formal language theory where the molecules resulting from the splicing system generate a language which is called a splicing language. In nature, DNA molecules can be read in two ways; forward and backward. A sequence of string that reads the same forward and backward is known as a palindrome. Palindromic and non-palindromic sequences can also be recognized in restriction enzymes. Research on splicing languages from DNA splicing systems with palindromic and non-palindromic restriction enzymes have been done previously. This research is motivated by the problem of DNA assembly to read millions of long DNA sequences where the concepts of automata and grammars are applied in DNA splicing systems to simplify the assembly in short-read sequences. The splicing languages generated from DNA splicing systems with palindromic and non- palindromic restriction enzymes are deduced from the grammars which are visualised as automata diagrams, and presented by transition graphs where transition labels represent the language of DNA molecules resulting from the respective DNA splicing systems.
DNA computing, or more generally, molecular computing, is a recent development on computations using biological molecules, instead of the traditional silicon-chips. Some computational models which are based on different operations of DNA molecules have been developed by using the concept of formal language theory. The operations of DNA molecules inspire various types of formal language tools which include sticker systems, grammars and automata. Recently, the grammar counterparts of Watson-Crick automata known as Watson-Crick grammars which consist of regular, linear and context-free grammars, are defined as grammar models that generate double-stranded strings using the important feature of Watson-Crick complementarity rule. In this research, a new variant of static Watson-Crick linear grammar is introduced as an extension of static Watson-Crick regular grammar. A static Watson-Crick linear grammar is a grammar counterpart of sticker system that generates the double-stranded strings and uses rule as in linear grammar. The main result of the paper is to determine some computational properties of static Watson-Crick linear grammars. Next, the hierarchy between static Watson-Crick languages, Watson-Crick languages, Chomsky languages and families of languages generated by sticker systems are presented.