Nascent nanocomputers: DNA self-assembly in O(1) stages.

摘要

DNA self-assembly offers a potential for nanoscale microcircuits and computers. To make that potential possible requires the development of reliable and efficient tile assembly models. Efficiency is often achieved by minimizing tile complexity, as well as by evaluating the cost and reliability of the specific elements of each tile assembly model. We consider a 2D tile assembly model at temperature 1. The standard 2D tile assembly model at temperature 1 has a tile complexity of O(n) for the construction of exact, complete n x n squares. However, previous research found a staged tile assembly model achieved a tile complexity of O(1) to construct n x n squares, with O(logn) stages. Our staged tile assembly model achieves a tile complexity of O(logn) using only O(1) stages to construct n x n squares.