Search

DNA splicing system is initiated by Head to mathematically model a relation between formal language theory and DNA molecules. In DNA splicing systems, DNA molecules are cut and recombined in specific ways with the existence of enzymes, which are also known as endonucleases, to produce further molecules. The resulting molecules are depicted as splicing languages by using concepts in formal languages theory. A sequence of restriction enzyme that reads the same forward and backward is called as a palindromic rule. Previously, researches on different types of splicing languages have been done. In this research, generalisations of splicing languages resulting from DNA splicing systems with non-overlapping cutting sites of two palindromic restriction enzymes are presented as theorems using the induction method. The results from this research are beneficial for researchers in the field of DNA computing since it contributes to the development of splicing languages generated from DNA splicing systems with different palindromic restriction enzymes by using these generalisations.

Sticker systems and Watson-Crick automata are two modellings of DNA molecules in DNA computing. A sticker system is a computational model which is coded with single and double-stranded DNA molecules; while Watson-Crick automata is the automata counterpart of sticker system which represents the biological properties of DNA. Both of these models use the feature of Watson-Crick complementarity in DNA computing. Previously, the grammar counterpart of the Watson-Crick automata have been introduced, known as Watson-Crick grammars which are classified into three classes: Watson-Crick regular grammars, Watson-Crick linear grammars and Watson-Crick context-free grammars. In this research, a new variant of Watson-Crick grammar called a static Watson-Crick context-free grammar, which is a grammar counterpart of sticker systems that generates the double-stranded strings and uses rule as in context-free grammar, is introduced. The static Watson-Crick context-free grammar differs from a dynamic Watson-Crick context-free grammar in generating double-stranded strings, as well as for regular and linear grammars. The main result of the paper is to determine the generative powers of static Watson-Crick context-free grammars. Besides, the relationship of the families of languages generated by Chomsky grammars, sticker systems and Watson-Crick grammars are presented in terms of their hierarchy.

Sticker system is a computer model which is coded with single and double-stranded molecules of DNA; meanwhile, Watson-Crick automata is the automata counterpart of the sticker system representing the biological properties of DNA. Both are the modelings of DNA molecules in DNA computing which use the feature of Watson-Crick complementarity. Formerly, Watson-Crick grammars which are classified into three classes have been introduced [1]. In this research, a grammar counterpart of sticker systems that uses the rule as in context-free grammar is introduced, known as a static Watson-Crick context-free grammar. The research finding on the computational power of these grammar shows that the family of context-free languages is strictly included in the family of static Watson-Crick context-free languages; the static Watson-Crick context-free grammars can generate non context-free languages; the family of Watson-Crick context-free languages is included in the family of static Watson-Crick context-free languages which are presented in terms of their hierarchy.

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.

Mathematical modelling of splicing system has been introduced to initiate a linkage between the study of informational macromolecules that includes DNA and formal language theory. The ability to present the nitrogenous base which is a component in a nucleotide of DNA, as a series of alphabet, ignites this interdisciplinary study. Over the years, researchers have developed models to match their need. In addition, product of splicing system is called splicing language. Through some development, second order limit language is derived from other type of languages known as limit language. Its existence and characteristics have been vastly discussed. Beside, some types of splicing system can produce second order limit language. In this research, the characteristics of varieties of splicing system are studied and their relations with second order limit language are established.

DNA computing, or more generally, molecular computing, is a recent development at the interface of computer science and molecular biology. In DNA computing, many computational models have been proposed in the framework of formal language theory and automata such as Watson-Crick grammars and sticker systems. A Watson-Crick grammar is a grammar model that generates double stranded strings, whereas a sticker system is a DNA computing model of the ligation and annealing operations over DNA strands using the Watson-Crick complementarity to form a complete double stranded DNA sequence. Most of the proposed DNA computing models make use of this concept, including the Watson-Crick grammars and sticker systems. Watson-Crick grammars and their variants can be explored using formal language theory which allows the development of new concepts of Watson-Crick grammars. In this research, a new variant of Watson-Crick grammar called a static Watson-Crick regular grammar is introduced as an analytical counterpart of sticker systems. The computation of a sticker system starts from a given set of incomplete double stranded sequence to form a complete double stranded sequence. Here, a static Watson-Crick regular grammar differs from a dynamic Watson-Crick regular grammar in generating double stranded strings: the latter grammar produces each strand string “independently” and only check for the Watson-Crick complementarity of a generated complete double stranded string at the end, while the former grammar generates both strand strings “dependently”, i.e., checking for the Watson-Crick complementarity for each complete substring. In this paper, computational properties of static Watson-Crick regular grammars are investigated to correlate with the Chomsky hierarchy and hierarchy of the families of dynamic Watson-Crick regular languages. The relationship between families of languages generated by static Watson-Crick regular grammars with several variants of sticker systems, Watson-Crick regular grammars and Chomsky grammars are presented by showing the hierarchy.

