Search

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. Research on generalisations of splicing languages in DNA splicing system involving palindromic sequences for restriction enzymes has been done previously. 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 one 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.

Head in 1987 was the first person to introduce the concept of splicing system as a theoretical model for DNA based computation using splicing operation. Splicing operation is a method of cutting and recombining DNA molecules under the influence of restriction enzymes such as ligase. Previous researches have proven that splicing systems with finite sets of axioms and rules generate only regular languages. Hence, in order to increase the computational power of the languages generated by splicing systems, several restrictions in the use of rules have been considered. In this paper, simple splicing systems controlled by permutation groups are defined and the computational power of the languages generated by this variable is explored.

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.

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 (non-overlapping) cutting sites are generalised as regular expressions.

Insertion is an operation in formal language theory that generalizes the operation of concatenation of words, where its variants allow the operation in different ways. Parallel insertion is a variant of insertion that simultaneously adds words between all letters of a word and also at the right and left extremities. In previous research, restrictions on the applicability have been imposed leading to so-called bonded insertion systems with a sequential and a parallel variant. Motivated by the atomic behavior of chemical compounds in the process of chemical bonding, the generative power of bonded insertion systems has been investigated where a language hierarchy was obtained. In this paper, we introduce new variants of bonded parallel insertion systems, namely bonded Indian parallel insertion systems and bonded uniformly parallel insertion systems. We present some results regarding the generative power of these new systems and a language hierarchy.

A place-labelled Petri net controlled grammar is, in general, a context-free grammar equipped with a Petri net and a function which maps places of the net to productions of the grammar. The languages of place-labelled Petri net controlled grammar consist of all terminal strings that can be obtained by parallel application of the rules of multisets which are the images of the sets of input places in a successful occurrence sequence of the Petri net. In this paper, we investigate the structural subclass of place-labelled Petri net controlled grammar which focus on the state machine. We also establish the generative capacity of state machine of place-labelled Petri net controlled grammars.

Splicing system was introduced by Head in 1987 in order to explore the recombinant behaviour of deoxyribonucleic acid (DNA) strands in the presence of restriction enzymes and ligases. Restriction enzymes cut the DNA strands into a left - pattern and right-pattern while the ligases recombine the left-pattern of the first string with the right-pattern of the second string and vice-versa. Semi-simple splicing system is a variant of splicing system where the splicing of DNA strands will be at two distinct sites. Splicing languages generated from the splicing system are classified based on their computational power, according to the Chomsky Hierarchy. Previous researchers found that the splicing system of finite set of strings and rules generates only regular languages which has the lowest computational power. Hence, some restriction has been introduced to increase the computational power of splicing languages generated. In this research, an element of alternating group of order three is associated with the initial strings of semi-simple splicing system to generate non-regular languages which has higher computational power. Some lemmas and theorems are proven to show that associating the alternating group to the initial strings could increase the computational power of the splicing languages.

A model for DNA computing using the recombination behavior of DNA molecules, known as a sticker system, was introduced by by L. Kari, G. Paun, G. Rozenberg, A. Salomaa, and S. Yu in the paper entitled DNA computing, sticker systems and universality from the journal of Acta Informatica vol. 35, pp. 401-420 in the year 1998. A sticker system uses the Watson-Crick complementary feature of DNA molecules: starting from the incomplete double stranded sequences, and iteratively using sticking operations until a complete double stranded sequence is obtained. It is known that sticker systems with finite sets of axioms and sticker rules generate only regular languages. Hence, different types of restrictions have been considered to increase the computational power of sticker systems. Recently, a variant of restricted sticker systems, called probabilistic sticker systems, has been introduced [4]. In this variant, the probabilities are initially associated with the axioms, and the probability of a generated string is ...

A Head splicing system (H-system)consists of a finite set of strings (words) written over a finite alphabet, along with a finite set of rules that acts on the strings by iterated cutting and pasting to create a splicing language. Any interpretation that is aligned with Tom Head's original idea is one in which the strings represent double-stranded deoxyribonucleic acid (dsDNA) and the rules represent the cutting and pasting action of restriction enzymes and ligase, respectively. A new way of writing the rule sets is adopted so as to make the biological interpretation transparent. This approach is used in a formal language- theoretic analysis of the hierarchy of certain classes of splicing systems, namely simple, semi-simple and semi-null splicing systems. The relations between such systems and their associated languages are given as theorems, corollaries and counterexamples.

The pioneer model of deoxyribonucleic acid (DNA) splicing system in a framework of Formal Language Theory was introduced by Head that led to the existence of other models of splicing system, namely Paun, Pixton and Yusof-Goode. These entire models are inspired by the molecular biological process of DNA splicing. Hence, this paper focuses on the translucent DNA splicing process, particularly on the generated language. Starting with some preliminaries in a limit graph, this paper also provides the experimental design with the predicted and actual result.

