Studies on Insertion-deletion Systems and Contextual Grammars Related to Ambiguity, Measures and Applications

Gene insertion and deletion are the operations that occur commonly in Deoxyribonucleic acid (DNA) processing and Ribonucleic acid (RNA) editing. Based on these operations, a computing model has been formulated in formal language theory known as insertion-deletion systems. As the biological macromolecules can be viewed as symbols, the gene sequences can be represented as strings. This suggests that the molecular representation can be theoretically analyzed if a biologically inspired computing model recognizes various bio-molecular structures that are predominantly available in DNA, RNA and proteins. Contextual grammars were introduced by Solomon Marcus in 1969 (Marcus 1969), based on the fundamental concept of descriptive linguistics. Internal contextual grammars were introduced by Păun and Nguyen in 1980 as a variant of contextual grammars. Several descriptional complexity measures and various levels of ambiguity were defined for (internal) contextual grammars. Bracketed and Fully bracketed contextual grammars were introduced (Martín Vide and Păun (1998)) to bring the notion of a tree structure to the derived strings. Contextual grammars are the counterpart of insertion-deletion systems as ‘strings’ of latter are ‘selectors’ of former.

We introduce a simple grammar model called Matrix insertion-deletion system to encompass various bio-molecular structures that occur at intramolecular level like hairpin, stem and loop, cloverleaf and at intermolecular level such as double strand, nick language and holliday structure and basic RNA secondary structures like kissing hairpin, bulge loop, internal loop. Based on the components used in the derivation, six new levels of ambiguity for insertion-deletion systems were introduced. We show that there are inherently i-ambiguous insertion-deletion languages which are j-unambiguous for the combinations $(i, j) \in {(5, 4), (4, 3), (4, 2), (3, 1), (2, 1), (1, 0), (0, 1)}$. Then, six new descriptional complexity measures for insertion-deletion systems based on the used contexts and strings were introduced. Finally, the trade-off between the ambiguity levels and various descriptional complexity measures were analyzed by introducing a new notion ‘pseudo inherently ambiguous languages’.

In addition to the work carried out in the domain of insertion-deletion system we carry out some work on its counterpart domain contextual grammar also. We analyze the trade-off between the ambiguity and descriptional complexity measures of languages generated by internal contextual grammars.