Date of Award


Degree Type


Degree Name

Master of Science


Computer Science


Dr. Lila Kari


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.



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.