A New Class of Graph Grammars and Modelling of Certain Biological Structures

Abstract

Graph grammars can be used to model the development of diverse graph families. Since their creation in the late 1960s, graph grammars have found usage in a variety of fields, such as the design of sophisticated computer systems and electronic circuits, as well as visual languages, computer animation, and even the modelling of intricate molecular structures Replacement of edges and nodes are the two primary approaches of graph rewriting. In this paper we introduce a new type of node replacement graph grammar known as nc-eNCE graph grammar. With this new class of graph grammars we generated certain graph classes and we showed that these class of graph grammars are more powerful than the existing edge and node controlled embedding graph grammars. In addition, these graph grammars were used to model several common protein secondary structures such as parallel and anti-parallel β-sheet structures in different configurations. The use of these graph grammars in modelling other bio-chemical structures and their interactions remains to be explored.

Keywords

• graph grammars
• non-confluence
• connection instructions
• regular control
• protein secondary structures
• generative power