Open Collections

Computational RNA secondary structure design : empirical complexity and improved methods

University of British Columbia

Ribonucleic acids play fundamental roles in cellular processes and their function is directly related to their structure. The research reported in this thesis is focused on the design of RNA strands that are predicted to fold to a given secondary structure, according to a standard thermodynamic model. The design of RNA structures is important for applications in therapeutics and nanotechnology. This work also applies to DNA with the appropriate thermodynamic model for DNA molecules. The overall goal of this research is to improve the performance and scope of algorithmic methods for RNA secondary structure design. First, we investigate the hardness of this problem, since its theoretical complexity is unknown. A scaling analysis on random and biologically generated structures supports the hypothesis that the running time of the RNA Secondary Structure Designer (RNA-SSD) algorithm, one of the state of the art algorithms for designing secondary structures, scales polynomially with the size of the structure. We found that structures with small stems separated by loops are difficult to design. Our improvements to the RNA-SSD algorithm include the support for primary structure constraints, where bases or base types are fixed in certain positions of the sequence. Such constraints are important, for example, when designing RNAs such as ribozymes or tRNAs, where certain base positions must be fixed in order to permit interaction with other molecules. We investigate the correlation between the number and the location of the primary structure constraints and the performance of RNA-SSD. In the second part of our research, we have extended the RNA-SSD algorithm to design for stability, rather than minimum free energy folding. We measure stability according to several criteria such as high probability of observing the minimum free energy structure, and low average number of incorrectly paired nucleotides in the ensemble of structures for the designed sequence. The design of complexes of RNA molecules, that is RNA molecules that interact with each other, is relevant for many applications. We describe several ways to design stable structures and complexes, and we also discuss the advantages and limitations of each approach.

Text

2011-02-11

For non-commercial purposes only, such as research, private study and education. Additional conditions apply, see Terms of Use https://open.library.ubc.ca/terms_of_use.

http://hdl.handle.net/2429/31202

Mathematics

University of British Columbia

Graduate