Insertion and deletion are considered to be the basic operations in Biology, more specifically in DNA processing and RNA editing. Based on these evolutionary transformations, a computing model has been formulated in formal language theory known as insertion-deletion systems. Since the biological macromolecules can be viewed as symbols, the gene sequences can be represented as strings. This suggests that the molecular representations can be theoretically analyzed if a biologically inspired computing model recognizes various bio-molecular structures like pseudoknot, hairpin, stem and loop, cloverleaf and dumbbell. In this paper, we introduce a simple grammar system that encompasses many bio-molecular structures including the above mentioned structures. This new grammar system is based on insertion-deletion and matrix grammar systems and is called Matrix insertion-deletion grammars. Finally, we discuss how the ambiguity levels defined for insertion-deletion grammar systems can be realized in bio-molecular structures, thus the ambiguity issues in gene sequences can be studied in terms of grammar systems. © 2011 Springer-Verlag.

Lakshmanan K

Department of Analytics

School of Computer Science and Engineering

Vellore Campus

L. Kuppusamy

A. Mahendran

Shankara Narayanan Krishna

Mahendran A

Krishna S.N.

ambiguity

bio-molecules

insertion-deletion systems

Matrix grammars

structure representation

Vellore Institute of Technology (VIT) is a private university located in&nbsp;Tamil Nadu, India. Founded in 1984, as Vellore Engineering College, the institution offers 20 undergraduate, 34 postgraduate, four integrated and four research programs. It has campuses in Vellore, Amravati, Bhopal and Chennai.

VIT is one of the top ranked private universities in India according to NIRF, THE and QS Rankings.&nbsp;Govt. of India has recognized&nbsp;VIT, Vellore as an&nbsp;Institution of Eminence. This has allowed VIT to take independent quality initiatives and move up in world ranking.

&nbsp;

&nbsp;

VIT University

Matrix insertion-deletion systems for bio-molecular structures

Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

Matrix insertion-deletion systems combine the idea of matrix control (a control mechanism well established in regulated rewriting) with that of insertion and deletion (as opposed to replacements). Given a matrix insertion-deletion system, the size of such a system is given by a septuple of integers (k; n, i′, i′ ′; m, j′, j′ ′). The first integer k denotes the maximum number of rules in (length of) any matrix. The next three parameters n, i′, i′ ′ denote the maximal length of the insertion string, the maximal length of the left context, and the maximal length of the right context of insertion rules, respectively. The last three parameters m, j′, j′ ′ are similarly understood for deletion rules. In this paper, we improve on and complement previous computational completeness results for such systems, showing that matrix insertion-deletion systems of size (1) (3; 1, 0, 1; 1, 0, 1), (3; 1, 0, 1; 1, 1, 0), (3; 1, 1, 1; 1, 0, 0) and (3; 1, 0, 0; 1, 1, 1) (2) (2; 1, 0, 1; 2, 0, 0), (2; 2, 0, 0; 1, 0, 1), (2; 1, 1, 1; 1, 1, 0) and (2; 1, 1, 0; 1, 1, 1), are computationally complete. Further, we also discuss linear and metalinear languages and we show how to simulate grammars characterizing them by matrix insertion-deletion systems of size (3; 1, 1, 0; 1, 0, 0), (3; 1, 0, 1; 1, 0, 0), (2; 2, 1, 0; 1, 0, 0) and (2; 2, 0, 1; 1, 0, 0). We also generate non-semilinear languages using matrices of length three with context-free insertion and deletion rules. © 2017, Springer Science+Business Media B.V., part of Springer Nature.

Natural Computing

Investigations on the power of matrix insertion-deletion systems with small sizes

A graph-controlled insertion–deletion (GCID) system is a regulated extension of an insertion–deletion system. Such a system has several components and each component has some insertion–deletion rules. The transition is performed by any applicable rule in the current component on a string and the resultant string is then moved to the target component specified in the rule. The language of the system is the set of all terminal strings collected in the final component. The parameters in the size (k;n,i′,i″;m,j′,j″) of a GCID system denote (from left to right) the maximum number of components, the maximal length of the insertion string, the maximal length of the left context for insertion, the maximal length of the right context for insertion; the last three parameters follow a similar representation with respect to deletion. In this paper, we discuss the computational completeness of the families of GCID systems of size (k;1,i′,i″;1,j′,j″) with k∈{3,5} and for (nearly) all values of i′,i″j′,j″∈{0,1}. All proofs are based on the simulation of type-0 grammars given in Special Geffert Normal Form (SGNF). The novelty in our proof presentation is that the context-free and the non-context-free rules of the given SGNF grammar are simulated by GCID systems of different sizes and finally we combine them by stitching and overlaying to characterize the recursive enumerable languages. This proof presentation greatly simplifies and unifies the proof of such characterization results. We also connect some of the obtained GCID simulations to the domain of insertion–deletion P systems. © 2017 Elsevier B.V.

Fulltext

Theoretical Computer Science

On the computational completeness of graph-controlled insertion–deletion systems with binary sizes

The biological sequences that occur in DNA, RNA and proteins can be considered as strings formed over the well defined chemical alphabets. Such gene sequences form structure based on the complementary pair and the structures can be interpreted as languages. Matrix insertion-deletion system has been introduced a few years back that modelled several bio-molecular structures occur at intramolecular and intermolecular level. In this paper, we identify some structures that are frequently noticed during RNA folding process such as double bulge loop, extended internal loop, triple stem and loop and we give the corresponding formal language representation to such structures. Further, we model the structures using Matrix insertion-deletion systems. This work is pioneering to give the language representation and modelling the structures of RNA folding process using formal grammar. © 2017, Springer International Publishing AG.

Theoretical Computer Science and Discrete Mathematics Lecture Notes in Computer Science

Formal Language Representation and Modelling Structures Underlying RNA Folding Process

AbstractInsertion and deletion are operations that occur commonly in DNA processing and RNA editing. Since biological macromolecules can be viewed as symbols, gene sequences can be represented as strings and structures can be interpreted as languages. This suggests that the bio-molecular structures that occur at different levels can be theoretically studied by formal languages. In the literature, there is no unique grammar formalism that captures various bio-molecular structures. To overcome this deficiency, in this paper, we introduce a simple grammar model called the matrix insertion–deletion system, and using it we model several bio-molecular structures that occur at the intramolecular, intermolecular and RNA secondary levels.

International Journal of Applied Mathematics and Computer Science

Modelling DNA and RNA secondary structures using matrix insertion–deletion systems

Matrix insertion-deletion systems combine the idea of matrix control (as established in regulated rewriting) with that of insertion and deletion (as opposed to replacements). We improve on and complement previous computational completeness results for such systems, showing (for instance) that matrix insertion-deletion systems with matrices of length two, insertion rules of type (1, 1, 1) and context-free deletions are computationally complete. We also show how to simulate (Kleene stars of) metalinear languages with several types of systems with very limited resources. We also generate non-semilinear languages using matrices of length three with context-free insertion and deletion rules. © Springer International Publishing Switzerland 2016.

Unconventional Computation and Natural Computation Lecture Notes in Computer Science

Generative Power of Matrix Insertion-Deletion Systems with Context-Free Insertion or Deletion

Bioinformatics

The language of RNA: a formal grammar that includes pseudoknots

Tree adjoining grammars for RNA structure prediction

Handbook of Formal Languages

Nucleic Acids Research

Genome structure described by formal languages

[1991] Proceedings. The Seventh IEEE Conference on Artificial Intelligence Application

Pattern-matching search of DNA sequences using logic grammars

Journal	Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
ISSN	3029743
Open Access	No