| ¡¡ | Chinese Journal of Computers Full Text |
| Title | The Basic Algebraic Principles of DNA Computing(I) |
| Authors | HUANG Yu-Qian |
| Address | (College of Computer Information and Engineering, Jiangxi Normal University, Nanchang 330022) |
| Year | 2008 |
| Issue | No.3(353¡ª371) |
| Abstract & Background | Abstract By introducing concepts of M-paste algebra, M-cut algebra and M-recombination algebra, the DNA computing associated with mark set M can be deduced precisely according to the algebraic laws given in the introduced algebras. The author investigates a series of properties of these algebras and obtains many interesting results. These results will give us much convenience in research on the theory and application of DNA computing. keywords DNA computing; M-paste algebra; M-cut algebra; M-recombination algebra; formal language background In his pioneering paper £ÛHead,1987£Ý, Head had introduced the splicing system concept as a formal device for the generation of languages and as a formal model of specific forms of DNA recombination. Thus he established the close relationship between the recombinant behavior of DNA in the field of life science and formal language theory in theoretical computer science. The splicing operation raises a large number of appealing problems for formal language theorists: Producing new splicing systems and studying it¡¯s power as well as properties of corresponding languages, looking for the relation between splicing operations and usual operations in formal language theory and for the closure of families of languages(in Chomsky hierarchy) under such operations, etc.After this, one developed varied splicing systems, such as, H-systems, extended H-systems, extended H-systems with certain control mechanisms(multiset, permitting context, forbidding context, double splicing, or distributed architectures), multiple splicing systems, etc. Some systems among those was proved that they are computation complete(equivalent to Turing machine), and constructed corresponding universal splicing systems. Mateescu et al. considered simple splicing systems £ÛMateescu,1998£Ý. They investigated the properties of the corresponding family: Representation, closure properties, descriptional complexity, decidability, relationships with other subfamilies of the family of regular languages etc. Specifically, they gave an algebraic characterization for languages in this family by introduced operation #M. But, except indicating that #M is an associative operation(expression and proof both are wrong), they haven¡¯t do any further researches of properties for introducing operations ¡óM and #M. In this paper, the author replaces ¡óM by ?M, and improves the definition of the operation #M. Moreover, the author also introduces new operations PM, SM and FM. Specifically, he investigates a series of properties of those operations, and further proposes concepts of M-paste algebra, M-cut algebra and M-recombination. Thus the DNA computing associated with mark set M can be deduced precisely according to algebraic laws given in proposed algebras. These results will give us much convenience in research on the theory and application of DNA computing. |