Combinatorial, topological, and computational approaches to DNA self-assembly
Applications of immediate concern have driven some of the most interesting questions in the field of graph theory, for example graph drawing and computer chip layout problems, random graph theory and modeling the internet, graph connectivity measures and ecological systems, etc. Currently, scientists are engineering self-assembling DNA molecules to serve emergent applications in biomolecular computing, nanoelectronics, biosensors, drug delivery systems, and organic synthesis. Often, the self-assembled objects, e.g. lattices or polyhedral skeletons, may be modeled as graphs. Thus, these new technologies in self-assembly are now generating challenging new design problems for which graph theory is a natural tool. We will present some new applications in DNA self-assembly and describe some of the graph-theoretical design strategy problems arising from them. We will see how finding optimal design strategies leads to developing new algorithms for graphs, addressing new computational complexity questions, and finding new graph invariants corresponding to the minimum number of components necessary to build a target structure under various laboratory settings.
Online