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

Jessica Sorrells, Leyda Almodovar, Cory Johnson, Jo Ellis-Monaghan, Author name not available (Why is that?)

Publication date: 30 July 2021

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.

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

Mathematics Subject Classification ID

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

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)