Degree
Master of Science
Program
Computer Science
Supervisor
Kari, Lila
Abstract
As part of ongoing efforts to view biological processes as computations, several formal models of DNA-based processes have been proposed and studied in the formal language literature. In this thesis, we survey some classical formal language word and language operations, as well as several bio-operations, and we propose a new operation inspired by a DNA recombination lab protocol known as Cross-pairing Polymerase Chain Reaction, or XPCR. More precisely, we define and study a word operation called word blending which models a special case of XPCR, where two words x w p and q w y sharing a non-empty overlap part w generate the word x w y. Properties of word blending that we study include closure properties of the Chomsky families of languages under this operation and its iterated version, existence of solution to equations involving this operation, and its state complexity.
Recommended Citation
Wang, Zihao, "Word Blending and Other Formal Models of Bio-operations" (2018). Electronic Thesis and Dissertation Repository. 5389.
https://ir.lib.uwo.ca/etd/5389