Mathematical Sciences Research Institute

Home » Workshop » Schedules » DNA Self-Assembly: Computational Complexity and Pragmatic Solutions

DNA Self-Assembly: Computational Complexity and Pragmatic Solutions

Modern Math Workshop 2022 October 26, 2022 - October 27, 2022

October 26, 2022 (01:45 PM PDT - 02:25 PM PDT)
Speaker(s): Leyda Almodóvar Velázquez (Stonehill College)
Primary Mathematics Subject Classification No Primary AMS MSC
Secondary Mathematics Subject Classification No Secondary AMS MSC
No Video Uploaded

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.

Supplements No Notes/Supplements Uploaded
Video/Audio Files
No Video Files Uploaded