DNA Self-Assembly: Computational Complexity and Pragmatic Solutions
Modern Math Workshop 2022 October 26, 2022 - October 27, 2022
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.