| Title: | Computational RNA Secondary Structure Design: Empirical complexity and Improved Methods |
| Speaker: |
Rosalia Aguirre-Hernandez
|
| Abstract |
My PhD research is focused on the design of RNA strands that are predicted
to fold to a given secondary structure, according to a standard
thermodynamic model such as that of the Turner group. The design
of RNA structures is important for applications in therapeutics and
nanotechnology.
My first contribution build on an existing algorithm called the RNA Secondary Structure Designer (RNA-SSD), one of the state of the art in computational RNA secondary structure design. RNA-SSD is a stochastic local search algorithm that efficiently search the sequence space to find a strand that is predicted to fold to a given minimum free energy structure. My improvements to the RNA-SSD algorithm include the support for primary structure constraints, the design of RNA duplexes where two RNA molecules interact with each other and the design of stable structures. To gain insights into the practical complexity of the RNA secondary structure design problem, I performed a scaling analysis using an improved version of RNA-SSD, and also the RNAinverse algorithm from the Vienna package. The data sets consist on biological structures, random structures and structures with biological characteristics. With an empirical analysis, I found that RNA-SSD scales polynomially with the size of the structure. I was also able to characterize difficult structures.
|