Splicing language is the language which results from a splicing system. Splicing system was first introduced by Tom Head in 1987 as the mathematical model of systems of restriction enzymes acting on initial DNA molecules. Splicing languages are closely related to automata theory. Simple splicing systems can be recognized by SH-automata diagrams due to the regularity of splicing languages. SH-automaton defines exactly one language which is the language generated by the simple splicing system. In this paper, the concept of firm and maximal firm subwords are introduced. Some examples are then given to illustrate the maximal firm subwords of a word in a simple splicing system. Taking the SH-automata concept, which is a short compact way of encoding normal non-deterministicautomata in the special case of SH systems, the maximal firm subwords of the initial words of an SH systems serve as the labels for the associated SH-automaton. Some examples which will show the maximal firm subwords of the words in the initial set I, the regular expression for the language generated by the given splicing system and the simplest non-deterministic automaton that recognizes the corresponding splicing system are also given

Watson-Crick automata are one of the automata types that are used for transitions with two reading heads. This automata work on double stranded sequencesrelated by a complementarity relation similar with the Watson-Crick complementarity of DNA molecules. Watson-Crick automata can be related to a Petri net, which is a graphical and mathematical formalism suitable for the modeling and analysis of concurrent, asynchronous and distributed systems.From the relation between Watson-Crick automata and Petri net, a new model namely Watson-Crick Petri net has been developed. In this paper, a new variant of Watson-Crick automata with Petri net as a control unit is introduced. We also presented various types of Watson-Crick Petri nets that are generated using transitions labelled with various labelling policies and finite sets of final markings.

Splicing system is a formal characterization of the generative capacity of specified enzymatic activities acting on initial DNA molecules that was first initiated by Head in 1987. This splicing system is formally illustrated under the framework of Formal Language Theory which is a branch of Theoretical Computer Science and Applied Discrete Mathematics. There are many types of splicing systems including null-context, simple, semi-simple and seminull. In this paper, some relations for those types of splicing systems are presented.

A model for DNA computing using the recombination behaviour of DNA molecules known as a sticker system has been introduced by Adleman in 1994. A sticker model is an abstract computational model which uses the Watson-Crick complementary principle of DNA molecules. Starting from the axioms – incomplete double stranded sequences, and iteratively using sticking operations, complete double stranded sequences are obtained. It is known that sticker systems with finite sets of axioms and sticker rules generate only regular languages. Hence, different types of restrictions have been considered to increase the computational power of sticker systems. In this paper, we introduce probabilistic sticker systems in which probabilities are initially associated with the axioms, and the probability of the generated string is computed by multiplying the probabilities of all occurrences of the initial strings used in the computation of the string.

The study on cutting and pasting of DNA molecules under the framework of Formal Language Theory has led to the mathematical modelling of splicing system. The output of splicing system is the splicing language which can be categorized into three types: adult or inert persistent, transient and limit language. In the biological point of view, limit language is predicted to appear after the reaction of DNA molecules and enzyme with the existence of appropriate ligase reached the equilibrium state. In this research, the second order limit language is investigated. It is defined as the distinct language after splicing occurs among the resulting splicing language of the first order splicing language. Besides that, the characteristics of second order limit language are observed based on the properties of the crossing sites of the rules such as left or right context and palindromic via Y-G approach. The results lead to some examples and theorems which are presented in this paper.

Sticker systems were introduced in 1998 as one of the DNA computing models by using the recombination behavior of DNA molecules. The Watson-Crick complementary principle of DNA molecules is abstractly used in the sticker systems to perform the computation of sticker systems. In this paper, the generative power of weighted one-sided sticker systems and weighted regular sticker systems are investigated. Moreover, the relationship of the families of languages generated by these two variants of sticker systems to the Chomsky hierarchy is also presented.

A Watson-Crick automaton is an automaton that works on tapes which are double stranded sequences of symbols related by Watson-Crick complementarity that are similar to the DNA molecules. However, this automaton cannot exploit the other fundamental features of DNA molecules such as the massive parallelism. Watson-Crick automata can be related to a model known as the Petri net. Petri net is a model based on the concepts of asynchronous and concurrent operation by the parts of a system and the realization by the parts can be represented by a graph or a net. From the relation between Watson-Crick automata and Petri net, a new model namely Watson-Crick Petri net has been developed. The language generated by Watson-Crick Petri net is a set of labeled sequences corresponding to the occurrence sequences of the model. In this research, some properties of languages generated by Watson-Crick Petri net are investigated.

A splicing system, one of the early theoretical models for DNA computing was introduced by Head in 1987. Splicing systems are based on the splicing operation which, informally, cuts two strings of DNA molecules at the specific recognition sites and attaches the prefix of the first string to the suffix of the second string, and the prefix of the second string to the suffix of the first string, thus yielding the new strings. For a specific type of splicing systems, namely the simple splicing systems, the recognition sites are the same for both strings of DNA molecules. It is known that splicing systems with finite sets of axioms and splicing rules only generate regular languages. Hence, different types of restrictions have been considered for splicing systems in order to increase their computational power. Recently, probabilistic splicing systems have been introduced where the probabilities are initially associated with the axioms, and the probabilities of the generated strings are computed from the probabilities of the initial strings. In this paper, some properties of probabilistic simple splicing systems are investigated. We prove that probabilistic simple splicing systems can also increase the computational power of the splicing languages generated.