Solving Minimum Spanning Tree Problems Based on DNA Chemical Reaction Networks

DNA strand displacement reactions are emerging as a promising biocomputing tool. The minimum spanning tree problem is fundamental in graph theory. This paper explores the use of DNA strand displacement reaction networks for addressing the minimum spanning tree problem. We also present a computing model that is based on DNA strand displacement reactions.

The model effectively solves the minimum spanning tree problem by intelligently integrating the three reaction modules of weighted, threshold, and sum. Thus, initially, we encoded the edges in the graph using distinct DNA sequences and effectively assigned the edges their respective weights. Afterwards, the threshold module applied a filter to the weighted edges based on the fluorescence intensity. Ultimately, the sum module gathered the filtered edges to calculate the overall weight of the minimum spanning tree. In order to verify the effectiveness of the proposed method, we conducted simulation experiments using visual DSD software.

The results of the simulations showed the viability and precision of this DNA computing model in resolving intricate problems.

Furthermore, this study not only confirms the capability of DNA computing in solving problems related to graph theory, but also offers significant theoretical backing and experimental foundation for the future advancement of DNA-based computer systems and biocomputing applications.