The Time Complexity of Self-Assembly
Florian M. Gartner, Isabella R. Graf and Erwin Frey
Time efficiency of self-assembly is crucial for many biological processes. Moreover, with the advances ofnanotechnology, time efficiency in artificial self-assembly becomes ever more important. While structuraldeterminants and the final assembly yield are increasingly well understood, kinetic aspects concerningthe time efficiency, however, remain much more elusive. In computer science, the concept oftimecomplexityis used to characterize the efficiency of an algorithm and describes how the algorithm’sruntime depends on the size of the input data. Here we characterize the time complexity ofnon-equilibrium self-assembly processes by exploring how the time required to realize a certain,substantial yield of a given target structure scales with its size. We identify distinct classes of assemblyscenarios, i.e. ‘algorithms’ to accomplish this task, and show that they exhibit drastically differentdegrees of complexity. Our analysis enables us to identify optimal control strategies for non-equilibriumself-assembly processes. Furthermore, we suggest an efficient irreversible scheme for the artificialself-assembly of nanostructures, which complements the state-of-the-art approach using reversiblebinding reactions and requires no fine-tuning of binding energies.