Date of Award
2008
Degree Type
Thesis
Degree Name
Master of Science
Program
Computer Science
Supervisor
Dr. Lila Kari
Abstract
In this thesis, we propose a bottom-up method to design single-stranded DNA sequences that form consecutive hairpin structures. This work was inspired by the hairpin-based DNA multi-state machine proposed by Takahashi et al. in 2004. They have successfully achieved this DNA multiple-hairpin structure in a laboratory experiment and proposed two possible applications. The first one is to construct a random access memory (RAM) by using the DNA machines as the access address for the data. The second one is to solve the maximum independent set problem (MISP). It is interesting thus to investigate how to design DNA sequences which form consecutive hairpin structures as mentioned above. We propose a bottom-up approach to construct consecutive hairpin structures, grounded on a so-called bond-free property, and several combinatorial constraints. A software is implemented to study the behavior of our bottom-up approach. We also calculate the maximal number of sequences that correctly fold into the desired multiple-hairpin structure. This calculation provides an estimation for the size of the memory that can be constructed using Takahashi et aVs method. Lastly, by selecting suitable parameters, we successfully construct a set of sequences that can fold in to the desirable multiple-hairpin structure. For example, our software is able to generate 120 sequences that can fold into a four-hairpin structure where the length of each hairpin stem is 20, the length of each hairpin loop is 7 and the external segment is 20. We validate these sequences using the molecule secondary structure prediction package, Vienna RNA secondary structure package.
Recommended Citation
Zeng, Yan, "DNA Hairpin Secondary Structure Design" (2008). Digitized Theses. 4199.
https://ir.lib.uwo.ca/digitizedtheses/4199