  We consider the problem of efficiently designing sets (codes) of equal-length
DNA strings (words) that satisfy certain combinatorial constraints. This
problem has numerous motivations including DNA computing and DNA self-assembly.
Previous work has extended results from coding theory to obtain bounds on code
size for new biologically motivated constraints and has applied heuristic local
search and genetic algorithm techniques for code design. This paper proposes a
natural optimization formulation of the DNA code design problem in which the
goal is to design n strings that satisfy a given set of constraints while
minimizing the length of the strings. For multiple sets of constraints, we
provide high-probability algorithms that run in time polynomial in n and any
given constraint parameters, and output strings of length within a constant
factor of the optimal. To the best of our knowledge, this work is the first to
consider this type of optimization problem in the context of DNA code design.