In DNA splicing system, the potential effects of sets of restriction enzymes and a ligase that allow DNA molecules to be cleaved and reassociated to produce further molecules are studied. A splicing language depicts the molecules resulting from a splicing system. In this research, a C++ programming code for DNA splicing system with one palindromic restriction enzyme for one and two (non-overlapping) cutting sites is developed. A graphical user interface, GUI is then designed to allow the user to insert the initial DNA string and restriction enzymes to generate the splicing languages which are the result of the computation of the C++ programming. This interface displays the resulting splicing languages, which depict the results from in vitro experiments of the respective splicing system. The results from this research simplify the lenghty manual computation of the resulting splicing languages of DNA splicing systems with one palindromic restriction enzyme.

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.

Through the years, formal language theory has evolved through continual interdisciplinary work in theoretical computer science, discrete mathematics and molecular biology. The combination of these areas resulted in the birth of DNA computing. Here, language generating devices that usually considered any set of letters have taken on extra restrictions or modified constructs to simulate the behavior of recombinant DNA. A type of these devices is an insertion-deletion system, where the operations of insertion and deletion of a word have been combined in a single construct. Upon appending integers to both sides of the letters in a word, bonded insertion-deletion systems were introduced to accurately depict chemical bonds in chemical compounds. Previously, it has been shown that bonded sequential insertion-deletion systems could generate up to recursively enumerable languages. However, the closure properties of these systems have yet to be determined. In this paper, it is shown that bonded sequential insertion-deletion systems are closed under union, concatenation, concatenation closure, λ-free concatenation closure, substitution and intersection with regular languages. Hence, the family of languages generated by bonded sequential insertion-deletion systems is shown to be a full abstract family of languages.

Graph splicing system is a notion originally used to illustrate the one-dimensional string of DNA splicing in the form of a graph. A graph splicing system is associated with a graph splicing scheme where graph splicing rules are defined. A graph splicing rule restricts the possible cuts to occur on the edges of the initial graph(s) in a graph splicing system. The subgraphs of the initial graph are used in the splicing rules to determine the edges that will be cut from the initial graph. The concept of graph splicing system can be applied on various types of graph, hence generates components of spliced graphs depending on the types of the graph splicing rules used. There is a graph splicing rule called as a cutting rule which can be applied on both linear graphs and circular graphs where the graphs are transformed into Pseudo-Linear Form. However, this cutting rule has limited various possible cuts that can occur on the complete graph. Therefore, in this research, the original concept of graph splicing system is applied on complete graphs as the initial graphs. Also, graph splicing rules involving subgraphs of the initial graphs which are also complete graphs, are considered and applied in the graph splicing system. Furthermore, the generated spliced graphs are obtained through the graph splicing system.

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.

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

A place-labelled Petri net (pPN) controlled grammar is a context-free grammar equipped with a Petri net and a function which maps places of the net to the productions of the grammar. The language consists of all terminal strings that can be obtained by simultaneously applying the rules of multisets which are the images of the sets of the input places of transitions in a successful occurrence sequence of the Petri net. In this paper, we study the generative power and structural properties of pPN-controlled grammars. We show that pPN-controlled grammars have the same generative power as matrix grammars. Moreover, we prove that for each pPN-controlled grammar, we can construct an equivalent place-labelled ordinary net controlled grammar.

