Western University Computer ScienceWestern Science

MSc Thesis Defense

 

Zihao Wang

Word Blending and Other Formal Models of Bio-operations

 

Date:
Time:
Place:
Supervisor:
Thesis Examiners:

Extra-Departmental
Examiner:
Chair:
Tuesday, May 29, 2018
130 a.m.
Middlesex College, Room 320
Dr. Lila Kari
Dr. Marc Moreno Maza
Dr. Roberto Solis Oba

Dr. David Jeffrey (Applied Math)
Dr. Robert Webber

 

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 xwu and vwy sharing a non-empty overlap part w generate the word xwy. 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.