Algorithms for Nucleic Acid Sequence Design

Citation

Zadeh, Joseph N. (2010) Algorithms for Nucleic Acid Sequence Design. Dissertation (Ph.D.), California Institute of Technology. doi:10.7907/20DG-NF39. https://resolver.caltech.edu/CaltechTHESIS:05112010-205335518

Abstract

Motivated by a growing field of research focused on programming function into biomolecules, we seek to decrease the cost of high-quality rational nucleic acid sequence design while increasing its versatility and availability. We begin by describing an algorithm for designing the sequence of one or more interacting nucleic acid strands intended to adopt a target secondary structure at equilibrium. Using ensemble defect optimization, we seek to minimize the average number of incorrectly paired nucleotides at equilibrium, calculated over the entire ensemble of unpseudoknotted secondary structures. Empirically, the algorithm exhibits asymptotic optimality and costs 4/3 the time of a single objective function evaluation for large structures. We then extend this algorithm to design multi-state systems with an arbitrary number of linked targets and demonstrate its efficacy on systems invented by molecular engineers. To improve the ease of use and availability of nucleic acid analysis and design tools, we present NUPACK, a web application already in wide use that allows the international research community to share a high-performance compute cluster for the analysis and design of systems of interacting nucleic acids.

Thesis Files