Choosing the Right Neighbourhood: a Way to Improve a Stochastic Local Search Algorithm for DNA Word Design

We present results on increasing the performance of a stochastic local search algorithm for the design of DNA codes, namely sets of equal-length words over the nucleotides alphabet {A,C,G,T\} that satisfy certain combinatorial constraints. Using empirical analysis of the algorithm, we gain insight on good design principles and in turn improve the performance of the SLS algorithm. We report several cases in which our algorithm finds word sets that match or exceed the best previously known constructions.