Fall Research Expo 2023

Algorithmic Generation of DNA Self-Assembly Graphs

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 allowing the molecules to bond with each other. Due to the unpredictability of DNA self-assembly in a laboratory setting and the 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 project introduces an algorithm to computationally generate and visualize at least one valid graph and for smaller cases, all non-isomorphic graphs,  given a pot of tiles. By adjusting a number of construction parameters, we can produce graphs of various orders and proportions of tiles.

 

PRESENTED BY
NSF-REU
College of Arts & Sciences 2024
Advised By
Cory Johnson
Associate Professor of Mathematics
Amanda Harsy
Associate Professor of Mathematics
PRESENTED BY
NSF-REU
College of Arts & Sciences 2024
Advised By
Cory Johnson
Associate Professor of Mathematics
Amanda Harsy
Associate Professor of Mathematics

Comments