Title: Computational complexity and pragmatic solutions for flexible tile based DNA self-assembly Show Chinese title

Title: 基于灵活瓷砖的DNA自组装的计算复杂性和实用解决方案

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. Show Chinese abstract

Abstract: DNA纳米结构的分支接头分子组装，由Seeman实验室在20世纪80年代开创，已经变得越来越复杂，组装目标也是如此。一个关键的设计步骤是找到一组最小的分支接头分子，这些分子能够自组装成目标结构，而不会形成不需要的子结构。我们使用图论，这是一种用于自组装DNA复合物的自然设计工具，来解决这个问题。在确定为此方法寻找最优设计策略通常是NP完全问题后，我们提供了针对特定设置的程序方案，并为自然组装目标如正多面体、规则晶格和纳米管提供了可证明最优的解决方案。这些例子也说明了设计挑战的范围。