Computational complexity and pragmatic solutions for flexible tile based DNA self-assembly

MaRDI QIDQ6374176zbMATH OpenFDO

Authors Leyda Almodovar, Jo Ellis-Monaghan, Cory Johnson, Jessica Sorrells

Publication date 30 July 2021

Has companion code repository https://github.com/am2an7da9/spectrum-of-the-pot-with-1-2-free-variables

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Applications of graph theory (05C90) Protein sequences, DNA sequences (92D20) Molecular structure (graph-theoretic methods, methods of differential topology, etc.) (92E10)

Abstract: Branched junction molecule assembly of DNA nanostructures, pioneered by Seeman's laboratory in the 1980s, has become increasingly sophisticated, as have the assembly targets. A critical design step is finding minimal sets of branched junction molecules that will self-assemble into target structures without unwanted substructures forming. We use graph theory, which is a natural design tool for self-assembling DNA complexes, to address this problem. After determining that finding optimal design strategies for this method is generally NP-complete, we provide pragmatic solutions in the form of programs for special settings and provably optimal solutions for natural assembly targets such as platonic solids, regular lattices, and nanotubes. These examples also illustrate the range of design challenges.

This page was built for publication: Computational complexity and pragmatic solutions for flexible tile based DNA self-assembly

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6374176)