Date of Award


Degree Type


Degree Name

Master of Science


Computer Science


Dr. Lila Kari


To solve the mystery of the intricate gene unscrambling mechanism in ciliates, various theoretical models for this process have been proposed from the point of view of computation. Two main models are the reversible guided recombination system by Kari and Landweber and the template-guided recombination (TGR) system by Prescott, Ehrenfeucht and Rozenberg, based on two categories of DNA recombination: the pointer guided and the template directed recombination respectively. The latter model has been generalized by Daley and McQuillan. In this thesis, we propose a new approach to generate regular languages using the iterated TGR system with a finite initial language and a finite set of templates, that reduces the size of the template language and the alphabet compared to that of the Daley-McQuillan model. To achieve computational completeness using only finite components we also propose an extension of the contextual template-guided recombination system (CTGR system) by Daley and McQuillan, by adding an extra control called permitting contexts on the usage of templates. Then we prove that our proposed system, the CTGR system using permitting contexts, has the capability to characterize the family of recursively enumerable languages using a finite initial language and a finite set of templates. Lastly, we present a comparison and analysis of the computational power of the reversible guided recombination system and the TGR system. Keywords: ciliates, gene unscrambling, in vivo computing, DNA computing, cellular computing, reversible guided recombination, template-guided recombination.



To view the content in your browser, please download Adobe Reader or, alternately,
you may Download the file to your hard drive.

NOTE: The latest versions of Adobe Reader do not support viewing PDF files within Firefox on Mac OS and if you are using a modern (Intel) Mac, there is no official plugin for viewing PDF files within the browser window.