DNA Self-Assembly: Computational Complexity and Pragmatic Solutions

Based on the tile method for DNA self-assembly, which involves branched junction molecules whose flexible k-arms are double strands of DNA, a collection of tiles can be designed to construct a nanostructure shaped like a target graph. A critical design step is finding minimal sets of branched junction molecules that will self-assemble into target structures subject without unwanted substructures forming. We apply tools from graph theory to address this problem and we show that finding optimal design strategies for this method is generally NP-complete. Additionally, we provide pragmatic solutions in the form of programs for special settings and provably optimal solutions for natural assembly targets such as platonic solids and regular lattices.