Efficient Initial Pool Generation for Weighted Graph Problems Using Parallel Overlap Assembly

Most DNA computing algorithms for mathematical problems start with combinatorial generation of an initial pool. Several methods for initial-pool generation have been proposed, including hybridization/ligation and mix/split methods. Here, we implement and compare parallel overlap assembly with the hybridization/ligation method. We applied these methods to the molecular algorithm to solve an instance of the graph problem with weighted edges. Our experimental results show that parallel overlap assembly is a better choice in terms of generation speed and material consumption than the hybridization/ligation method. Simulation of parallel overlap assembly was performed to investigate the potential and the limitation of the method.