Novel algorithms for in vitro gene synthesis

Methods for reliable synthesis of long genes offer great promise for novel protein synthesis via expression of synthetic genes. Current technologies use computational methods for design of short oligos, which can then be reliably synthesized and assembled into the desired target gene. A precursor to this process is optimization of the gene sequence for improved protein expression. In this thesis, we provide the first results on the computational complexity of oligo design for gene synthesis. For collision-oblivious oligo design -- when mishybridizations between oligos are ignored -- we give an efficient dynamic programming algorithm. We show that an abstraction of the collision-aware oligo design problem is NP-hard. We extend our collision-oblivious algorithm to achieve collision-aware oligo design, when the gene can be partitioned into independently-assembled segments. We propose additional algorithms for gene optimization and demonstrate their utility for collision-aware design. All methods are evaluated on a large biological gene set.