A new fast algorithm for solving the minimum spanning tree problem based on DNA molecules computation

Area of Science:

• Computational Biology
• Graph Theory
• Bioinformatics

Background:

• The Minimum Spanning Tree (MST) problem is a critical NP-hard problem in graph theory with broad applications.
• Existing DNA molecular operations have been limited in solving NP-hard problems like MST, typically focusing on NP-complete path problems.
• There is a need for efficient algorithms to address complex graph problems using novel computational approaches.

Purpose of the Study:

• To develop a new, fast DNA algorithm for solving the Minimum Spanning Tree (MST) problem.
• To extend the application of DNA molecular operations to NP-hard problems with multi-lateral solutions.
• To improve the efficiency and accuracy of MST problem-solving compared to existing methods.

Main Methods:

• Designed flexible length DNA strands to represent vertices and edges of an undirected graph.
• Utilized DNA molecular operations to perform computations for the MST problem.
• Analyzed the algorithm's time complexity, achieving O(3m+n) for a graph with n vertices and m edges.

Main Results:

• The proposed DNA algorithm successfully solves the MST problem with solutions in a proper length range.
• Computer simulations demonstrate significantly reduced computation time compared to existing algorithms.
• The method achieves high solution accuracy, outperforming current approaches.

Conclusions:

• The novel DNA algorithm effectively extends the utility of DNA computing for complex NP-hard graph problems.
• This approach simplifies computational complexity and offers a promising alternative for solving the MST problem.
• The findings suggest a potential for DNA computing in advanced graph theory and applied mathematics.