Algorithmic Generation of DNA Self-Assembly Graphs

Abstract

With recent advancements in the field of nanotechnology, there has been increasing interest in self-assembling nanostructures. These are constructed through the process of branched junction DNA molecules bonding with each other without external guidance. Using a flexible tile-based model, we represent molecules as vertices of a graph and cohesive ends of DNA strands as complementary half-edges. Due to the unpredictability of DNA self-assembly in a laboratory setting, there is a risk of undesirable products being incidentally constructed. Predicting what structures can be produced from a given list of components (referred to as a “pot of tiles”) is useful but has been proven NP-hard. This research introduces an algorithm that generates and visualizes one graph realized by a given pot. For smaller cases, it also produces all possible graphs up to isomorphism. By adjusting the construction parameters, the algorithm can produce graphs of any viable order and collection of proportions of tiles.