Formal models and algorithms for DNA data analysis using Watson-Crick grammars

Abstract

Genetic information encoding in deoxyribonucleic acid (DNA) and DNA manipulation techniques contributes to the advancement of computing technology; namely DNA computing. However, the research in the counterpart of automata in formal language theory which is grammars, of Watson-Crick automata that is one of DNA computing models, has yet to be completed. Thus, more extended computing models for both computationally and algorithmically efficient methods for general and specific purposes can be further exhibited through the investigation of the grammars. The purpose of this research is to develop novel theoretical models based on DNA computing, Watson-Crick automata specifically and it also aims to design efficient algorithms using these models for the specific purposes especially membership and parsing problems. We have established Watson-Crick grammars; particularly modified version of Watson-Crick regular grammars, novel Watson-Crick linear grammars, and Watson-Crick context-free grammars. The expansion of the grammars starting from Watson-Crick regular grammars to Watson-Crick context-free grammars was based on Chomsky’s families of languages hierarchy. The generative power and closure properties of each type of the grammars were investigated. Watson-Crick regular grammars are able to generate non-context-free languages, thus it is more powerful than their counterpart which is regular grammars. The distinction of each type of Watson-Crick grammars is on their ability to generate different levels of balanced parentheses in Dyck language. It is proven that Watson-Crick regular languages are properly included in Watson-Crick linear languages, and the latter are properly included in Watson-Crick context-free languages. The upper bound of the family of Watson-Crick context-free languages is the family of matrix languages. Although they are more powerful, it has been discovered that their closure properties are similar with the properties of the Chomsky grammars’ counterparts. The simplification processes of Watson-Crick (WK) context-free grammars were studied. This resulted in a normal form based on Chomsky normal form, but it came with two types of terminal symbols instead of one. Using this WK-Chomsky normal form, we designed a membership algorithm based on Cocke-Younger-Kasami algorithm, which can also be utilized as a parsing method for data in the form of double-stranded string with Watson-Crick complementarity. The expansion of Watson-Crick context-free grammars also led to the development of their automata counterparts, Watson-Crick pushdown automata; with one stack or complementarity stacks. Unlike Watson-Crick automata, complementarity-stack Watson-Crick pushdown automaton includes double stacks connected by Watson-Crick complementarity. We also modified two basic parsing algorithms: top-down parsing and bottom-up parsing to suit double-stranded strings based on this automaton. Further, we introduced Watson-Crick matrix grammars where the rules in Watson-Crick context-free grammars are arranged in matrices, allowing simultaneous control on the production rules. Although it is not more powerful than parallel communicating Watson-Crick automata systems, the result suggests that parallelism features can be employed in the variants of Watson-Crick grammars. These models can be well implemented in string matching problems such as problems occur in DNA analysis and natural language processing.