DNA computing involves computing models which use the recombination behavior of DNA molecules as computation devices. This idea was successfully applied by Adleman in his biological experiment in order to show the solvability of the Hamiltonian path problem for larger instances. In 1998, a DNA based computation model, called sticker system, which is an abstraction of the computations using the recombination behavior as in Adleman’s experiment was proposed. In 2013, a new variant of sticker system using weights was introduced, namely the weighted sticker system. In this paper, the generative capacity for several variants of bounded delay and nonrestrictive weighted sticker systems are investigated. The relation between families of languages generated by several variants of weighted sticker systems and weighted grammars are also presented.

Sticker systems have been introduced as one of the DNA computing models by using the recombination behavior of DNA molecules in 1998. Abstractly, the systems use the Watson-Crick complementary principle of DNA molecules to perform the computation in generating new strings. By associating some weights to the axioms and dominoes of sticker system, a new version of restricted sticker system namely weighted sticker system has been introduced. In this paper, we study the generative power of weighted sticker systems by considering the languages generated by weighted sticker system with different weighting spaces and cut-points. The relations of the languages generated by weighted sticker systems in the Chomsky hierarchy are also investigated.

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.

The mathematical modelling of splicing system which involves recombination of DNA molecules was first introduced by Head in 1987. Splicing of DNA involves cutting of DNA molecules using the restriction enzymes and re-associating different fragments of DNA molecules using the ligase under some specific chemical conditions. A splicing language, L is generated if there exists a splicing system S for which L = L(S). There are different types of splicing systems which have been discussed by various researchers. Among them are the persistent splicing system, null-context and uniform splicing system. In this paper, some molecular examples on null-context splicing system and uniform splicing systems with different initial strings and combination of restriction enzymes will be discussed. Applications of automata theory on some molecular examples of null-context and uniform splicing languages will also be presented in this paper.

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 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 Watson-Crick Petri net is a new formal model that enhances a Petri net with the Watson-Crick complementary feature adapted from DNA molecules. The transitions of a Watson-Crick Petri net are labeled with pairs of symbols, and a firing sequence of transitions of the Watson-Crick Petri net is considered as successful if and only if it produces complete double stranded sequences of symmetrically related symbols according to some mode of execution termination of the firing of transitions. As an execution termination mode, we can consider the set of all reachable markings and a finite set of final markings. In this research, we investigate the fundamental properties of Watson-Crick Petri net languages with finite sets of final markings.

In this paper we introduce a new variant of splicing systems, called fuzzy splicing systems, and establish some basic properties of language families generated by this type of splicing systems. We study the “fuzzy effect” on splicing operations, and show that the “fuzzification” of splicing systems can increase and decrease the computational power of splicing systems with finite components with respect to fuzzy operations and cut-points chosen for threshold languages.

In this paper we introduce splicing systems with probabilities, i.e., probabilistic splicing systems, and establish basic properties of language families generated by this type of splicing systems. We show that a simple extension of splicing systems with probabilities may increase the computational power of splicing systems with finite components.

In this paper we introduce a new variant of splicing systems, called weighted splicing systems, and establish some basic properties of language families generated by this type of splicing systems. We show that a simple extension of splicing systems with weights can increase the computational power of splicing systems with finite components.

The first mathematical model of a splicing system that was analyzed in the framework of Formal Language Theory was developed in 1987 by Head. This model consists of a finite alphabet, a finite set of initial strings over the alphabet, and a finite set of rules that act upon the strings by iterated cutting and pasting, generating new strings. In this paper, a new notation for writing rules in a splicing system and a new extension of splicing systems is introduced in order to make the biological process transparent. These are called Yusof-Goode rules, and they are associated with Yusof-Goode splicing systems. Four different classes of splicing systems are discussed: null-context, uniform, simple and SkH systems. Also, counterexamples are given to illustrate relationships between these splicing system classes.

A mathematical model of a splicing system was firstly developed by Head in 1987. This model is abstractly analyzed in the framework of Formal Language Theory, which is a branch of Applied Discrete Mathematics and Theoretical Computer Science. This model consists of a finite set of initial strings over an alphabet that acts upon a finite set of rules. In this paper, some analysis on certain types of splicing systems namely, null-context, uniform, simple and S k H system are presented as propositions and corollaries. Besides, some counterexamples are given to illustrate these relations.